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$. Sequentially, for $i$ from $l$ to $r$, update $v$ by applying the transformation $v = |v - a_i|$. Find the final value of $v$.

Input

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

The second line contains $n$ space-separated integers representing the sequence $a$.

The following $m$ lines each contain three space-separated integers $l, r, v$ representing a query.

This problem is online. All input values $l, r, v$ must be XORed with the answer to the previous query. If there is no previous query, use $0$.

Output

For each query, output a single integer representing the answer on a new line.

Examples

Input 1

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

Output 1

1
4
4
5
1

Note

Explanation of the example:

In the first query, $3$ undergoes transformations by values $2, 5, 3$ sequentially, becoming $1, 4, 1$. The answer is $1$.

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

In the second query, $1$ undergoes transformation by value $5$, becoming $4$. The answer is $4$.

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

In the third query, $2$ undergoes transformations by values $4, 5, 2, 5$ sequentially, becoming $2, 3, 1, 4$. The answer is $4$.

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

In the fourth query, $1$ undergoes transformations by values $4, 5, 2, 5$ sequentially, becoming $3, 2, 0, 5$. The answer is $5$.

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

In the fifth query, $1$ undergoes transformations by values $2, 5, 3$ sequentially, becoming $1, 4, 1$. The answer is $1$.

Constraints

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