A57 - Doubling Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 個の穴がある砂場に、一匹のアリが住んでいます。このアリは規則的な動きをすることが知られており、穴 i（1 \leq i \leq N）に入った翌日には穴 A_i に移動します。

それについて、以下の Q 個のクエリを処理してください。

  • j 個目のクエリ：いま穴 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 です。