Ви граєте в гру, яка складається з \(n\) планет. Кожна планета має телепорт на іншу планету (або на саму планету).

Ваше завдання полягає в тому, щоб обробити \(q\) запитів такого вигляду:

• коли ви починаєте на планеті \(x\) і подорожуєте через \(k\) телепортів, якої планети ви досягнете?

Обмеження

• \(1≤n,q≤2⋅10^5\)
• \(1≤t_i​ ≤n\)
• \(1≤x≤n\)
• \(0≤k≤10^9\)

Формат вхідних даних

У першому рядку є два цілих числа \(n\) і \(q\): кількість планет і запитів. Планети пронумеровані \(1,2,…,n\).

У другому рядку \(n\) цілих чисел \(t_1,t_2,…,t_n\): для кожної планети пункт призначення телепортатора. Можливо, що \(t_i=i\).

Нарешті, є \(q\) рядків, що описують запити. Кожен рядок містить два цілих числа \(x\) і \(k\): ви починаєте на планеті \(x\) і подорожуєте через \(k\) телепортів.

Формат вихідних даних

Вивести відповідь на кожен запит.

Приклад вхідних даних

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

Приклад вихідних даних

1
2
4