Кілька капокових дерев із рідного саду досі ростуть у спогадах 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)]$ — послідовність Прюфера цього дерева. Її означення наведено в розділі «Примітки».

Згадуючи минуле, 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$ — 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 вершинами, послідовністю Прюфера $[2,0,2]$ та множиною ребер $\{(1,2),(0,3),(0,2),(2,4)\}$. Отже, вершини $0,2$ суміжні.
• Відрізку $[3,5)$ відповідає дерево з 4 вершинами, послідовністю Прюфера $[3,0]$ та множиною ребер $\{(1,3),(0,2),(0,3)\}$. Отже, вершини $1,2$ не суміжні.
• Відрізку $[0,0)$ відповідає дерево з 2 вершинами й порожньою послідовністю Прюфера. Єдине ребро — $(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$ і є послідовністю Прюфера дерева $T$.