故園中的那幾棵木棉，仍舊生長在小 N 逐漸朦朧的記憶中。小 N 對故園的記憶，可以用一個長度為 $n$ 的序列 $[a_0,a_1,\ldots,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),\ldots,\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$ 表示故園記憶序列。
• $l,r$ 分別表示每次詢問所給定的區間的兩個端點。
• $x,y$ 分別表示每次詢問所給定的兩個結點的編號。
• 該函數需要返回一個長度恰好為 $m$ 的序列 $f_0,f_1,\ldots,f_{m-1}$，其中 $f_i$（$0\le i<m$）表示第 $i$ 次詢問的結果。
• 對於每個測試點，該函數會被評測程式呼叫恰好一次。

本試題目錄下的 template_kapok.cpp 是提供的範例程式碼，選手可參考並實作自己的程式碼。

測試程式方式

選手可以在本題目錄下使用如下命令編譯得到可執行檔：

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

對於編譯得到的可執行檔 kapok：

• 可執行檔將從標準輸入讀入以下格式的資料：

  • 第一行包含三個非負整數 $c,n,m$。
  • 第二行包含 $n$ 個非負整數 $a_0,a_1,\ldots,a_{n-1}$。
  • 第 $i+3$（$0\le i<m$）行包含四個非負整數 $l_i,r_i,x_i,y_i$。

• 可執行檔將輸出以下格式的資料至標準輸出：

  • 第 $i+1$（$0\le i<m$）行包含一個非負整數，其中 $0$ 表示 $f_i$ 為 false，$1$ 表示 $f_i$ 為 true。

範例

輸入格式 1

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

輸出格式 1

1
0
1

說明

• 區間 $[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$ 相鄰。

範例 2

見選手目錄下的 kapok/kapok2.in 與 kapok/kapok2.ans。

該範例滿足測試點 $3\sim5$ 的約束條件。

範例 3

見選手目錄下的 kapok/kapok3.in 與 kapok/kapok3.ans。

該範例滿足測試點 $3\sim5$ 的約束條件。

資料範圍

對於所有測試資料，均有：

• $1\le n,m\le2\times10^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$（$c\ge2$）的無根樹 $T$：

• 依次執行 $c-2$ 次操作，其中第 $i$（$0\le i<c-2$）次操作如下：

  • 找出當前編號最小的葉子 $v_i$；
  • 記錄其唯一相鄰點的編號 $p_i$；
  • 然後從 $T$ 中刪去 $v_i$ 及其唯一鄰邊。

• 如此得到的長度為 $c-2$ 的序列 $[p_0,p_1,\ldots,p_{c-3}]$，即為 $T$ 的 Prüfer 序列。