Youngwoo 有两个长度为 $N$ 的整数数组 $A$ 和 $B$。对于所有整数 $i$，均满足 $A[i] \le B[i]$。

若一个区间满足以下所有条件，则称其为一个美好的区间：

• $l, r$ 为整数；
• $0 \le l \le r \le N - 1$；
• 可以通过对数组 $[A[l], \dots, A[r]]$ 重复进行如下操作，使其变为 $[B[l], \dots, B[r]]$。
  • 设当前数组为 $X = [X[0], X[1], \dots, X[r-l]]$；
  • 选择两个不同的整数 $i, j$，满足 $0 \le i, j \le r-l$ 且 $X[i] = X[j]$，并将 $X[i]$ 增加 $1$。

Youngwoo 想知道哪些区间是美好的区间。

具体来说，Youngwoo 有编号从 $0$ 到 $Q-1$ 的 $Q$ 个询问，由长度为 $Q$ 的数组 $L$ 和 $R$ 表示。

第 $j$ 个询问询问区间 $[L[j], R[j]]$ 是否为美好的区间。（$0 \le j \le Q-1$）

你需要编写程序回答 Youngwoo 的所有询问。

实现细节

你需要实现如下函数：

vector<int> array_operation(vector<int> A, vector<int> B, vector<int> L, vector<int> R)

• $A, B$：大小为 $N$ 的整数数组。
• $L, R$：大小为 $Q$ 的整数数组。

该函数应返回一个大小为 $Q$ 的整数数组 $S$。对于每个 $j$（$0 \le j \le Q-1$）：

• 若区间 $[L[j], R[j]]$ 是美好的区间，则 $S[j] = 1$；
• 否则 $S[j] = 0$。

该函数只会被调用一次。

提交的源代码中不得在任何部分执行输入输出函数。

限制

• $1 \le N, Q \le 250,000$
• 对于所有 $i$，$1 \le A[i] \le B[i] \le 10^9$（$0 \le i \le N-1$）
• 对于所有 $j$，$0 \le L[j] \le R[j] \le N-1$（$0 \le j \le Q-1$）

子任务

1. $9$ 分：$N, Q \le 100$，$B[i] \le 100$（$0 \le i \le N-1$）
2. $7$ 分：$N, Q \le 2000$，$A[i] = 1$（$0 \le i \le N-1$）
3. $16$ 分：$A[i] = 1$（$0 \le i \le N-1$）
4. $10$ 分：$N, Q \le 2000$
5. $4$ 分：$B[i] \le 2$（$0 \le i \le N-1$）
6. $13$ 分：$B[i] \le 100$（$0 \le i \le N-1$）
7. $31$ 分：$B[i] \le 250000$（$0 \le i \le N-1$）
8. $10$ 分：无额外限制。

样例数据

样例 1

考虑如下调用：

array_operation([2, 1, 1, 2], [2, 1, 3, 3], [0, 0, 1], [1, 3, 3])

• $[0, 1]$ 是美好的区间，因为两个数组 $[A[0], A[1]]$ 和 $[B[0], B[1]]$ 相同。
• $[0, 3]$ 是美好的区间，因为可以通过如下操作将 $[2,1,1,2]$ 变为 $[2,1,3,3]$：
  • 选择 $i = 3, j = 0$，执行操作后数组变为 $[2,1,1,3]$。
  • 选择 $i = 2, j = 1$，执行操作后数组变为 $[2,1,2,3]$。
  • 选择 $i = 2, j = 0$，执行操作后数组变为 $[2,1,3,3]$。
• $[1, 3]$ 不是美好的区间。可以证明无论如何操作，都无法将 $[1,1,2]$ 变为 $[1,3,3]$。

因此，函数应返回 $[1,1,0]$。

样例 2

考虑如下调用：

array_operation([1, 2, 1, 2, 1], [2, 3, 1, 4, 2], [0, 0, 1, 1, 2], [2, 4, 3, 4, 3])

在所有区间中，美好的区间为：

$[0,2]$, $[0,3]$, $[0,4]$, $[1,4]$, $[2,2]$。

因此，函数应返回 $[1,1,0,1,0]$。

Sample Grader

样例评测器的输入格式如下：

• 第 1 行：$N\ Q$
• 接下来对于所有 $i$（$0 \le i \le N-1$）：
  • 第 $2 + i$ 行：$A[i]\ B[i]$
• 接下来对于所有 $i$（$0 \le i \le Q-1$）：
  • 第 $2 + N + i$ 行：$L[i]\ R[i]$

样例评测器按照如下格式输出答案：

• 第 1 行：array_operation 的返回值