AT_abc030_d [ABC030D] へんてこ辞書

[problemUrl]: https://atcoder.jp/contests/abc030/tasks/abc030_d ミカミくんは怪しい英単語帳を使っています。その単語帳には $ N $ 個の単語の意味が載っており、単語 $ i $ の説明には「単語 $ b_i $ と同じ意味である」とだけ書いてあります。ここで、$ i $ 番目の単語を単語 $ i $ と呼ぶことにします。 ミカミくんはまだ一つの英単語も知らないので、単語 $ i $ の意味を調べようとしたとき、単語 $ b_i $ の意味を調べようとします。ミカミくんは真面目なので、今までにすでに調べようとしたことのある単語でも同じように単語帳をひき続けます。 しかし、残念ながらこの単語帳では英単語の意味自体はどこにも書いていないため、意味を知ることはできません。 ある単語 $ i $ を調べようとして、単語帳を参照し、単語 $ b_i $ を調べようとするまでを1ステップとします。 ミカミくんが単語 $ i $ を調べようとして、$ k $ ステップ経ったとき、ミカミくんはどの単語を調べようとしているでしょうか？ ### Input & Output Format 入力は以下の形式で標準入力から与えられる。 > $ N $ $ a $ $ k $ $ b_1 $ $ b_2 $ … $ b_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) $ であることが保証される。

N/A

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

### 部分点 この問題には部分点が設定されている。 - $ k\ ≦\ 10^{18} $ を満たすデータセットに正解した場合は $ 50 $ 点が与えられる。 ### Sample Explanation 1 ミカミくんは、それぞれのステップで以下のように単語を調べます。 $ 1 $ ステップ目で、単語 $ 4 $ の意味を知るため、単語 $ 2 $ を調べようとします。 $ 2 $ ステップ目で、単語 $ 2 $ の意味を知るため、単語 $ 3 $ を調べようとします。 $ 3 $ ステップ目で、単語 $ 3 $ の意味を知るため、単語 $ 1 $ を調べようとします。 $ 4 $ ステップ目で、単語 $ 1 $ の意味を知るため、単語 $ 2 $ を調べようとします。 $ 5 $ ステップ目で、単語 $ 2 $ の意味を知るため、単語 $ 3 $ を調べようとします。 よって、$ 5 $ ステップ経ったとき、ミカミくんは単語 $ 3 $ を調べようとしています。 ### Sample Explanation 2 $ k $ はたいへん大きくなることがあります。