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