Beautiful Poem Segments

Literary master ZHY composed a poem consisting of (n) words. For convenience, he recorded his poem as an integer sequence (a_1, a_2, \dots, a_n). After creation, he immediately shared his work with YHZ. Deeply touched by the poem’s beauty, YHZ decided to excerpt some of its "sentences" to elevate his literary taste.

A sentence is defined as any contiguous subsequence of (a_1, a_2, \dots, a_n). Its length is the number of words in that subsequence. However, YHZ only likes to copy the "beautiful sentences". Since he does not know much about grammar, he simply considers a sentence beautiful if and only if it does not contain any two adjacent identical words. Formally, a contiguous subsequence (a_l, a_{l+1}, \dots, a_r) (where (1 \le l \le r \le n)) is beautiful if and only if for every (l \le i < r) we have (a_i \neq a_{i+1}).

For each (i) from (1) to (n), let (b_i) denote the number of beautiful sentences of length (i) in (a). YHZ is interested in the value [ S = b_1 \oplus b_2 \oplus \cdots \oplus b_n, ] where (\oplus) denotes the bitwise XOR operation.

However, before YHZ can finish his excerpts, the master ZHY announces that he will perform (q) modifications. In each modification, ZHY selects an interval ([l, r]) and an integer (x), and adds (x) to every word in that interval, i.e. for every (l \le j \le r), set (a_j \leftarrow a_j + x). After each modification (and also before any modification), YHZ would like to know the updated value of (S = b_1 \oplus b_2 \oplus \cdots \oplus b_n).

Your task is to help YHZ: Given the initial array (a) and (q) modifications, compute (S) before any modification and after each modification.

Note: A contiguous subsequence \(a_l, a_{l+1}, \dots, a_r\) is beautiful if for every \(l \le i < r\), \(a_i \neq a_{i+1}\).

inputFormat

The first line contains two integers \(n\) and \(q\) \((1 \le n, q \le 10^5)\): the number of words in the poem and the number of modifications.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) \(|a_i| \le 10^9\) representing the poem.

Each of the next \(q\) lines contains three integers \(l, r, x\) \((1 \le l \le r \le n, |x| \le 10^9)\) meaning that for every \(l \le j \le r\), the word \(a_j\) is increased by \(x\).

outputFormat

Output \(q+1\) lines. The first line is the value of \(S = b_1 \oplus b_2 \oplus \cdots \oplus b_n\) for the initial array. Each of the next \(q\) lines should contain the value of \(S\) after the corresponding modification.

sample

5 2
1 2 2 3 4
2 3 1
1 5 -1

7
7
7