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

それぞれの町にはと名前のついた 3 台のテレポーターが設置されています。町 のテレポーター の転送先はそれぞれ町, , です。

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

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

制約


入力


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

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

出力


出力は1行で個の整数をスペース区切りで出力してください。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

Submit


Go (1.14)