故郷の庭にあった数本のキワタは、薄れていく小 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$ を含みます。
  • 2 行目は $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 列です。