Die Kapokbäume im alten Garten wachsen noch immer in 小 Ns allmählich verblassenden Erinnerungen. Ihre Erinnerung an den Garten lässt sich durch eine Folge $[a_0,a_1,\ldots,a_{n-1}]$ der Länge $n$ darstellen.

Jeder Kapokbaum im alten Garten hat die Form eines ungewurzelten Baums mit beschrifteten Knoten. 小 Ns Eindruck eines Kapokbaums lässt sich durch ein Intervall $[l,r)$ ihrer Gartenerinnerung beschreiben:

• Der Baum hat $k=r-l+2$ Knoten mit den Nummern $0\sim k-1$.
• $[\min(a_l,k-1),\min(a_{l+1},k-1),\ldots,\min(a_{r-1},k-1)]$ ist der Prüfer-Code dieses Baums. Die genaue Definition des Prüfer-Codes steht im Abschnitt „Hinweis“.

Während sie sich erinnert, stellt 小 N dir auch $m$ Anfragen. Die $i$-te Anfrage ($0\le i<m$) lautet:

• Sind im Kapokbaum, der dem Intervall $[l_i,r_i)$ der Gartenerinnerung entspricht, die Knoten $x_i,y_i$ benachbart?

Implementierungsdetails

Du musst und sollst keine Funktion main implementieren.

Stelle sicher, dass deine eingereichte Quelldatei den Header kapok.h einbindet, indem du am Anfang den folgenden Code einfügst:

#include "kapok.h"

Implementiere in deiner eingereichten Quelldatei kapok.cpp die folgende Funktion:

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$ geben die Testfallnummer, die Länge der Gartenerinnerungsfolge und die Anzahl der Anfragen an. $c=0$ bedeutet, dass es sich um ein Beispiel handelt.
• $a$ ist die Gartenerinnerungsfolge.
• $l,r$ geben die beiden Endpunkte des Intervalls jeder Anfrage an.
• $x,y$ geben die beiden Knotennummern jeder Anfrage an.
• Die Funktion muss eine Folge $f_0,f_1,\ldots,f_{m-1}$ mit genau $m$ Elementen zurückgeben. Dabei gibt $f_i$ für $0\le i<m$ das Ergebnis der $i$-ten Anfrage an.
• Für jede Testdatei ruft das Bewertungsprogramm diese Funktion genau einmal auf.

Im Aufgabenverzeichnis findest du die Beispieldatei template_kapok.cpp. Du kannst dich daran orientieren und deinen eigenen Code implementieren.

Wie du dein Programm testen kannst

Im Aufgabenverzeichnis kannst du mit dem folgenden Befehl eine ausführbare Datei kompilieren:

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

Für die kompilierte ausführbare Datei kapok gilt:

• Sie liest Daten im folgenden Format von der Standardeingabe:

  • Die erste Zeile enthält drei nichtnegative ganze Zahlen $c,n,m$.
  • Die zweite Zeile enthält $n$ nichtnegative ganze Zahlen $a_0,a_1,\ldots,a_{n-1}$.
  • Die $(i+3)$-te Zeile für $0\le i<m$ enthält vier nichtnegative ganze Zahlen $l_i,r_i,x_i,y_i$.

• Sie schreibt Daten im folgenden Format auf die Standardausgabe:

  • Die $(i+1)$-te Zeile für $0\le i<m$ enthält eine nichtnegative ganze Zahl. Dabei bedeutet $0$, dass $f_i$ gleich false ist, und $1$, dass $f_i$ gleich true ist.

Beispiele

Eingabe 1

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

Ausgabe 1

1
0
1

Hinweis zu Beispiel 1

• Der Baum zum Intervall $[0,3)$ hat $5$ Knoten, den Prüfer-Code $[2,0,2]$ und die Kantenmenge $\{(1,2),(0,3),(0,2),(2,4)\}$. Daher sind die Knoten $0,2$ benachbart.
• Der Baum zum Intervall $[3,5)$ hat $4$ Knoten, den Prüfer-Code $[3,0]$ und die Kantenmenge $\{(1,3),(0,2),(0,3)\}$. Daher sind die Knoten $1,2$ nicht benachbart.
• Der Baum zum Intervall $[0,0)$ hat $2$ Knoten und einen leeren Prüfer-Code. Seine einzige Kante ist $(0,1)$. Daher sind die Knoten $0,1$ benachbart.

Beispiel 2

Siehe kapok/kapok2.in und kapok/kapok2.ans im Teilnehmerverzeichnis.

Dieses Beispiel erfüllt die Beschränkungen der Testfälle $3\sim5$.

Beispiel 3

Siehe kapok/kapok3.in und kapok/kapok3.ans im Teilnehmerverzeichnis.

Dieses Beispiel erfüllt die Beschränkungen der Testfälle $3\sim5$.

Beschränkungen

Für alle Testdaten gilt:

• $1\le n,m\le2\times10^5$.
• Für alle $0\le i<n$ gilt $0\le a_i<n+2$.
• Für alle $0\le i<m$ gilt $0\le l_i\le r_i\le n$ und $0\le x_i,y_i<r_i-l_i+2$.

• Besondere Eigenschaft A: Für alle $0\le i<m$ wird nach Vorgabe von $l_i,r_i$ das geordnete Knotenpaar $(x_i,y_i)$ unabhängig und gleichverteilt aus allen geordneten Knotenpaaren ausgewählt, die die Beschränkungen erfüllen.

Hinweis

Für einen ungewurzelten Baum $T$ mit den Knotennummern $0\sim c-1$ und $c\ge2$ gilt:

• Führe nacheinander $c-2$ Operationen aus. Die $i$-te Operation für $0\le i<c-2$ lautet:

  • Finde das aktuelle Blatt $v_i$ mit der kleinsten Nummer.
  • Notiere die Nummer $p_i$ seines einzigen Nachbarn.
  • Entferne anschließend $v_i$ und seine einzige inzidente Kante aus $T$.

• Die so entstandene Folge $[p_0,p_1,\ldots,p_{c-3}]$ der Länge $c-2$ ist der Prüfer-Code von $T$.