P10255 A Poem

A formal statement of the problem is given at the end of the 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

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 $q+1$ lines, representing the answer before the first operation and after each operation.

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$. ---- | Subtask ID | $n$ | $q$ | Special Property | Score | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $0$ | $\le 300$ | $\le 300$ | None | $15$ | | $1$ | $\le 5000$ | $\le 5000$ | None | $15$ | | $2$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | Guaranteed that $a_i,x$ are uniformly random within the value range | $10$ | | $3$ | $\le 5\times 10^4$ | $\le 5\times 10^4$ | None | $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$ | None | $25$ | 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