Автор: | Женя Татаринов | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
Выходной файл: | Стандартный выход |
В мире существует много маркетинговых тактик, чтобы заставить Вас покупать больше товаров в супермаркетах. Одной из таких тактик является создание лабиринта в супермаркете. Покупатель идет по заранее составленному маршруту, который проходит через определенные стенды, и при перемещении покупатель видит различные товары и ему хочется их купить.
В супер-пупер-маркете находится n различных стендов, пронумерованных целыми числами от 1 до n. В этом супер-пупер-маркете используется тактика создания лабиринта, поэтому от i-го стенда покупатель перейдет к ai-му стенду.
Вы — менеджер супер-пупер-маркета. Вам стало интересно, около какого стенда покупатель окажется через k переходов, если сейчас он находится около d-го стенда (причем Вам стало интересно q раз, то есть Вам нужно ответить на q независимых друг от друга запросов).
В первой строке входных данных вводятся натуральные числа n и q (2 ≤ n ≤ 105, 1 ≤ q ≤ 105).
В следующей строке вводится n чисел, i-е по счету число равно ai. Это означает, что от i-го стенда покупатель перейдет к ai-му стенду (1 ≤ ai ≤ n).
В следующих q строках вводятся числа di и ki (1 ≤ di ≤ n, 1 ≤ ki ≤ 109). Это означает, что для каждого запроса вам нужно сообщить, около какого стенда покупатель окажется через k переходов, если сейчас он находится около d-го стенда.
Для каждого запроса на новой строке выведите порядковый номер нужного стенда.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|