Problem Description

Given a sequence $a$ of length $n$, each position represents a transformation $x = |x - a_i|$. For each query, you are given an interval $[l, r]$ and a value $v$. Let $i$ go from $l$ to $r$ in order, visit each element $a_i$, and update $v$ to $|v - a_i|$. Find the value of $v$ after all transformations.

Input Format

The first line contains two integers $n, m$.

The second line contains $n$ integers separated by spaces, representing the sequence $a$.

The next $m$ lines each contain three integers $l, r, v$ separated by spaces, representing a query.

This problem is forced online: all input values $l, r, v$ must be XORed with the answer of the previous query. If there was no previous query, then XOR with $0$.

Output Format

For each query, output one integer per line, representing the answer.

5 5
4 5 2 5 3
3 5 3
3 3 0
5 0 6
5 0 5
6 0 4

1
4
4
5
1

Hint

Idea: nzhtl1477, Solution: nzhtl1477&ccz181078, Code: nzhtl1477, Data: nzhtl1477&
FutaRimeWoawaSete

Sample explanation:

In the first query, $3$ is transformed in order by values $2, 5, 3$, becoming $1, 4, 1$, so the answer is $1$.

After decryption, the second query is interval $[2, 2]$ with value $1$.

In the second query, $1$ is transformed in order by value $5$, becoming $4$, so the answer is $4$.

After decryption, the third query is interval $[1, 4]$ with value $2$.

In the third query, $2$ is transformed in order by values $4, 5, 2, 5$, becoming $2, 3, 1, 4$, so the answer is $4$.

After decryption, the fourth query is interval $[1, 4]$ with value $1$.

In the fourth query, $1$ is transformed in order by values $4, 5, 2, 5$, becoming $3, 2, 0, 5$, so the answer is $5$.

After decryption, the fifth query is interval $[3, 5]$ with value $1$.

In the fifth query, $1$ is transformed in order by values $2, 5, 3$, becoming $1, 4, 1$, so the answer is $1$.

Constraints:

For $100\%$ of the testdata, $1 \le n, m, a_i, v \le 10^5$, and $1 \le l, r \le n$.

Translated by ChatGPT 5