Problem Description

You are given an integer sequence of length $ N $: $A_1,\ A_2,\ \ldots,\ A_N$. Process the following $ Q $ queries in order.

• Select all elements whose values are between $ L_i $ and $ R_i $ (inclusive), and answer their exclusive OR. Then, update all selected elements to $ X_i $. If there are no integers between $ L_i $ and $ R_i $, the answer is $ 0 $.

Definition of Exclusive OR

The exclusive OR of integers $c_1,\ c_2,\ ...,\ c_n$, denoted as $ X $, is defined as follows:

• When $ X $ is written in binary, the value of the $ 2^k $ ($k\ \ge\ 0$) digit is $ 1 $ if there are an odd number of integers among $c_1,\ c_2,\ ...,\ c_n$ whose binary representation has $ 1 $ at the $ 2^k $ digit, and $ 0 $ if there are an even number.

For example, the exclusive OR of $ 3 $ and $ 5 $ is $ 6 $ (in binary: the exclusive OR of 011 and 101 is 110).

Input Format

The input is given from the standard input in the following format:

$N\ Q$ $A_1\ A_2\ \ldots\ A_N$ $L_1\ R_1\ X_1$ $L_2\ R_2\ X_2$ $\vdots$ $L_Q\ R_Q\ X_Q$

Output Format

Output $ Q $ lines. The $ i $ $(1\le\ i\le\ Q)$ line should contain the answer for the $ i $th query.

Sample Input and Output

Sample Input #1

5 2
7 4 1 5 9
7 10 2
2 8 5

Sample Output #1

14
1

Sample Input #2

1 1
5
1 3 2

Sample Output #2

0

Sample Input #3

15 10
76 87 42 60 30 58 52 82 42 13 81 8 97 5 87
4 11 92
56 60 68
90 100 24
30 35 15
12 17 53
24 32 31
0 6 85
74 82 55
69 72 30
50 61 49

Sample Output #3

13
6
97
30
2
24
0
79
0
3

Notes/Hints

Constraints

• $1\le\ N\le\ 3\times\ 10^5$
• $1\le\ Q\le\ 2\times\ 10^5$
• $0\le\ A_i\le\ 10^9$
• $0\le\ L_i\le\ R_i\le\ 10^9$
• $0\le\ X_i\le\ 10^9$
• All inputs are integers

Sample Explanation 1

• In the first query, the integers between $ 7 $ and $ 10 $ are $ 7 $ and $ 9 $. Their exclusive OR is $ 14 $, which is output. Then, these two are updated to $ 2 $, resulting in the sequence $\{2,4,1,5,2\}$.
• In the second query, the integers between $ 2 $ and $ 8 $ are $2,\ 4,\ 5,\ 2$. Their exclusive OR is $ 1 $, which is output. Then, these four are updated to $ 5 $, resulting in the sequence $\{5,5,1,5,5\}$.

见题面 Input 部分

见题面 Output 部分