众所周知，法老胡夫（Khufu）是一位伟大的统治者，但许多人不知道他也是一位时尚爱好者。在过去，他拥有 $N$ 座金字塔，编号为 $0$ 到 $N - 1$，其中金字塔 $i$（$0 \le i < N$）由 $A[i]$ 块石头组成。他还拥有当年最时尚的金字塔的最新目录。该目录包含 $N$ 座金字塔，编号为 $0$ 到 $N - 1$，其中金字塔 $i$（$0 \le i < N$）由 $B[i]$ 块石头组成。

对于任意满足 $0 \le x \le y < N$ 的 $x$ 和 $y$，我们定义金字塔区间 $A[x..y]$ 为序列 $A[x], A[x + 1], \dots, A[y]$。类似地，我们也定义金字塔区间 $B[x..y]$。

每天，胡夫都会浏览目录并选择两个金字塔区间 $A[L..R]$ 和 $B[X..Y]$，其中 $R - L = Y - X$（$L, R, X$ 和 $Y$ 的值每天可能不同）。之后，他想知道是否可以通过变换使他的区间 $A[L..R]$ 变得与目录中的区间 $B[X..Y]$ 完全相同。对一个区间进行变换是指执行以下步骤任意次数：从该区间内的一座金字塔中取出一块石头，并将其移动到该区间内相邻的金字塔中。

你的任务是回答多个如下形式的问题：给定四个整数 $L, R, X$ 和 $Y$，确定是否可以将 $A[L..R]$ 变换为 $B[X..Y]$。请注意，每座金字塔中实际的石头数量永远不会真正改变，胡夫只是想知道一个区间是否可以被变换为另一个区间。

实现细节

你需要实现以下函数：

void init(std::vector<int> A, std::vector<int> B)

• $A, B$：两个长度为 $N$ 的数组，分别描述胡夫的金字塔和目录中金字塔的石头数量。
• 该函数在任何对 can_transform 的调用之前被恰好调用一次。

bool can_transform(int L, int R, int X, int Y)

• $L, R$：胡夫金字塔区间的起始和结束下标。
• $X, Y$：目录金字塔区间的起始和结束下标。
• 如果可以将 $A[L..R]$ 变换为 $B[X..Y]$，该函数应返回 true，否则返回 false。
• 该函数被恰好调用 $Q$ 次，每天一次。

样例

考虑以下调用：

init([1, 2, 3, 4, 5], [2, 2, 2, 4, 5])

假设评测程序随后调用 can_transform(0, 2, 0, 2)。该调用应返回金字塔序列 $A[0..2] = [1, 2, 3]$ 是否可以变换为 $B[0..2] = [2, 2, 2]$。这确实是可能的，方法是将区间中最后一座金字塔的一块石头移动到第一座金字塔。因此，此调用应返回 true。

假设评测程序随后调用 can_transform(3, 4, 3, 4)。该调用应返回我们是否可以将胡夫的金字塔 $A[3..4] = [4, 5]$ 变换为 $B[3..4] = [4, 5]$。这些金字塔已经完全相同。因此，此调用应返回 true。

假设评测程序随后调用 can_transform(0, 2, 1, 3)。该调用应返回金字塔序列 $A[0..2] = [1, 2, 3]$ 是否可以变换为 $B[1..3] = [2, 2, 4]$。这是不可能的，因此此调用应返回 false。

数据范围

• $1 \le N \le 100\,000$
• $1 \le Q \le 100\,000$
• $1 \le A[i] \le 10^9$
• $1 \le B[i] \le 10^9$

在每次对 can_transform 的调用中：

• $0 \le L \le R < N$
• $0 \le X \le Y < N$
• $R - L = Y - X$

子任务

示例评测程序

输入格式

N Q
A[0] A[1] ... A[N-1]
B[0] B[1] ... B[N-1]
L[0] R[0] X[0] Y[0]
L[1] R[1] X[1] Y[1]
...
L[Q-1] R[Q-1] X[Q-1] Y[Q-1]

这里，$L[i], R[i], X[i]$ 和 $Y[i]$ 分别表示第 $i$ 次调用 can_transform 时 $L, R, X$ 和 $Y$ 的值。

输出格式

P[0]
P[1]
...
P[Q-1]

这里，如果第 $i$ 次调用 can_transform 返回 true，则 $P[i]$ 为 $1$，否则为 $0$。