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

Условие

В мире существует много маркетинговых тактик, чтобы заставить Вас покупать больше товаров в супермаркетах. Одной из таких тактик является создание лабиринта в супермаркете. Покупатель идет по заранее составленному маршруту, который проходит через определенные стенды, и при перемещении покупатель видит различные товары и ему хочется их купить.

В супер-пупер-маркете находится n различных стендов, пронумерованных целыми числами от 1 до n. В этом супер-пупер-маркете используется тактика создания лабиринта, поэтому от i-го стенда покупатель перейдет к a_i-му стенду.

Вы — менеджер супер-пупер-маркета. Вам стало интересно, около какого стенда покупатель окажется через k переходов, если сейчас он находится около d-го стенда (причем Вам стало интересно q раз, то есть Вам нужно ответить на q независимых друг от друга запросов).

Формат входных данных

В первой строке входных данных вводятся натуральные числа n и q (2 ≤ n ≤ 10⁵, 1 ≤ q ≤ 10⁵).

В следующей строке вводится n чисел, i-е по счету число равно a_i. Это означает, что от i-го стенда покупатель перейдет к a_i-му стенду (1 ≤ a_i ≤ n).

В следующих q строках вводятся числа d_i и k_i (1 ≤ d_i ≤ n, 1 ≤ k_i ≤ 10⁹). Это означает, что для каждого запроса вам нужно сообщить, около какого стенда покупатель окажется через k переходов, если сейчас он находится около d-го стенда.

Формат выходных данных

Для каждого запроса на новой строке выведите порядковый номер нужного стенда.

Примеры тестов

3 5
2 3 1
1 1
1 2
1 3
1 4
1 5

2
3
1
2
3

Разбор

Давайте для каждого 2^k ≤ d_i посчитаем, около какого стенда окажется покупатель через 2^k переходов, если сейчас он находится около стенда под номером x. Для этого существует формула: s(x, k) = s(s(x, k − 1), k − 1) при k > 0

Теперь каждое d_i представим в виде суммы степеней двойки, и будет подниматься по нужным s(x, k). Итоговая асимптотика — O((n + q) * log(10⁹))