← 返回题目列表

AtCoder · abc223_h

H. 异或查询

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

给定的是一系列 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} is X_i.

什么是 \mathrm{XOR}?

按位 \mathrm{XOR} 整数 A 和 B, A\ \mathrm{XOR}\ B,定义如下:

  • 当 A\ \mathrm{XOR}\ B 以基数 2 书写,即 2^k的地点 (k \geq 0)是 1 如果恰好是以下之一 A 和 B is 1,和 0 否则。
例如,我们有 3\ \mathrm{XOR}\ 5 = 6 (以二为基数: 011\ \mathrm{XOR}\ 101 = 110).

约束

  • 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}
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

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} is X_i,和 No 否则。


示例输入 1

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

示例输出 1

Yes
No

在第一个查询中,您可以选择 A_1 和 A_3,其 \mathrm{XOR} is 7.

在第二个查询中,无法选择元素以使其 \mathrm{XOR} is 7.


示例输入 2

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

示例输出 2

No
No
Yes
No
Yes
No
No
No
Yes
Yes