P14353 重排

给定长度为 $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

第一行两个非负整数 $m$ 和 $T$，分别表示你需要求出重排后 $f$ 最大值的序列个数以及生成序列参数。 第二行 $m$ 个非负整数表示 $b_1,\dots,b_m$。 **注意：【数据范围】一节仅对 $b'_i$ 的范围做出了保证，没有对 $b_i$ 的范围做出保证。**

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

**【样例解释 #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$ | $0$ | AB | | $3$ | $10^3$ | $0$ | AB | | $4$ | $2\times 10^5$ | $0$ | AB | | $5$ | $2\times 10^5$ | $0$ | A | | $6$ | $2\times 10^5$ | $1$ | AB | | $7$ | $2\times 10^5$ | $1$ | A | | $8$ | $2\times 10^5$ | $1$ | 无 | | $9$ | $10^6$ | $1$ | 无 | | $10$ | $3\times 10^6$ | $1$ | 无 | 特殊性质 A：$b'_i\leq m$（$1\leq i\leq m$）。 特殊性质 B：$b'_i\neq b'_j$（$1\leq i