Те несколько хлопковых деревьев из родного сада всё ещё растут в постепенно туманящихся воспоминаниях 小 N. Её воспоминания о родном саде можно представить последовательностью $[a_0,a_1,\ldots,a_{n-1}]$ длины $n$.

Каждое хлопковое дерево в родном саду имеет форму неукоренённого дерева с помеченными вершинами. Впечатление 小 N об одном из них описывается отрезком $[l,r)$ её воспоминаний:

• В дереве $k=r-l+2$ вершины, пронумерованные от $0$ до $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$) имеет следующий вид:

• Смежны ли вершины $x_i,y_i$ в хлопковом дереве, соответствующем отрезку воспоминаний $[l_i,r_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$ — номера двух вершин, заданных в каждом запросе.
• Функция должна вернуть последовательность $f_0,f_1,\ldots,f_{m-1}$ длины ровно $m$, где $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$.
  • Вторая строка содержит $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\sim5$.

Пример 3

См. файлы kapok/kapok3.in и kapok/kapok3.ans в каталоге участника.

Этот пример удовлетворяет ограничениям тестов $3\sim5$.

Ограничения

Для всех наборов данных:

• $1\le n,m\le2\times10^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$ генерируются независимо и равномерно случайно из всех допустимых упорядоченных пар вершин.

Примечание

Для неукоренённого дерева $T$ с вершинами, пронумерованными от $0$ до $c-1$ ($c\ge2$):

• Последовательно выполните $c-2$ операции. Операция $i$ ($0\le i<c-2$) состоит в следующем:
  • Найдите лист $v_i$ с наименьшим на данный момент номером.
  • Запишите номер $p_i$ его единственного соседа.
  • Удалите из $T$ вершину $v_i$ и её единственное ребро.
• Полученная последовательность $[p_0,p_1,\ldots,p_{c-3}]$ длины $c-2$ является кодом Prüfer дерева $T$.