Beberapa pohon kapuk di kampung halaman masih tumbuh dalam ingatan Xiao N yang perlahan memudar. Ingatan Xiao N tentang kampung halamannya dapat dinyatakan dengan sebuah barisan $[a_0,a_1,\ldots,a_{n-1}]$ sepanjang $n$.

Setiap pohon kapuk di kampung halaman berbentuk pohon tak berakar dengan simpul berlabel. Kesan Xiao N tentang sebuah pohon kapuk dapat dideskripsikan dengan sebuah interval $[l,r)$ dari ingatan tentang kampung halamannya:

• Jumlah simpul pohon ini adalah $k=r-l+2$, dengan nomor simpul $0\sim k-1$;
• $[\min(a_l,k-1),\min(a_{l+1},k-1),\ldots,\min(a_{r-1},k-1)]$ adalah barisan Prüfer pohon ini. Definisi barisan Prüfer dijelaskan dalam bagian Petunjuk.

Saat mengenang masa lalu, Xiao N juga mengajukan $m$ pertanyaan kepadamu. Pertanyaan ke-$i$ ($0\le i<m$) adalah:

• Pada pohon kapuk yang bersesuaian dengan interval $[l_i,r_i)$ dalam ingatan tentang kampung halaman, apakah simpul $x_i,y_i$ bertetangga?

Detail Implementasi

Peserta tidak perlu dan tidak boleh mengimplementasikan fungsi main.

Peserta harus memastikan bahwa berkas kode sumber yang dikumpulkan menyertakan berkas header kapok.h, yaitu menambahkan kode berikut pada awal program:

#include "kapok.h"

Peserta harus mengimplementasikan fungsi berikut dalam berkas kode sumber kapok.cpp yang dikumpulkan:

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$ masing-masing menyatakan nomor kasus uji, panjang barisan ingatan tentang kampung halaman, dan jumlah pertanyaan. $c=0$ berarti kasus uji tersebut merupakan contoh.
• $a$ menyatakan barisan ingatan tentang kampung halaman.
• $l,r$ masing-masing menyatakan kedua ujung interval yang diberikan pada setiap pertanyaan.
• $x,y$ masing-masing menyatakan nomor kedua simpul yang diberikan pada setiap pertanyaan.
• Fungsi ini harus mengembalikan sebuah barisan $f_0,f_1,\ldots,f_{m-1}$ yang panjangnya tepat $m$, dengan $f_i$ ($0\le i<m$) menyatakan hasil pertanyaan ke-$i$.
• Untuk setiap kasus uji, fungsi ini akan dipanggil tepat satu kali oleh program penilai.

Berkas template_kapok.cpp dalam direktori soal ini merupakan kode contoh yang disediakan. Peserta dapat menggunakannya sebagai acuan untuk mengimplementasikan kode sendiri.

Cara Menguji Program

Peserta dapat menggunakan perintah berikut dalam direktori soal ini untuk mengompilasi program menjadi berkas yang dapat dijalankan:

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

Untuk berkas kapok yang dihasilkan:

• Program akan membaca data dari masukan standar dengan format berikut:
  • Baris pertama memuat tiga bilangan bulat nonnegatif $c,n,m$.
  • Baris kedua memuat $n$ bilangan bulat nonnegatif $a_0,a_1,\ldots,a_{n-1}$.
  • Baris ke-$(i+3)$ ($0\le i<m$) memuat empat bilangan bulat nonnegatif $l_i,r_i,x_i,y_i$.
• Program akan menulis data ke keluaran standar dengan format berikut:
  • Baris ke-$(i+1)$ ($0\le i<m$) memuat sebuah bilangan bulat nonnegatif, dengan $0$ menyatakan bahwa $f_i$ adalah false, dan $1$ menyatakan bahwa $f_i$ adalah true.

Contoh

Masukan 1

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

Keluaran 1

1
0
1

Penjelasan

• Pohon yang bersesuaian dengan interval $[0,3)$ memiliki $5$ simpul, barisan Prüfer $[2,0,2]$, dan himpunan sisi $\{(1,2),(0,3),(0,2),(2,4)\}$. Karena itu, simpul $0,2$ bertetangga.
• Pohon yang bersesuaian dengan interval $[3,5)$ memiliki $4$ simpul, barisan Prüfer $[3,0]$, dan himpunan sisi $\{(1,3),(0,2),(0,3)\}$. Karena itu, simpul $1,2$ tidak bertetangga.
• Pohon yang bersesuaian dengan interval $[0,0)$ memiliki $2$ simpul, barisan Prüfer kosong, dan satu-satunya sisi $(0,1)$. Karena itu, simpul $0,1$ bertetangga.

Contoh 2

Lihat kapok/kapok2.in dan kapok/kapok2.ans dalam direktori peserta.

Contoh ini memenuhi batasan kasus uji $3\sim5$.

Contoh 3

Lihat kapok/kapok3.in dan kapok/kapok3.ans dalam direktori peserta.

Contoh ini memenuhi batasan kasus uji $3\sim5$.

Batasan

Untuk semua data uji, berlaku:

• $1\le n,m\le2\times10^5$;
• Untuk semua $0\le i<n$, berlaku $0\le a_i<n+2$;
• Untuk semua $0\le i<m$, berlaku $0\le l_i\le r_i\le n$ dan $0\le x_i,y_i<r_i-l_i+2$.

• Sifat khusus A: untuk semua $0\le i<m$, setelah $l_i,r_i$ diberikan, $x_i,y_i$ dibangkitkan secara acak, independen, dan seragam dari semua pasangan simpul terurut yang memenuhi batasan.

Petunjuk

Untuk sebuah pohon tak berakar $T$ dengan simpul bernomor $0\sim c-1$ ($c\ge2$):

• Lakukan $c-2$ operasi secara berurutan. Operasi ke-$i$ ($0\le i<c-2$) adalah sebagai berikut:
  • Temukan daun $v_i$ dengan nomor terkecil saat ini;
  • Catat nomor $p_i$ dari satu-satunya simpul yang bertetangga dengannya;
  • Kemudian hapus $v_i$ beserta satu-satunya sisi yang bersisian dengannya dari $T$.
• Barisan $[p_0,p_1,\ldots,p_{c-3}]$ sepanjang $c-2$ yang diperoleh dengan cara ini adalah barisan Prüfer dari $T$.