异或查询

题目描述

给定一个由 $N$ 个正整数构成的序列 $A = (A_1, \dots, A_N)$。

处理 $Q$ 个查询。在第 $i$ 个查询 $(1 \leq i \leq Q)$ 中，判断是否可以从 $A_{L_i}, A_{L_i + 1}, \dots, A_{R_i}$ 中选择一个或多个元素，使它们的 $\mathrm{XOR}$ 等于 $X_i$。

什么是 $\mathrm{XOR}$？

整数 $A$ 和 $B$ 的按位异或 $A\ \mathrm{XOR}\ B$ 定义如下：

当用二进制表示 $A\ \mathrm{XOR}\ B$ 时，$2^k$ 位（$k \geq 0$）上的数字在 $A$ 和 $B$ 中恰好一个为 $1$ 时为 $1$，否则为 $0$。

例如，有 $3\ \mathrm{XOR}\ 5 = 6$（二进制下 $011\ \mathrm{XOR}\ 101 = 110$）。

输入格式

输入按以下格式从标准输入给出：

$N$ $Q$
$A_1$ $\ldots$ $A_N$
$L_1$ $R_1$ $X_1$
$\vdots$
$L_Q$ $R_Q$ $X_Q$

输出格式

输出 $Q$ 行。第 $i$ 行 $(1 \leq i \leq Q)$ 包含 Yes（如果可以从 $A_{L_i}, A_{L_i + 1}, \dots, A_{R_i}$ 中选择一个或多个元素使它们的 $\mathrm{XOR}$ 等于 $X_i$），否则输出 No。

样例

5 2
3 1 4 1 5
1 3 7
2 5 7

Yes
No

第一个查询中，可以选择 $A_1$ 和 $A_3$，它们的 $\mathrm{XOR}$ 为 $7$。

第二个查询中，无法选择元素使它们的 $\mathrm{XOR}$ 为 $7$。

10 10
8 45 56 9 38 28 33 5 15 19
10 10 53
3 8 60
1 10 29
5 7 62
3 7 51
8 8 52
1 4 60
6 8 32
4 8 58
5 9 2

No
No
Yes
No
Yes
No
No
No
Yes
Yes

数据范围

• $1 \leq N \leq 4 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq A_i \lt 2^{60}$
• $1 \leq L_i \leq R_i \leq N$
• $1 \leq X_i \lt 2^{60}$
• 输入中的所有数值均为整数。