问题陈述

给定一个长度为$N$的非负整数序列$A=(A_1,A_2,\\dots,A_N)$和一个正整数$K$。

找出对于所有满足$1 \\leq X_i \\leq N\\ (1\\leq i \\leq K)$的$K$个正整数序列$X=(X_1,X_2,\\dots,X_K)$，计算$\\displaystyle \\sum_{i=1}^{K} A_{X_i}$ 的按位异或（bitwise XOR）值。

什么是按位异或（bitwise XOR）？

正整数$A$和$B$的按位异或$A \\oplus B$ 定义如下：

• 当用二进制表示并将$A \\oplus B$写成二进制时，在第$2^k$位（$k \\geq 0$）上的数字为$1$当且仅当在该位的$A$和$B$中有且仅有一个数字为$1$，否则为$0$。

例如，我们有 $3 \\oplus 5 = 6$（二进制表示为：$011 \\oplus 101 = 110$）。
一般地，$k$个非负整数$p_1, p_2, p_3, \\dots, p_k$的按位异或$(p_1 \\oplus p_2) \\oplus p_3 \\oplus \\dots \\oplus p_k$ 可以定义为 $(\\dots ((p_1 \\oplus p_2) \\oplus p_3) \\oplus \\dots \\oplus p_k)$。我们可以证明，该值与$p_1, p_2, p_3, \\dots, p_k$的顺序无关。

约束条件

• $1 \\leq N \\leq 1000$
• $1 \\leq K \\leq 10^{12}$
• $0 \\leq A_i \\leq 1000$
• 输入的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $K$ $A_1$ $A_2$ $\\dots$ $A_N$

输出

打印答案。

示例输入1

2 2
10 30

示例输出1

40

需要考虑四个序列：$(X_1,X_2)=(1,1),(1,2),(2,1),(2,2)$，对应的$A_{X_1}+A_{X_2}$ 分别为 $20,40,40,60$。因此，答案为 $20 \\oplus 40 \\oplus 40 \\oplus 60=40$。

示例输入2

4 10
0 0 0 0

示例输出2

0

示例输入3

11 998244353
314 159 265 358 979 323 846 264 338 327 950

示例输出3

236500026047