← 返回题目列表

AtCoder · tessoku_book_be

A57. 加倍

中文机器翻译题面 查看原题

配点: 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 。