配点: 1000 点
問題文
N 洞的沙箱里。众所周知,这种蚂蚁会进行有规律的运动 输入 i(1 \leq i \leq N后的第二天) A_i 。
关于这一点,请参见下文。 Q 请处理一个查询。
- j 第二个查询:Imaana 当你在 X_j 当你在Y_j 一天后您会进入哪个洞?
制約
- 所有输入均为整数
- 1 \leq N \leq 100000
- 1 \leq Q \leq 100000
- 1 \leq A_i \leq N
- 1 \leq X_j \leq N
- 1 \leq Y_j \leq 10^9
入力
输入是按以下格式从标准输入给出的。
N Q A_1 A_2 \ldots A_N X_1 Y_1 X_2 Y_2 \vdots X_Q Y_Q
出力
Q 行。 在j 行中,j 请输出查询的答案。
入力例 1
7 4 2 4 1 7 6 5 3 1 1 1 5 2 13 5 999999999
出力例 1
2 1 3 6
今名 1 当你在
- 1 几天后出现一个洞 我在 A_1 = 2
- 2 几天后出现一个洞 我在 A_2 = 4
- 3 几天后出现一个洞 我在 A_4 = 7
- 4 几天后出现一个洞 我在 A_7 = 3
- 5 几天后出现一个洞 我在 A_3 = 1
。因此,1, 2 每个查询的答案是 2, 1 。