Background

A formal statement of the problem is given at the end of the description.

Problem Description

Literary master ZHY created a poem.

This poem consists of $n$ words. For convenience, ZHY records the poem as an integer sequence of length $n$: $a_1,a_2,\dots,a_n$. After finishing, ZHY immediately shared his work with YHZ. After appreciating the beauty of the poem, YHZ wants to improve his literary skills by excerpting lines from it.

YHZ believes that a “line” should be a continuous subsequence of $a_1,a_2,\dots,a_n$, and the length of the line is the length of that subsequence. Of course, he will not excerpt all lines, but only chooses “beautiful lines” to excerpt. Since he does not understand grammar, YHZ simply thinks a line is “beautiful” if and only if there are no two adjacent repeated words in the line. Formally, a line formed by a continuous subsequence $a_l,a_{l+1},\dots,a_r$ ($l\leq r$) is “beautiful” if and only if for all $l\leq i<r$, we have $a_i\neq a_{i+1}$.

YHZ finds that there are too many beautiful lines in ZHY’s poem, so he needs to classify them. Still because he does not understand grammar, he wants to classify them directly by line length. Let $b_i$ be the number of beautiful lines of length $i$. YHZ wants to know $b_1,b_2,\dots,b_n$. But even the total number of all $b$ values is too large, so he only needs $b_1\oplus b_2\oplus\dots\oplus b_n$.

Before YHZ finishes excerpting, literary master ZHY tells YHZ that he will make $Q$ rounds of polishing. Specifically, in each round, ZHY chooses a segment $[l_i,r_i]$ and an integer $x_i$, and for all $l_i\leq j\leq r_i$, he modifies the word $a_j$ to $a_j+x_i$. Studious YHZ wants to excerpt the poem after each polishing; that is, for the sequence $a_1,a_2,\dots,a_n$ after each modification, he wants to know $b_1\oplus b_2\oplus\dots\oplus b_n$.

However, ZHY is too hardworking and makes too many rounds of polishing, and YHZ cannot handle such a large workload. So he asks you to help him.

Formal statement:

Given a sequence $a_{1\sim n}$, define $b_i$ as the number of intervals of length $i$ in $a$ such that any two adjacent numbers are different. There are $q$ operations. Each operation gives $l,r,x$, meaning adding $x$ to all elements in $a_{l\sim r}$. Please output $b_1\oplus b_2\oplus \cdots \oplus b_n$ before the first operation and after each operation, where $\oplus$ denotes bitwise XOR.

Input Format

The first line contains two positive integers $n,q$.

The second line contains $n$ integers $a_{1},a_{2},\cdots,a_{n}$.

The next $q$ lines each contain three integers $l_{i},r_{i},x_{i}$, describing one operation.

Output Format

Output $q+1$ lines, representing the answer before the first operation and after each operation.

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

4
6
5

Hint

Explanation of the sample:

Before the first modification, the sequence is $[1,2,3,4]$. We get $b_1=4,b_2=3,b_3=2,b_4=1$, so the answer is $4\oplus 3 \oplus 2\oplus 1=4$.

After the first modification, the sequence is $[2,3,3,4]$. We get $b_1=4,b_2=2,b_3=0,b_4=0$, so the answer is $4\oplus 2 \oplus 0\oplus 0=6$.

After the second modification, the sequence is $[2,4,4,4]$. We get $b_1=4,b_2=1,b_3=0,b_4=0$, so the answer is $4\oplus 1 \oplus 0\oplus 0=5$.

For all testdata, $1 \le n,q \le 2\times 10^5$, $1\le l \le r \le n$, $0\le |x|,|a_i|\le 10^9$.

Translated by ChatGPT 5