Задача B. Супер-пупер-маркет

Автор:Женя Татаринов   Ограничение времени: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
3 5
2 3 1
1 1
1 2
1 3
1 4
1 5
2
3
1
2
3

0.053s 0.009s 13