重排查询

题目描述

给定两个长度为 $N$ 的正整数序列：$A=(A_1,A_2,\ldots,A_N)$ 和 $B=(B_1,B_2,\ldots,B_N)$。

接下来按顺序处理 $Q$ 个查询。第 $i$ 个查询如下所述。

给定正整数 $l_i,r_i,L_i,R_i$。如果可以重排子序列 $(A_{l_i},A_{l_i+1},\ldots,A_{r_i})$，使其与子序列 $(B_{L_i},B_{L_i+1},\ldots,B_{R_i})$ 一致，则输出 Yes；否则输出 No。

输入格式

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

$N$ $Q$
$A_1$ $A_2$ $\ldots$ $A_N$
$B_1$ $B_2$ $\ldots$ $B_N$
$l_1$ $r_1$ $L_1$ $R_1$
$l_2$ $r_2$ $L_2$ $R_2$
$\vdots$
$l_Q$ $r_Q$ $L_Q$ $R_Q$

输出格式

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

样例

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

Yes
No
No
Yes

对于第 1 个查询，可以重排 $(1,2,3)$ 使其与 $(2,3,1)$ 一致，因此输出 Yes。

对于第 2 个查询，无论如何重排 $(1,2)$ 都无法与 $(1,4,2)$ 一致，因此输出 No。

对于第 3 个查询，无论如何重排 $(1,2,3,2)$ 都无法与 $(3,1,4,2)$ 一致，因此输出 No。

对于第 4 个查询，可以重排 $(1,2,3,2,4)$ 使其与 $(2,3,1,4,2)$ 一致，因此输出 Yes。

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

Yes
Yes
No
No

数据范围

• $1 \leq N,Q \leq 2 \times 10^5$
• $1 \leq A_i,B_i \leq N$
• $1 \leq l_i \leq r_i \leq N$
• $1 \leq L_i \leq R_i \leq N$
• 所有输入值均为整数。