传送门的多步落点

难度：T2

【知识点：倍增与二进制跳跃】

前置知识：本单元此前讲解的状态、边界与实现。

题目描述

有 $n$ 个站点，每个站点都指定了唯一的下一站。每次询问给出起点和跳转步数，求按后继关系走完这些步后所在的站点。每次询问独立从指定起点出发。

输入格式

第一行$n$、$q$，第二行$n$个后继编号；之后$q$行，每行起点$s$和步数$k$。

规则说明

第 $i$ 个后继编号表示：位于站点 $i$ 时，走一步就到这个编号的站点。每一步都按当前位置的后继继续跳转，可以回到已经经过的站点；走 $0$ 步时仍在起点。

输出格式

每行输出相应落点。

数据范围

$1\le n,q\le 100000$，后继与$s$在$1$..$n$，$0\le k\le 10^9$。

样例输入

4 3
2 3 4 1
1 13
3 0
2 1000000000

样例输出

2
3
2

样例输入 2

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

样例输出 2

1
4
3

样例说明 2

三次询问分别停在 $1,4,3$。最后一次的路线是 $2,3,4,2,3$。