問題文

長さ $N$ の整数列 $A_1, A_2, \\ldots, A_N$ があります。以下の $Q$ 個のクエリを順番に処理してください。

• 値が $L_i$ 以上 $R_i$ 以下である要素をすべて選び、それらの排他的論理和を答える。その後、選んだ要素をすべて $X_i$ に更新する。 ただし、$L_i$ 以上 $R_i$ 以下の整数が $1$ つも存在しない場合の答えは $0$ とする。

排他的論理和とは

整数 $c_1, c_2, ..., c_n$ の排他的論理和 $X$ は、以下のように定義されます。

• $X$ を二進数表記したときの $2^k$ ($k \\ge 0$) の位の値は、$c_1, c_2, ..., c_n$ のうち、二進数表記したときの $2^k$ の位の値が $1$ となるものが奇数個ならば $1$、偶数個ならば $0$ である。

例えば、$3$ と $5$ の排他的論理和は $6$ です(二進数表記すると: 011 と 101 の排他的論理和は 110 です)。

制約

• $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$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

$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$

出力

$Q$ 行出力してください。 $i$ $(1\\le i\\le Q)$ 行目には $i$ 番目のクエリに対する答えを出力してください。

入力例 1

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

出力例 1

14
1

• $1$ つめのクエリでは、$7$ 以上 $10$ 以下の整数は $7$ と $9$ の $2$ つなのでこれらの排他的論理和の $14$ を出力します。 その後この $2$ つを $2$ に更新して、数列は $\\{2,4,1,5,2\\}$ になります。
• $2$ つめのクエリでは、$2$ 以上 $8$ 以下の整数は $2, 4, 5, 2$ の $4$ つなのでこれらの排他的論理和の$1$ を出力します。 その後この $4$ つを $5$ に更新して、数列は $\\{5,5,1,5,5\\}$ になります。

入力例 2

1 1
5
1 3 2

出力例 2

0

条件をみたす $A_i$ が存在しない場合の答えは $0$ です。このときは更新も行われません。

入力例 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

出力例 3

13
6
97
30
2
24
0
79
0
3