AT_agc031_d [AGC031D] A Sequence of Permutations

[problemUrl]: https://atcoder.jp/contests/agc031/tasks/agc031_d $ 1 $ から $ N $ の整数からなる $ 2 $ つの順列 $ p $ と $ q $ に対して、順列 $ f(p,q) $ を以下を満たす順列として定めます。 - $ f(p,q) $ の $ p_i $ ($ 1\ \leq\ i\ \leq\ N $) 項目の値は $ q_i $ である。 ただし, $ p_i $, $ q_i $ はそれぞれ $ p $, $ q $ の $ i $ 項目の値を表している。 $ 1 $ から $ N $ の整数からなる $ 2 $ つの順列 $ p $, $ q $ が与えられます。 このとき、$ 1 $ から $ N $ の順列からなる列 {$ a_n $} を以下のように定めます。 - $ a_1=p $, $ a_2=q $ - $ a_{n+2}=f(a_n,a_{n+1}) $ ( $ n\ \geq\ 1 $ ) 正整数 $ K $ が与えられるので、$ a_K $ を求めて下さい。

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ K\ \leq\ 10^9 $ - $ p $ と $ q $ は $ 1 $ から $ N $ の順列である。 ### Sample Explanation 1 $ a_3=f(p,q) $ であるから、$ f(p,q) $ が求められればよいです。 この場合は $ p_i=i $ なので、$ f(p,q)=q $ となります。