给定 Nimber 数列 $a_1, a_2, \dots, a_{K-1}$，$b_1, b_2, \dots, b_5$ 以及 $c_1, c_2, \dots, c_5$。

对于所有 $n \ge K$，定义： $$a_n = \left( \bigoplus_{i=1}^5 a_{n-i} \otimes b_i \right) \oplus \left( \bigoplus_{i=1}^5 a_{n-K+i} \otimes c_i \right)$$

求 $a_m$ 的值。

说明

Nimber 是与 Nim 游戏相关的非负整数。对于本题，需要用到以下两种运算：

• “$\oplus$” 是 Nim 和：$a \oplus b = \text{mex} \{a' \oplus b \mid 0 \le a' < a\} \cup \{a \oplus b' \mid 0 \le b' < b\}$。
• “$\otimes$” 是 Nim 积：$a \otimes b = \text{mex} \{(a' \otimes b) \oplus (a \otimes b') \oplus (a' \otimes b') \mid 0 \le a' < a, 0 \le b' < b\}$。

其中，$\text{mex}(S)$ 表示不在集合 $S$ 中的最小非负整数。

输入格式

第一行包含两个正整数 $K$ 和 $m$ ($6 \le K \le 10^5, 1 \le m \le 10^{18}$)。 第二行包含 $K-1$ 个非负整数 $a_1, a_2, \dots, a_{K-1}$ ($0 \le a_i < 2^{32}$)。 第三行包含五个非负整数 $b_1, b_2, \dots, b_5$ ($0 \le b_i < 2^{32}$)。 第四行包含五个非负整数 $c_1, c_2, \dots, c_5$ ($0 \le c_i < 2^{32}$)。

输出格式

输出一行，包含一个整数：$a_m$ 的值。

样例

样例输入 1

6 1000000000000000000
1 2 3 4 5
1 0 0 0 0
0 0 0 0 0

样例输出 1

5

样例输入 2

6 10
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15

样例输出 2

9

样例输入 3

11 123
849 674 223 677 243 657 979 583 643 845
979 282 313 567 433
122 443 132 554 132

样例输出 3

32098