$N$ 個の町があります。町は $1$ から $N$ まで番号が振られています。

それぞれの町には$A, B, C$と名前のついた 3 台のテレポーターが設置されています。町 $i(1 \leq i \leq N)$ のテレポーター $A, B, C$の転送先はそれぞれ町$A_i$, $B_i$, $C_i$ です。

あなたはテレポータを使って旅をします。テレポータをAから順に、$A, B, C, A, B, C, A ..$と使うことにしました。(厳密には$x$の村にいる際に旅を始めてから$y$回目のテレポートのとき、移動する先は$y$を3で割った余りが1なら$A_x$、2なら$B_x$、0なら$C_x$ となります)

あなたは正の整数 $K$ が好きなので、各町から出発してテレポーターをちょうど $K$ 回使ったときに、どの町に到着するかを調べることにしました。

制約

• $1 \leq N \leq 2 \times 10^{5}$
• $0 \leq K \leq 10^{12}$
• $1 \leq Ai, Bi, Ci \leq N$

入力

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

N K
A_1 A2 .. B(N-1) AN
B1 B2 .. B(N-1) BN
C1 C2 .. C(N-1) CN

出力

出力は1行で$N$個の整数をスペース区切りで出力してください。i個目の要素は町$i$から出発して$K$回テレポータを使ったときにいる町の番号$d_i$を出力します。

d1 d2 .. d(N-1) dN

入力例1

6 4
1 2 4 3 5 6
2 1 5 4 3 6
1 2 4 3 5 6

出力例1

2 1 4 5 3 6

町1からスタートするとき、1回目はAのテレポータを使い町1に移動し、2回目はBのテレポータを使い町2に移動し、3回目はCのテレポータを使い町2に移動し、4回目はAのテレポータを使い町2に移動します。 つまり、

• i=1のとき、1->1->2->2->2です。

それぞれ、町iからスタートするとき、以下のようになります。

• i=2のとき、2->2->1->1->1です。
• i=3のとき、3->4->4->3->4です。
• i=4のとき、4->3->5->5->5です。
• i=5のとき、5->5->3->4->3です。
• i=6のとき、6->6->6->6->6です。

入力例2

1 10000
1
1
1

出力例2

1

入力例3

10 12345
2 3 4 5 6 7 8 9 1 1
1 2 3 4 5 6 5 4 3 3
1 2 4 5 6 1 5 6 10 4

出力例3

6 6 6 6 6 6 6 6 6 6