题目描述

给定长度为 $n$ 的正整数序列 $a$，求 $g(a)$ 的值：

$$g(a)=\max_{a'}\{f(a')\}\\ f(a)=\sum_{i=2}^{n} |a_{i}-a_{i-1}|$$

其中，$a'$ 是序列 $a$ 经过任意重排后得到的任意一个序列。

但是这实在是一个三岁小宝宝都会的简单题，因此你想对 $m$ 个序列都求出上述式子的最大值，这 $m$ 个序列满足以下条件。

• 第 $i$ 个序列 $p_i$ 长度为 $i$。
• 第一个序列 $p_1$ 为 $[b'_1=b_1]$。
• 第 $i$（$2\leq i\leq m$）个序列 $p_i$ 满足：对于任意满足 $1\leq j<i$ 的正整数 $j$ 满足 $p_{i,j}=p_{i-1,j}$，且 $p_{i,i} = b'_i=b_i\oplus (T\cdot g(p_{i-1}))$。

其中，$\oplus$ 表示二进制按位异或。

输入格式

第一行两个非负整数 $m$ 和 $T$，分别表示你需要求出重排后 $f$ 最大值的序列个数以及生成序列参数。

第二行 $m$ 个非负整数表示 $b_1,\dots,b_m$。

注意：【数据范围】一节仅对 $b'_i$ 的范围做出了保证，没有对 $b_i$ 的范围做出保证。

输出格式

共一行一个非负整数，为 $\oplus_{i=1}^{m} g(p_i)$。

5 0
1 2 3 4 5

14

8 0
5 2 7 1 4 3 8 6

2

提示

【样例解释 #1】

$g(p_1),g(p_2),\dots,g(p_m)$ 分别为 $0,1,3,7,11$。

令 $p'_i$ 为 $p_i$ 重排后任意满足 $f(p'_i)$ 最大的序列。

$p_1=[1]$，$p'_1=[1]$，$f(p'_1)=0$。

$p_2=[1,2]$，$p'_2=[1,2]$，$f(p'_2)=|1-2|=1$。

$p_3=[1,2,3]$，$p'_3=[1,3,2]$，$f(p'_3)=|1-3|+|3-2|=3$。

$p_4=[1,2,3,4]$，$p'_4=[3,1,4,2]$，$f(p'_4)=|3-1|+|1-4|+|4-2|=7$。

$p_5=[1,2,3,4,5]$，$p'_5=[4,2,5,1,3]$，$f(p'_5)=|4-2|+|2-5|+|5-1|+|1-3|=11$。

该样例满足测试点 $1$ 的限制。

【样例解释 #2】

$g(p_1),g(p_2),\dots,g(p_m)$ 分别为 $0,3,8,15,17,19,27,31$。

该样例满足测试点 $3$ 的限制。

【数据范围】

对于全部测试点：$1\leq m\leq 3\times 10^6$，$1\leq b'_i\leq 10^9$，$T\in \{0,1\}$。

测试点编号	$m\leq$	$T=$	特殊性质
$1$	$8$	$0$	AB
$2$	$100$
$3$	$10^3$
$4$	$2\times 10^5$
$5$			A
$6$		$1$	AB
$7$			A
$8$			无
$9$	$10^6$
$10$	$3\times 10^6$

特殊性质 A：$b'_i\leq m$（$1\leq i\leq m$）。

特殊性质 B：$b'_i\neq b'_j$（$1\leq i<j\leq m$）。