Estás jugando a un juego que consta de ~n~ planetas. Cada planeta tiene un teletransportador a otro planeta (o al propio planeta).

Tu tarea es procesar ~q~ consultas de la forma: cuando empiezas en el planeta ~x~ y viajas a través de ~k~ teletransportadores, ¿a qué planeta llegarás?

Entrada

La primera línea de entrada tiene dos enteros ~n~ y ~q~: el número de planetas y consultas. Los planetas se numeran ~1,2,\dots,n~.

La segunda línea tiene ~n~ enteros ~t_1,t_2,\dots,t_n~: para cada planeta, el destino del teletransportador. Es posible que ~t_i=i~.

Por último, hay ~q~ líneas que describen las consultas. Cada línea tiene dos enteros ~x~ y ~k~: se empieza en el planeta ~x~ y se viaja a través de ~k~ teletransportadores.

Salida

Imprime la respuesta a cada consulta.

Restricciones

• ~1 \leq n, q \leq 2 \cdot 10^5~
• ~1 \leq t_i \leq n~
• ~1 \leq x \leq n~
• ~0 \leq k \leq 10^9~

Ejemplo de Entrada

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

Ejemplo de Salida

1
2
4