问题描述

给定一个长度为 $N$ 的整数序列 $A_1, A_2, \\ldots, A_N$。请按顺序处理以下 $Q$ 个查询。

• 从序列中选择值大于等于 $L_i$ 且小于等于 $R_i$ 的元素，并计算它们的异或值作为答案。然后将选定的元素全部更新为 $X_i$。如果不存在大于等于 $L_i$ 且小于等于 $R_i$ 的整数，则答案为 $0$。

异或值定义如下：

整数 $c_1, c_2, ..., c_n$ 的异或值 $X$ 可以通过以下方式计算：

• 将 $X$ 表示为二进制形式，若 $c_1, c_2, ..., c_n$ 在二进制表示中的第 $2^k$ ($k \\ge 0$) 位有奇数个 $1$，则 $X$ 的二进制表示的第 $2^k$ 位为 $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

• 在第一个查询中，大于等于 $7$ 且小于等于 $10$ 的整数有 $7$ 和 $9$，它们的异或值为 $14$。然后将这两个元素更新为 $2$，序列变为 $\\{2,4,1,5,2\\}$。
• 在第二个查询中，大于等于 $2$ 且小于等于 $8$ 的整数有 $2, 4, 5, 2$，它们的异或值为 $1$。然后将这四个元素更新为 $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