Los ceibos del antiguo jardín siguen creciendo en los recuerdos cada vez más borrosos de N. Sus recuerdos del jardín pueden representarse mediante una secuencia de longitud $n$, $[a_0,a_1,\ldots,a_{n-1}]$.

Cada ceibo del jardín tiene la forma de un árbol sin raíz con vértices etiquetados. La impresión que N conserva de uno de ellos se describe mediante un intervalo $[l,r)$ de sus recuerdos:

• El árbol tiene $k=r-l+2$ vértices, numerados del $0$ al $k-1$.
• Su secuencia de Prüfer es $[\min(a_l,k-1),\min(a_{l+1},k-1),\ldots,\min(a_{r-1},k-1)]$. La definición de secuencia de Prüfer se detalla en la sección «Nota».

Mientras recuerda el pasado, N te plantea $m$ consultas. La consulta $i$ ($0\leq i<m$) es:

• En el ceibo correspondiente al intervalo $[l_i,r_i)$ de sus recuerdos, ¿son adyacentes los vértices $x_i,y_i$?

Detalles de implementación

No necesitas ni debes implementar la función main.

El archivo fuente que entregues debe incluir la cabecera kapok.h. Añade al comienzo:

#include "kapok.h"

Debes implementar la siguiente función en el archivo fuente 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 indican, respectivamente, el número del punto de prueba, la longitud de la secuencia de recuerdos y el número de consultas. c = 0 indica que se trata de un ejemplo.
• a es la secuencia de recuerdos.
• l, r son los dos extremos del intervalo de cada consulta.
• x, y son los números de los dos vértices de cada consulta.
• La función debe devolver una secuencia de longitud exactamente $m$, $f_0,f_1,\ldots,f_{m-1}$, donde $f_i$ ($0\leq i<m$) es el resultado de la consulta $i$.
• Para cada punto de prueba, el evaluador llama a esta función exactamente una vez.

El archivo template_kapok.cpp del directorio del problema contiene código de ejemplo que puedes consultar para implementar tu solución.

Cómo probar tu programa

Puedes compilar un ejecutable desde el directorio del problema con esta orden:

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

El ejecutable kapok obtenido funciona así:

• Lee de la entrada estándar datos con el formato siguiente:

  • La primera línea contiene tres enteros no negativos $c,n,m$.
  • La segunda línea contiene $n$ enteros no negativos $a_0,a_1,\ldots,a_{n-1}$.
  • La línea $i+3$ ($0\leq i<m$) contiene cuatro enteros no negativos $l_i,r_i,x_i,y_i$.

• Escribe en la salida estándar datos con el formato siguiente:

  • La línea $i+1$ ($0\leq i<m$) contiene un entero no negativo: $0$ indica que $f_i$ es false y $1$ indica que es true.

Ejemplos

Entrada 1

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

Salida 1

1
0
1

Nota

• El árbol del intervalo $[0,3)$ tiene $5$ vértices, secuencia de Prüfer $[2,0,2]$ y conjunto de aristas $\{(1,2),(0,3),(0,2),(2,4)\}$; por tanto, los vértices $0,2$ son adyacentes.
• El árbol del intervalo $[3,5)$ tiene $4$ vértices, secuencia de Prüfer $[3,0]$ y conjunto de aristas $\{(1,3),(0,2),(0,3)\}$; por tanto, los vértices $1,2$ no son adyacentes.
• El árbol del intervalo $[0,0)$ tiene $2$ vértices y secuencia de Prüfer vacía. Su única arista es $(0,1)$, por lo que los vértices $0,1$ son adyacentes.

Ejemplo 2

Consulta kapok/kapok2.in y kapok/kapok2.ans en el directorio del concursante.

Este ejemplo cumple las restricciones de los puntos de prueba $3\sim5$.

Ejemplo 3

Consulta kapok/kapok3.in y kapok/kapok3.ans en el directorio del concursante.

Este ejemplo cumple las restricciones de los puntos de prueba $3\sim5$.

Restricciones

Para todos los datos de prueba:

• $1\leq n,m\leq2\times10^5$.
• Para todo $0\leq i<n$, $0\leq a_i<n+2$.
• Para todo $0\leq i<m$, $0\leq l_i\leq r_i\leq n$ y $0\leq x_i,y_i<r_i-l_i+2$.

• Propiedad especial A: para todo $0\leq i<m$, una vez fijados $l_i,r_i$, los $x_i,y_i$ se generan de forma independiente y uniformemente aleatoria entre todos los pares ordenados de vértices que cumplen las restricciones.

Nota

Para un árbol sin raíz $T$ cuyos vértices están numerados del $0$ al $c-1$, con $c\geq2$:

• Realiza $c-2$ operaciones consecutivas. La operación $i$ ($0\leq i<c-2$) consiste en:

  • Encontrar la hoja $v_i$ con el menor número actual.
  • Registrar el número $p_i$ de su único vecino.
  • Eliminar de $T$ el vértice $v_i$ y su única arista incidente.

• La secuencia resultante $[p_0,p_1,\ldots,p_{c-3}]$, de longitud $c-2$, es la secuencia de Prüfer de $T$.