As poucas árvores de algodão-seda de sua antiga casa continuam crescendo nas lembranças cada vez mais vagas de 小N. As lembranças de 小N sobre sua antiga casa podem ser representadas por uma sequência $[a_0,a_1,\ldots,a_{n-1}]$ de comprimento $n$.

Cada árvore de algodão-seda de sua antiga casa tem a forma de uma árvore não enraizada com vértices rotulados. A impressão que 小N tem de uma dessas árvores pode ser descrita por um intervalo $[l,r)$ de suas lembranças:

• A árvore tem $k=r-l+2$ vértices, numerados de $0$ a $k-1$.
• $[\min(a_l,k-1),\min(a_{l+1},k-1),\ldots,\min(a_{r-1},k-1)]$ é o código de Prüfer da árvore. A definição do código de Prüfer encontra-se na seção de dicas.

Ao recordar o passado, 小N também faz $m$ consultas a você. A consulta $i$, com $0\le i<m$, é:

• Na árvore de algodão-seda correspondente ao intervalo $[l_i,r_i)$ das lembranças de sua antiga casa, os vértices $x_i,y_i$ são adjacentes?

Detalhes de implementação

Você não precisa e não deve implementar a função main.

O código-fonte submetido deve incluir o cabeçalho kapok.h, isto é, deve começar com o código abaixo:

#include "kapok.h"

Você deve implementar a seguinte função no arquivo-fonte kapok.cpp submetido:

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$ representam, respectivamente, o número do teste, o comprimento da sequência de lembranças da antiga casa e o número de consultas. $c=0$ indica um exemplo.
• $a$ representa a sequência de lembranças da antiga casa.
• $l,r$ representam, respectivamente, os dois extremos do intervalo fornecido em cada consulta.
• $x,y$ representam, respectivamente, os rótulos dos dois vértices fornecidos em cada consulta.
• A função deve retornar uma sequência $f_0,f_1,\ldots,f_{m-1}$ de comprimento exatamente $m$, em que $f_i$, para $0\le i<m$, representa o resultado da consulta $i$.
• Para cada teste, o avaliador chamará essa função exatamente uma vez.

O arquivo template_kapok.cpp no diretório deste problema contém um código de exemplo que você pode consultar para implementar sua solução.

Como testar o programa

Você pode usar o seguinte comando no diretório deste problema para compilar um executável:

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

Para o executável kapok gerado:

• O executável lê da entrada padrão dados no seguinte formato:

  • A primeira linha contém três inteiros não negativos $c,n,m$.
  • A segunda linha contém $n$ inteiros não negativos $a_0,a_1,\ldots,a_{n-1}$.
  • A linha $i+3$, para $0\le i<m$, contém quatro inteiros não negativos $l_i,r_i,x_i,y_i$.

• O executável escreve na saída padrão dados no seguinte formato:

  • A linha $i+1$, para $0\le i<m$, contém um inteiro não negativo: $0$ indica que $f_i$ é false, e $1$ indica que $f_i$ é true.

Exemplos

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

Saída 1

1
0
1

Explicação

• A árvore correspondente ao intervalo $[0,3)$ tem $5$ vértices, código de Prüfer $[2,0,2]$ e conjunto de arestas $\{(1,2),(0,3),(0,2),(2,4)\}$. Portanto, os vértices $0,2$ são adjacentes.
• A árvore correspondente ao intervalo $[3,5)$ tem $4$ vértices, código de Prüfer $[3,0]$ e conjunto de arestas $\{(1,3),(0,2),(0,3)\}$. Portanto, os vértices $1,2$ não são adjacentes.
• A árvore correspondente ao intervalo $[0,0)$ tem $2$ vértices, código de Prüfer vazio e uma única aresta $(0,1)$. Portanto, os vértices $0,1$ são adjacentes.

Exemplo 2

Consulte kapok/kapok2.in e kapok/kapok2.ans no diretório do competidor.

Este exemplo satisfaz as restrições dos testes $3\sim5$.

Exemplo 3

Consulte kapok/kapok3.in e kapok/kapok3.ans no diretório do competidor.

Este exemplo satisfaz as restrições dos testes $3\sim5$.

Restrições

Para todos os dados de teste:

• $1\le n,m\le2\times10^5$;
• Para todo $0\le i<n$, vale $0\le a_i<n+2$;
• Para todo $0\le i<m$, valem $0\le l_i\le r_i\le n$ e $0\le x_i,y_i<r_i-l_i+2$.

• Propriedade especial A: para todo $0\le i<m$, após fixar $l_i,r_i$, o par $x_i,y_i$ é gerado de maneira independente e uniformemente aleatória dentre todos os pares ordenados que satisfazem as restrições.

Dicas

Para uma árvore não enraizada $T$ cujos vértices são numerados de $0$ a $c-1$, com $c\ge2$:

• Execute $c-2$ operações em ordem. A operação $i$, para $0\le i<c-2$, é a seguinte:

  • Encontre a folha $v_i$ com o menor rótulo atual;
  • Registre o rótulo $p_i$ de seu único vizinho;
  • Remova de $T$ o vértice $v_i$ e sua única aresta incidente.

• A sequência $[p_0,p_1,\ldots,p_{c-3}]$ de comprimento $c-2$ assim obtida é o código de Prüfer de $T$.