数组的异或和

题目描述

对于长度均为 $M$、由非负整数组成的序列 $B=(B_1,B_2,\dots,B_M)$ 和 $C=(C_1,C_2,\dots,C_M)$,定义 $B$ 和 $C$ 的异或和 $S(B,C)$ 为长度 $M$、由非负整数组成的序列 $(B_1\oplus C_1, B_2\oplus C_2, ..., B_{M}\oplus C_{M})$。这里,$\oplus$ 表示按位异或。

例如,若 $B = (1, 2, 3)$,$C = (3, 5, 7)$,则 $S(B, C) = (1\oplus 3, 2\oplus 5, 3\oplus 7) = (2, 7, 4)$。

给定一个由非负整数组成的序列 $A = (A_1, A_2, \dots, A_N)$。用 $A(i, j)$ 表示由 $A$ 的第 $i$ 个元素到第 $j$ 个元素组成的连续子序列。

你将收到下面说明的 $Q$ 个查询,请处理完所有的查询。

每个查询给出整数 $a$、$b$、$c$、$d$、$e$、$f$,均在 $1$ 到 $N$ 之间(含端点)。这些整数满足 $a \le b$,$c \le d$,$e \le f$,且 $b-a=d-c$。若 $S(A(a, b), A(c, d))$ 按字典序严格小于 $A(e, f)$,则输出 Yes;否则输出 No。

什么是按位异或?

两个整数 $a$ 和 $b$ 的排他逻辑和 $a \oplus b$ 定义如下。

$a \oplus b$ 的二进制表示中,第 $2^k$ 位($k \ge 0$)在 $a$ 和 $b$ 的二进制表示中第 $2^k$ 位恰好有一个为 $1$ 时为 $1$,否则为 $0$。

例如,$3 \oplus 5 = 6$(二进制表示:$011 \oplus 101 = 110$)。

什么是序列的字典序?

当且仅当满足以下 1. 或 2. 之一时,称序列 $A = (A_1, \ldots, A_{|A|})$ 按字典序严格小于序列 $B = (B_1, \ldots, B_{|B|})$。

1. $|A|\lt |B|$ 且 $(A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|})$。
2. 存在整数 $1\le i\le \min\{|A|,|B|\}$,同时满足以下两者:
   • $(A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})$
   • $A_i \lt B_i$

输入格式

输入按以下格式从标准输入给出,其中 $\text{query}_i$ 表示第 $i$ 个查询:

$N$ $Q$
$A_1$ $A_2$ $\dots$ $A_N$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

查询的格式如下:

$a$ $b$ $c$ $d$ $e$ $f$

输出格式

输出 $Q$ 行。第 $i$ 行应包含第 $i$ 个查询的答案。

样例

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

No
No
Yes
No
Yes

对于第一个查询,有 $A(1, 3) = (1, 2, 3)$ 和 $A(2, 4) = (2, 3, 1)$,所以 $S(A(1,3),A(2,4)) = (1 \oplus 2, 2 \oplus 3, 3 \oplus 1) = (3, 1, 2)$。这比 $A(1, 4) = (1, 2, 3, 1)$ 按字典序更大,因此答案是 No。

对于第二个查询,有 $S(A(1,2),A(2,3)) = (3, 1)$ 和 $A(3,4) = (3, 1)$,两者相等,因此答案是 No。

10 10
725560240 9175925348 9627229768 7408031479 623321125 4845892509 8712345300 1026746010 4844359340 2169008582
5 6 5 6 2 6
5 6 1 2 1 1
3 8 3 8 1 6
5 10 1 6 1 7
3 4 1 2 5 5
7 10 4 7 2 3
3 6 1 4 7 9
4 5 3 4 8 9
2 6 1 5 5 8
4 8 1 5 1 9

Yes
Yes
Yes
Yes
No
No
No
No
No
No

数据范围

• $1 \le N \le 5 \times 10^5$
• $0 \le A_i \le 10^{18}$
• $1 \le Q \le 5 \times 10^4$
• $1 \le a \le b \le N$
• $1 \le c \le d \le N$
• $1 \le e \le f \le N$
• $b - a = d - c$
• 输入中的所有值均为整数