故園嗰幾棵木棉，依然生長喺小 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\sim 5$ 嘅限制條件。

樣例 3

見選手目錄下嘅 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$（$c\ge 2$）嘅無根樹 $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 序列。