AtCoder Beginner Contest 030

D - へんてこ辞書


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

ミカミくんは怪しい英単語帳を使っています。その単語帳には N 個の単語の意味が載っており、単語 i の説明には「単語 b_i と同じ意味である」とだけ書いてあります。ここで、i 番目の単語を単語 i と呼ぶことにします。 ミカミくんはまだ一つの英単語も知らないので、単語 i の意味を調べようとしたとき、単語 b_i の意味を調べようとします。ミカミくんは真面目なので、今までにすでに調べようとしたことのある単語でも同じように単語帳をひき続けます。 しかし、残念ながらこの単語帳では英単語の意味自体はどこにも書いていないため、意味を知ることはできません。 ある単語 i を調べようとして、単語帳を参照し、単語 b_i を調べようとするまでを1ステップとします。

ミカミくんが単語 i を調べようとして、k ステップ経ったとき、ミカミくんはどの単語を調べようとしているでしょうか?


入出力

入力は以下の形式で標準入力から与えられる。

N a
k
b_1 b_2b_N
  • 1 行目には、単語の数 N (2 ≦ N ≦ 10^5) とミカミくんが調べようとしている単語の番号 a (1 ≦ a ≦ N) がスペース区切りで与えられる。
  • 2 行目には、ミカミくんが単語を調べるステップ数 k(1 ≦ k ≦ 10^{100000}) が与えられる。
  • 3 行目には、各単語の説明を表す N 個の整数 b_1,...,b_N が空白区切りで与えられる。
  • 1 ≦ b_i ≦ N かつ b_i ≠ i (1 ≦ i ≦ N) であることが保証される。

部分点

この問題には部分点が設定されている。

  • k ≦ 10^{18} を満たすデータセットに正解した場合は 50 点が与えられる。

出力

ミカミくんが単語 a を調べようとしてから k ステップ経ったとき、調べようとしている単語の番号を 1 行に出力せよ。出力の末尾にも改行をいれること。


入力例1

6 4
5
2 3 1 2 6 5

出力例1

3

ミカミくんは、それぞれのステップで以下のように単語を調べます。

1 ステップ目で、単語 4 の意味を知るため、単語 2 を調べようとします。

2 ステップ目で、単語 2 の意味を知るため、単語 3 を調べようとします。

3 ステップ目で、単語 3 の意味を知るため、単語 1 を調べようとします。

4 ステップ目で、単語 1 の意味を知るため、単語 2 を調べようとします。

5 ステップ目で、単語 2 の意味を知るため、単語 3 を調べようとします。

よって、5 ステップ経ったとき、ミカミくんは単語 3 を調べようとしています。


入力例2

4 1
100000000000000000000
2 3 4 1

出力例2

1

k はたいへん大きくなることがあります。


入力例3

8 1
1
2 3 4 5 3 2 4 5

出力例3

2

Submit提出する