Un árbol tiene \(n\) nodos con raíz en el \(0\). Responde \(q\) consultas: el \(k\)-ésimo ancestro del nodo \(u\) (el primer ancestro es el padre, el segundo el padre del padre, etc.), o \(-1\) si no existe.

Subir de a un nodo puede costar \(O(n)\) por consulta: hace falta algo más rápido.

Entrada

La primera línea tiene \(n\) y \(q\) \((1 \le n, q \le 10^5)\). La segunda tiene \(p_0, \dots, p_{n-1}\). El árbol se da con el arreglo de padres: el padre del nodo \(i\) es \(p_i\), y la raíz es el nodo \(0\), con \(p_0 = -1\). Cada una de las siguientes \(q\) líneas tiene una consulta \(u\) \(k\) \((0 \le u < n, 1 \le k \le n)\).

Salida

Para cada consulta, una línea con el ancestro o \(-1\).

Ejemplo 1

Entrada

7 3
-1 0 0 1 1 2 2
3 1
5 2
6 3

Salida

1
0
-1