Uolevi pelaa peliä, jossa on n tasoa. Jokaisella tasolla on teleportti, josta pääsee jollekin toiselle tasolle.

Tehtäväsi on vastata joukkoon kyselyitä, joissa Uolevi aloittaa tasolta x ja kulkee k kertaa eteenpäin teleportin kautta. Sinun tulee ilmoittaa, mille tasolle Uolevi päätyy.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja q: tasojen määrä ja kyselyiden määrä. Tasot on numeroitu kokonaisluvuin 1,2,\ldots,n.

Seuraavalla rivillä on n lukua t_1,t_2,\ldots,t_n. Luku t_i kertoo, mille tasolle tason i teleportista pääsee.

Lopuksi syötteessä on q riviä, jotka kuvaavat kyselyt. Jokaisella rivillä on kaksi kokonaislukua x ja k: Uolevi aloittaa tasolta x ja liikkuu eteenpäin k teleportin kautta.

Tuloste

Tulosta jokaiseen kyselyyn, mille tasolle Uolevi päätyy lopulta.

Rajat

• 1 \le n,q \le 10^5
• 1 \le x \le n
• 1 \le k \le 10^9

Esimerkki

Syöte:

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

Tuloste:

2
4
4