Kilka drzew kapokowych z rodzinnego ogrodu wciąż rośnie w coraz bardziej mglistych wspomnieniach 小 N. Jej pamięć o rodzinnym ogrodzie można przedstawić jako ciąg $[a_0,a_1,\ldots,a_{n-1}]$ o długości $n$.

Każde drzewo kapokowe w ogrodzie ma postać nieukorzenionego drzewa z etykietowanymi wierzchołkami. Wrażenie 小 N o jednym takim drzewie opisuje przedział $[l,r)$ jej wspomnień:

• Drzewo ma $k=r-l+2$ wierzchołki, ponumerowane $0 \sim k-1$.
• $[\min(a_l,k-1),\min(a_{l+1},k-1),\ldots,\min(a_{r-1},k-1)]$ jest kodem Prüfera tego drzewa. Definicję kodu Prüfera podano w sekcji „Uwagi”.

Wspominając przeszłość, 小 N zadaje ci $m$ zapytań. Zapytanie $i$ ($0 \le i < m$) brzmi:

• Czy w drzewie kapokowym odpowiadającym przedziałowi wspomnień $[l_i,r_i)$ wierzchołki $x_i,y_i$ są sąsiadami?

Szczegóły implementacji

Nie musisz i nie powinieneś implementować funkcji main.

Przesyłany plik źródłowy musi zawierać nagłówek kapok.h. W tym celu na początku programu dodaj:

#include "kapok.h"

W przesyłanym pliku źródłowym kapok.cpp należy zaimplementować następującą funkcję:

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$ oznaczają odpowiednio numer testu, długość ciągu wspomnień i liczbę zapytań. $c=0$ oznacza przykład.
• $a$ oznacza ciąg wspomnień o rodzinnym ogrodzie.
• $l,r$ opisują dwa końce przedziału podanego w każdym zapytaniu.
• $x,y$ opisują numery dwóch wierzchołków podanych w każdym zapytaniu.
• Funkcja powinna zwrócić ciąg $f_0,f_1,\ldots,f_{m-1}$ o długości dokładnie $m$, w którym $f_i$ ($0 \le i < m$) oznacza wynik zapytania $i$.
• Dla każdego testu program oceniający wywoła tę funkcję dokładnie raz.

Plik template_kapok.cpp w katalogu zadania zawiera przykładowy kod, na którym możesz oprzeć swoją implementację.

Testowanie programu

W katalogu zadania możesz skompilować plik wykonywalny następującym poleceniem:

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

Dla otrzymanego pliku wykonywalnego kapok:

• Program odczytuje ze standardowego wejścia dane w następującym formacie:

  • Pierwszy wiersz zawiera trzy nieujemne liczby całkowite $c,n,m$.
  • Drugi wiersz zawiera $n$ nieujemnych liczb całkowitych $a_0,a_1,\ldots,a_{n-1}$.
  • Wiersz $i+3$ ($0 \le i < m$) zawiera cztery nieujemne liczby całkowite $l_i,r_i,x_i,y_i$.

• Program wypisuje na standardowe wyjście dane w następującym formacie:

  • Wiersz $i+1$ ($0 \le i < m$) zawiera jedną nieujemną liczbę całkowitą: $0$ oznacza, że $f_i$ jest false, a $1$, że $f_i$ jest true.

Przykład

Wejście 1

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

Wyjście 1

1
0
1

Uwagi

• Przedziałowi $[0,3)$ odpowiada drzewo o 5 wierzchołkach, kodzie Prüfera $[2,0,2]$ i zbiorze krawędzi $\{(1,2),(0,3),(0,2),(2,4)\}$. Wierzchołki $0,2$ są więc sąsiadami.
• Przedziałowi $[3,5)$ odpowiada drzewo o 4 wierzchołkach, kodzie Prüfera $[3,0]$ i zbiorze krawędzi $\{(1,3),(0,2),(0,3)\}$. Wierzchołki $1,2$ nie są więc sąsiadami.
• Przedziałowi $[0,0)$ odpowiada drzewo o 2 wierzchołkach i pustym kodzie Prüfera. Jego jedyną krawędzią jest $(0,1)$, więc wierzchołki $0,1$ są sąsiadami.

Przykład 2

Zobacz pliki kapok/kapok2.in i kapok/kapok2.ans w katalogu zawodnika.

Przykład spełnia ograniczenia testów $3 \sim 5$.

Przykład 3

Zobacz pliki kapok/kapok3.in i kapok/kapok3.ans w katalogu zawodnika.

Przykład spełnia ograniczenia testów $3 \sim 5$.

Ograniczenia

Dla wszystkich danych testowych:

• $1 \le n,m \le 2 \times 10^5$.
• Dla wszystkich $0 \le i < n$: $0 \le a_i < n+2$.
• Dla wszystkich $0 \le i < m$: $0 \le l_i \le r_i \le n$ oraz $0 \le x_i,y_i < r_i-l_i+2$.

• Właściwość szczególna A: dla każdego $0 \le i < m$, po ustaleniu $l_i,r_i$ wartości $x_i,y_i$ są generowane niezależnie i jednostajnie losowo spośród wszystkich uporządkowanych par wierzchołków spełniających ograniczenia.

Uwagi

Dla nieukorzenionego drzewa $T$ o wierzchołkach ponumerowanych $0 \sim c-1$ ($c \ge 2$):

• Wykonaj kolejno $c-2$ operacje. Operacja $i$ ($0 \le i < c-2$) wygląda następująco:

  • Znajdź obecny liść $v_i$ o najmniejszym numerze.
  • Zapisz numer $p_i$ jego jedynego sąsiada.
  • Następnie usuń z $T$ wierzchołek $v_i$ i jego jedyną incydentną krawędź.

• Otrzymany w ten sposób ciąg $[p_0,p_1,\ldots,p_{c-3}]$ o długości $c-2$ jest kodem Prüfera drzewa $T$.