Description

To the south there is a land of immortals, called Mosuo; in Mosuo there is a lake, and it is Lugu.

Chacha is searching for her dream in Lugu Lake. In the hazy mist, Chacha’s $n$ dreams are arranged into a sequence. All of Chacha’s dreams look like “Lawa” (Lawa). To distinguish these Lawa, Chacha defines that the “beauty value” of the $i$-th Lawa from left to right is a non-negative integer $a_i$. Facing these dreams, Chacha will perform $m$ operations. Each operation gives two numbers $p, x$, and then applies bitwise XOR with $x$ to both $a_p$ and $a_{p+1}$. After each operation, Chacha wants to know: in the current dream sequence, how many subsegments $[l, r]$ satisfy $l \le r$ and have XOR sum equal to $0$. Please answer Chacha’s question.

The XOR sum of segment $[l, r]$ is defined as $a_l \otimes a_{l + 1} \otimes \dots a_{r - 1} \otimes a_r$, where $\otimes$ denotes the binary bitwise XOR operation, i.e. the “^” operator in C++. Two segments are different if and only if their left endpoints are different, or their right endpoints are different, or both are different.

To avoid overly large output, you only need to output four integers: the bitwise XOR of all your answers, the number of times your answer is odd, the maximum among all your answers, and the minimum among all your answers.

Input Format

The first line contains two integers, representing the number of dreams $n$ and the number of operations $m$.
The second line contains $n$ space-separated integers, where the $i$-th integer is the beauty value $a_i$ of the $i$-th Lawa.
The next $m$ lines each contain two integers, denoting the $p$ and $x$ of one operation in order.

Output Format

Output four lines, each containing one integer, in order: the bitwise XOR of all your answers, the number of times your answer is odd, the maximum among all your answers, and the minimum among all your answers.

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

3
3
3
1

Hint

Sample 1 Explanation

• After the first operation, the sequence becomes ${2,1,3,4,5}$. There is exactly one segment $[1,3]$ whose XOR sum is $0$, so the answer for this query is $1$.
• After the second operation, the sequence becomes ${2,2,0,4,5}$. The segments $[1,2]$, $[1,3]$, and $[3,3]$ have XOR sum $0$, so the answer for this query is $3$.
• After the third operation, the sequence becomes ${2,2,3,7,5}$. There is exactly one segment $[1,2]$ whose XOR sum is $0$, so the answer for this query is $1$. The XOR of all answers is $3$. There are $3$ times when the answer is odd. The maximum among all answers is $3$, and the minimum is $1$.

Constraints

This problem uses bundled subtasks, with 5 subtasks in total.

• Subtask $1$ ($10$ points): $n, m \le 100$.
• Subtask $2$ ($10$ points): $n, m \le 300$.
• Subtask $3$ ($20$ points): $n, m \le 3000$.
• Subtask $4$ ($30$ points): $n, m \le 10^5$.
• Subtask $5$ ($30$ points): no special restrictions.

For the first four subtasks, it is guaranteed that $a_i, x \le n$.
For all testdata, it is guaranteed that $1 \le n, m \le 10^6$, $0 \le a_i, x \le 10^9$, and $1 \le p < n$.

Notes

• Note that $a_i, x \leq Y$ does not imply $a_i \otimes x \leq Y$.
• Note the impact of large input size on program efficiency.
• The special output format in this problem is only to avoid TLE due to overly large output, and is unrelated to the solution.
• Note the impact of constant factors on program efficiency.
• This problem provides two sample files; see dream.zip in the additional files.

Translated by ChatGPT 5