题目描述

長さ $M$ の非負整数列 $B=(B_1,B_2,\dots,B_M),\ C=(C_1,C_2,\dots,C_M)$ に対して、$B$ と $C$ の XOR 和 $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$ の連続部分列を $A(i,\ j)$ と表します。
以下に説明するクエリが $Q$ 個与えられるので全て処理してください。

各クエリでは $1$ 以上 $N$ 以下の整数 $a,\ b,\ c,\ d,\ e,\ f$ が与えられます。これらの整数は $a\ \leq\ b,\ c\ \leq\ d,\ e\ \leq\ 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\ \geq\ 0$) の位の数は、$A,\ B$ を二進表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $1$、そうでなければ $0$ である。

例えば、$3\ \oplus\ 5\ =\ 6$ となります (二進表記すると: $011\ \oplus\ 101\ =\ 110$)。 数列の辞書順とは？数列 $A\ =\ (A_1,\ \ldots,\ A_{|A|})$ が $B\ =\ (B_1,\ \ldots,\ B_{|B|})$ より辞書順で真に小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。

1. $ |A|\ かつ\ (A_{1},\ldots,A_{|A|})\ =\ (B_1,\ldots,B_{|A|}) $ である。
2. ある整数 $1\leq\ i\leq\ \min\{|A|,|B|\}$ が存在して、下記の $2$ つがともに成り立つ。

• $(A_{1},\ldots,A_{i-1})\ =\ (B_1,\ldots,B_{i-1})$
• $A_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$ 番目のクエリへの答えを出力せよ。

题目大意

题目描述

对于两个长度为 $t$ 的非负整数序列 $x,y$，定义非负整数序列 $S(x,y)=(x_1\oplus y_1,x_2\oplus y_2,\dots,x_t\oplus y_t)$，其中 $\oplus$ 为按位异或（XOR）。

对于长度为 $k$ 的序列 $x$ 和长度为 $l$ 的序列 $y$，若 $x<y$，当且仅当满足以下条件之一：

• $k<l$ 且 $(x_1,x_2,\dots,x_k)=(y_1,y_2,\dots,y_k)$。
• 存在 $i\in[1,\min\{k,l\}]$ 使得 $(x_1,x_2,\dots,x_{i-1})=(y_1,y_2,\dots,y_{i-1})$ 且 $x_i<y_i$。

对于长度为 $t$ 的序列 $x$，定义序列 $x_{i,j}=(x_i,x_{i+1},\dots,x_j)$，其中 $1\leq i\leq j\leq t$。

给你一个长度为 $n$ 的序列 $a$，共有 $m$ 次询问，每次询问给你 $b,c,d,e,f,g$，若 $S(a_{b,c},a_{d,e})<a_{f,g}$，输出 Yes，否则输出 No。

输入格式

第一行两个整数 $n,m$，含义如题中所述。

第二行 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

接下来 $m$ 行，每行 $6$ 个整数 $b,c,d,e,f,g$，含义如题中所述。

输出格式

对于每个询问，输出一行一个字符串 Yes 或 No，表示该询问的答案。

数据范围与提示

样例一：

对于第一个询问，$a_{1,3}=(1,2,3),a_{2,4}=(2,3,1),a_{1,4}=(1,2,3,1),S(a_{1,3},a_{2,4})=(3,1,2)$。
对于第二个询问，$a_{1,2}=(1,2),a_{2,3}=(2,3),a_{3,4}=(3,1),S(a_{1,2},a_{2,3})=(3,1)$。

数据范围：

对于所有数据，$1\leq n\leq 5\times 10^5,1\leq m\leq 5\times 10^4,0\leq a_i\leq 10^{18},1\leq b\leq c\leq n,1\leq d\leq e\leq n,1\leq f\leq g\leq n$，保证 $c-b=e-d$。

Translate by Zek3L.

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

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\ \leq\ N\ \leq\ 5\ \times\ 10^5$
• $0\ \leq\ A_i\ \leq\ 10^{18}$
• $1\ \leq\ Q\ \leq\ 5\ \times\ 10^4$
• $1\ \leq\ a\ \leq\ b\ \leq\ N$
• $1\ \leq\ c\ \leq\ d\ \leq\ N$
• $1\ \leq\ e\ \leq\ f\ \leq\ N$
• $b\ -\ a\ =\ d\ -\ c$
• 入力される値はすべて整数

Sample Explanation 1

$1$ 番目のクエリについて、$ 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 になります。 $2$ 番目のクエリについて、$S(A(1,2),A(2,3))\ =\ (3,\ 1)$, $A(3,4)\ =\ (3,\ 1)$ であり両者は等しく、答えは No になります。