D - 漸化式 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

数列 A はすべての要素が 32 ビットの符号なし整数で表現でき、その値は次のようにして決まる。

  • はじめの K 項 A_1,\,A_2,\,...,\,A_K は入力で与えられる。
  • A とは別に K 項の数列 C_1,\,C_2,\,...,\,C_K （こちらもすべての要素が 32 ビットの符号なし整数におさまる）が入力で与えられ、K+1 項目以降の A の値はこの C を用いて次のように計算される。
    • N ≧ 1 に対し A_{N+K} = (C_1\,AND\,A_{N+K-1})\,XOR\,(C_2\,AND\,A_{N+K-2})\,XOR\,...\, XOR\,(C_K\,AND\,A_N)
    • ただし AND はビットごとの論理積、 XOR はビットごとの排他的論理和を表す。

この数列 A の M 番目の値 A_M を求めるプログラムを作成せよ。

入力

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

K M
A_1 A_2 ... A_K
C_1 C_2 ... C_K
  • 1 行目には、はじめに決まっている項の数を表す整数 K (1 ≦ K ≦ 100) および数列の求める項の番号を表す整数 M (1 ≦ M ≦ 10^9) が与えられる。
  • 2 行目には、数列 A の最初の K 項が順に与えられる。A の値はすべて 32 ビット符号なし整数におさまる。
  • 3 行目には、数列 A の K+1 項目以降を計算するときに使う数列 C の要素が順に与えられる。C の値はすべて 32 ビット符号なし整数におさまる。

出力

A_M の値を 1 行に出力せよ。

出力の末尾にも改行をいれること。

入力例1

3 5
10 20 30
7 19 13

出力例1

16

実際に A の値を計算していくと次のようになる。

  • A_4 = (7\,AND\,30)\,XOR\,(19\,AND\,20)\,XOR\,(13\,AND\,10) = 30
  • A_5 = (7\,AND\,30)\,XOR\,(19\,AND\,30)\,XOR\,(13\,AND\,20) = 16

入力例2

5 100
2345678901 1001001001 3333333333 3141592653 1234567890
2147483648 2147483647 4294967295 4294967294 3434343434

出力例2

1067078691

入力例3

30 999999999
11627 5078 8394 6412 10346 3086 3933 668 9879 11739 4501 6108 12336 8771 2768 2438 2153 7047 5476 313 1264 369 12070 10743 10663 747 370 4671 5235 3439
114 3613 3271 5032 11241 6961 3628 150 12191 2396 7638 3046 11594 8162 11136 786 9878 2356 11660 1070 3649 10882 9746 1415 3307 7077 9319 9981 3437 544

出力例3

2148