一首诗

题目描述最后有形式化题意。

文学大师 ZHY 创作了一首诗。 这首诗由 $n$ 个单词组成，为了方便表述，ZHY 将这首诗记录为一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$。创作完后，ZHY 立刻将自己的作品分享给了 YHZ。YHZ 在感受到了诗歌之美后，希望借此提高一下自己的文学素养，于是准备对这首诗中的诗句进行摘抄。 YHZ 认为一个“诗句”，应该是 $a_1,a_2,\dots,a_n$ 的一个**连续**子序列，诗句的长度即为子序列的长度。当然，他不会摘抄所有的诗句，而是只选择“优美的诗句”进行摘抄。由于不懂文法，YHZ 简单地认为一个诗句是“优美的”，当且仅当这个诗句中不存在两个**相邻**的重复单词。形式化的说，一个连续子序列 $a_l,a_{l+1},\dots,a_r$（$l\leq r$）组成的诗句是“优美的”，当且仅当对于所有的 $l\leq i<r$，有 $a_i\neq a_{i+1}$。 YHZ 发现文学大师 ZHY 写的诗里优美的诗句太多了，所以他需要进行归类。不过还是由于他不懂文法，他希望直接按照句子的长度归类。记 $b_i$ 为长度为 $i$ 的优美的诗句的个数，YHZ 希望知道 $b_1,b_2,\dots,b_n$。但即使是所有的 $b$ 数量也太多了，所以他只需要知道 $b_1\oplus b_2\oplus\dots\oplus b_n$。 还没等 YHZ 摘抄结束，文学大师 ZHY 告诉 YHZ 他要进行 $Q$ 次润色。具体地，每次润色，ZHY 会选择一个诗句 $[l_i,r_i]$ 和一个整数 $x_i$，并对所有的 $l_i\leq j\leq r_i$，将单词 $a_j$ 修改为 $a_j+x_i$。好学的 YHZ 希望对每次润色后的诗歌进行摘抄，即对于每次修改后的 $a_1,a_2\dots,a_n$，知道 $b_1\oplus b_2\oplus\dots\oplus b_n$。 不过文学大师 ZHY 太卷了，他进行的润色次数太多了，YHZ 还是承受不了这么大的工作量，所以他希望你帮帮他。 **形式化题面：** 给定一个序列 $a_{1\sim n}$，定义 $b_i$ 表示 $a$ 中有多少个长度为 $i$ 的区间使得任意两个相邻的数都不同。有 $q$ 次操作，每次操作给定 $l,r,x$，表示将 $a_{l\sim r}$ 都加上 $x$。请在第一次操作之前和每次操作之后求出 $b_1\oplus b_2\oplus \cdots \oplus b_n$。其中 $\oplus$ 表示按位异或。

第一行两个正整数 $n,q$。 第二行 $n$ 个整数 $a_{1},a_{2},\cdots,a_{n}$。 接下来 $q$ 行，每行三个整数 $l_{i},r_{i},x_{i}$，表示一次操作。

输出 $q+1$ 行，表示第一次操作前和每次操作后的答案。

4 2
1 2 3 4
1 2 1
2 3 1

4
6
5

样例解释： 第一次修改之前序列为 $[1,2,3,4]$，得到 $b_1=4,b_2=3,b_3=2,b_4=1$，故答案为 $4\oplus 3 \oplus 2\oplus 1=4$。 第一次修改之后序列为 $[2,3,3,4]$，得到 $b_1=4,b_2=2,b_3=0,b_4=0$，故答案为 $4\oplus 2 \oplus 0\oplus 0=6$。 第二次修改之后序列为 $[2,4,4,4]$，得到 $b_1=4,b_2=1,b_3=0,b_4=0$，故答案为 $4\oplus 1 \oplus 0\oplus 0=5$。 ---- | 子任务编号 | $n$ | $q$ | 特殊性质 | 分值 | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $0$ | $\le 300$ | $\le 300$ | 无 | $15$ | | $1$ | $\le 5000$ | $\le 5000$ | 无 | $15$ | | $2$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | 保证 $a_i,x$ 在值域内均匀随机 | $10$ | | $3$ | $\le 5\times 10^4$ | $\le 5\times 10^4$ | 无 | $30$ | | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $l=1,r=n$ | $5$ | | $5$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | 无 | $25$ | 对于所有数据，$1 \le n,q \le 2\times 10^5$，$1\le l \le r \le n$，$0\le |x|,|a_i|\le 10^9$。