故园中的那几棵木棉，仍旧生长在小 $N$ 逐渐朦胧的记忆中。小 $N$ 对故园的记忆，可以用一个长度为 $n$ 的序列 $[a_0,a_1,\dots,a_{n - 1}]$ 表示。

故园中的每棵木棉，都形如一棵结点带有编号的无根树。小 $N$ 对一棵木棉的印象，可以用她的故园记忆中的一个区间 $[l,r)$ 描述：

• 这棵树的结点数为 $k = r - l + 2$，结点编号为 $0 \sim k - 1$。
• 序列 $[\min(a_l,k - 1),\min(a_{l + 1},k - 1),\dots,\min(a_{r - 1},k - 1)]$ 是这棵树的 Prüfer 序列。Prüfer 序列的定义详见提示。

在回忆往事时，小 $N$ 向你提出了 $m$ 次询问。第 $i \ (0 \le i < m)$ 次询问为：

• 在故园记忆的区间 $[l_i,r_i)$ 所对应的木棉上，结点 $x_i$ 与结点 $y_i$ 是否相邻？

实现细节

选手不需要，也不应该实现 main 函数。

选手需要确保提交的程序源文件包含头文件 kapok.h，即在程序开头加入以下代码：

#include "kapok.h"

选手需要在提交的程序源文件 kapok.cpp 中实现以下函数：

std::vector<bool> kapok(
    int c, int n, int m, std::vector<int> a, std::vector<int> l, std::vector<int> r, std::vector<int> x, std::vector<int> y
);

• $c,n,m$ 分别表示测试点编号、故园记忆序列的长度与询问次数。$c = 0$ 表示该测试点为样例。
• $a$ 是一个长度为 $n$ 的序列，表示小 $N$ 的故园记忆。
• $l,r$ 均为长度为 $m$ 的序列，其中 $l_i,r_i \ (0 \le i < m)$ 表示第 $i$ 次询问给定区间的两个端点。
• $x,y$ 均为长度为 $m$ 的序列，其中 $x_i,y_i \ (0 \le i < m)$ 表示第 $i$ 次询问给定的两个结点编号。
• 该函数需要返回一个长度恰好为 $m$ 的布尔序列 $[f_0,f_1,\dots,f_{m - 1}]$，其中 $f_i \ (0 \le i < m)$ 表示第 $i$ 次询问的答案。
• 若结点 $x_i$ 与结点 $y_i$ 相邻，则 $f_i$ 应为 true；否则，$f_i$ 应为 false。
• 对于每个测试点，该函数会被评测程序调用恰好一次。

本试题目录下的 template_kapok.cpp 是提供的示例代码，选手可参考并实现自己的代码。

测试程序方式

选手可以在本题目录下使用如下命令编译得到可执行文件：

g++ grader.cpp kapok.cpp -o kapok -O2 -std=c++14 -static

对于编译得到的可执行文件 kapok：

• 可执行文件将从标准输入读入以下格式的数据：

  • 第一行包含三个非负整数 $c,n,m$。
  • 第二行包含 $n$ 个非负整数 $a_0,a_1,\dots,a_{n - 1}$。
  • 接下来 $m$ 行，第 $i + 1 \ (0 \le i < m)$ 行包含四个非负整数 $l_i,r_i,x_i,y_i$。

• 可执行文件将输出以下格式的数据至标准输出：

  • 共输出 $m$ 行，第 $i + 1 \ (0 \le i < m)$ 行包含一个非负整数。
  • 若 $f_i$ 为 false，则输出 $0$；若 $f_i$ 为 true，则输出 $1$。

样例一

input

0 8 3
2 0 2 6 0 7 2 2
0 3 0 2
3 5 1 2
0 0 0 1

output

1
0
1

explanation

• 区间 $[0,3)$ 对应的树有 $5$ 个结点，Prüfer 序列为 $[2,0,2]$，边集为 ${(1,2),(0,3),(0,2),(2,4)}$。因此结点 $0$ 与结点 $2$ 相邻。
• 区间 $[3,5)$ 对应的树有 $4$ 个结点，Prüfer 序列为 $[3,0]$，边集为 ${(1,3),(0,2),(0,3)}$。因此结点 $1$ 与结点 $2$ 不相邻。
• 区间 $[0,0)$ 对应的树有 $2$ 个结点，Prüfer 序列为空，唯一一条边为 $(0,1)$。因此结点 $0$ 与结点 $1$ 相邻。

样例二

见下发文件 kapok/kapok2.in 与 kapok/kapok2.ans。

该样例满足测试点 $3 \sim 5$ 的约束条件。

样例三

见下发文件 kapok/kapok3.in 与 kapok/kapok3.ans。

该样例满足测试点 $3 \sim 5$ 的约束条件。

数据范围

对于所有测试数据，均有：

• $1 \le n,m \le 2 \times 10^5$；
• 对于所有 $0 \le i < n$，均有 $0 \le a_i < n + 2$；
• 对于所有 $0 \le i < m$，均有 $0 \le l_i \le r_i \le n$，且 $0 \le x_i,y_i < r_i - l_i + 2$。

特殊性质 A：对于所有 $0 \le i < m$，在给定 $l_i,r_i$ 后，$(x_i,y_i)$ 均从所有满足限制的有序点对中独立、均匀、随机生成。

提示

对于一棵结点编号为 $0 \sim c - 1$ 的无根树 $T\ (c \ge 2)$，依次执行 $c - 2$ 次操作。其中，第 $i \ (0 \le i < c - 2)$ 次操作如下：

• 找出当前编号最小的叶子 $v_i$。
• 记录其唯一相邻结点的编号 $p_i$。
• 从 $T$ 中删除结点 $v_i$ 及其唯一相邻边。

如此得到的长度为 $c - 2$ 的序列 $[p_0,p_1,\dots,p_{c - 3}]$，即为树 $T$ 的 Prüfer 序列。

时间限制：$\texttt{2s}$

空间限制：$\texttt{1GB}$