Прыжковые указатели

Миллион вершин, миллион запросов «$k$-й предок», шестьдесят четыре мегабайта.

В первой строке $n$ и $q$ ($1 \le n \le 10^6$, $1 \le q \le 10^6$). Во второй строке $n-1$ родителей (родитель имеет меньший номер). В следующих $q$ строках по два числа $v$ и $k$.

Для каждого запроса выведите предка вершины $v$ на $k$ шагов вверх или $-1$, если такого нет.