配点: 400点

問題文

11 から NN までの番号が付いた NN 個のマスがあります。また、スイッチは MM 個あり、それぞれのスイッチはマス Cj(1jM)C_j (1≦ j ≦M) にあります。
全てのスイッチにON/OFF の 22 つの状態があります。最初スイッチは OFF です。また、全てのスイッチは共有されており、ひとつのスイッチの状態が変化するとすべてのスイッチも同様に変化します。

くしらくんはマス 11 にコマを置き、以下の操作を KK 回行いました。

今コマがいるマスを xx としたとき、

  • スイッチが OFF ならば、コマを AxA_x に移動させ、移動した先にスイッチがあるならばそれを 11 回押す。
  • スイッチが ON ならば、コマを BxB_x に移動させ、移動した先にスイッチがあるならばそれを 11 回押す。

KK 回の操作を終えた後、コマはどのマスにいるか答えてください。

制約

  • 1MN1051 ≦ M ≦ N ≦ 10^5
  • 1K10181 ≦ K ≦ 10^{18}
  • 1Ai,BiN1 ≦ A_i, B_i ≦ N
  • 1CjN1 ≦ C_j ≦N
  • 入力はすべて整数である

入力

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

NN MM KK
A1A_1 A2A_2 ... ANA_N
B1B_1 B2B_2 ... BNB_N
C1C_1 C2C_2 ... CMC_M

出力

答えを出力してください。


入出力例1

  • 入力
4 2 3
2 4 3 1
4 1 1 2
2 4
  • 出力
4

コマは、11(OFF)→22(ON)→11(ON)→44(OFF) と移動します。


入出力例1

  • 入力
1 1 10000000000
1
1
1
  • 出力
1

操作を行ってもコマの位置が変わらない場合があります。

Submit


Go (1.21)