AB的值（含easy,hard)【鱼CR3】

一个很好的体验

题目背景

本题是第五题/第六题。

本题的满分是 200 分，easy 占 100 分，hard 占 100 分，easy, hard 题面相同，仅仅是数据范围上的不同。所以我们就整合为了 1 道题

题目描述

zhangjinxuan 有一个非负整数序列 $A=(A_1, A_2, ..., A_N)$。

Wei_Yuanhao 要问 zhangjinxuan $K$ 个问题，第 $i$ 个问题会给你一个正整数 $B, X$，问当执行以下操作后 $A_B$ 为多少？

1. 重复执行以下 $X$ 次操作：

   • 将 $B$ 设置为 $A_B$。

输入格式

N K
A_1 A_2 ... A_N
B_i X_i
B_i+1 X_i+1
...
B_K X_K

输出格式

一共 $K$ 行，每一行都表示结果。

样例 #1

样例输入 #1

5 10
2 3 4 5 1
5 1
5 0
5 2
1 3
2 3
4 100
5 100
1 100
2 100
3 100

样例输出 #1

2
1
3
5
1
5
1
2
3
4

样例 #2

样例输入 #2

4 6
2 2 4 3
2 1
2 5
3 2
3 10
2 1000
1 2000

样例输出 #2

2
2
4
4
2
2

提示

样例解释1

对于第 4 组询问，也就是 1 3，操作流程如下：

1. 开始之前，$B=1$
2. 第 $1$ 步，$B=A_1=2$
3. 第 $2$ 步，$B=A_2=3$
4. 第 $3$ 步，$B=A_2=4$

所以答案是 $A_4$，也就是 5。

样例解释2

对于第 2 组询问，也就是 2 5，操作流程如下：

1. 开始之前，$B=2$
2. 第 $1$ 步，$B=A_2=2$
3. 第 $2$ 步，$B=A_2=2$

...

这个是一个 2 的循环，所以答案是 $A_2$，也就是 2。

对于第 3 组询问，也就是 3 2，操作流程如下：

1. 开始之前，$B=3$
2. 第 $1$ 步，$B=A_3=4$
3. 第 $2$ 步，$B=A_4=3$

所以答案是 $A_3$，也就是 4。

Easy 难度数据范围

对于 60% 的数据，保证 $1 \le N, K, X \le 100$

另外 20% 的数据，保证 $X =1$

对于 100% 的数据，保证 $1 \le N, K, X \le 2000$

$1 \le A_i \le N$，但不保证 $A_i \neq A_j (i \neq j)$。

$1 \le B \le N$

Hard 难度数据范围

对于 100% 的数据，保证 $1 \le N, K, X \le 2 \times 10^{5}$

$1 \le A_i \le N$，但不保证 $A_i \neq A_j (i \neq j)$。

$1 \le B \le N$

所有输入均为整数。