P17144 [NOI 2026] Kapok

The statement and sample attachments come from [QOJ](https://qoj.ac/contest/3939/problem/18987)。 When submitting to Luogu, there is no need to include the header `#include "kapok.h"`。Just copy ```cpp std::vector kapok( int c, int n, int m, std::vector a, std::vector l, std::vector r, std::vector x, std::vector y ); ``` to the beginning of your program, and compile with a C++17 or higher compiler.

Those kapok trees in the old home are still growing in Little $N$'s gradually blurred memories. Little $N$'s memories of the old home can be represented by a sequence of length $n$, $[a_0,a_1,\ldots,a_{n-1}]$。 Each kapok tree in the old home is an unrooted tree with labeled nodes. Little $N$'s impression of a kapok tree can be described by an interval $[l,r)$ of her old-home memory: - This tree has $k=r-l+2$ nodes, with node labels $0\sim k-1$。 - $[\min(a_l,k-1),\min(a_{l+1},k-1),\ldots,\min(a_{r-1},k-1)]$ is the Prüfer sequence of this tree, where the definition of Prüfer sequence is given in the [Hint] section. While recalling the past, Little $N$ also asked you $m$ queries. The $i$-th query ($0\le i

### Test Program Method Contestants can compile an executable in this problem directory using the following command: ```bash g++ grader.cpp kapok.cpp -o kapok -O2 -std=c++14 -static ``` For the compiled executable `kapok`: - The executable will read input from standard input in the following format: - The first line contains three non-negative integers $c,n,m$。 - The second line contains $n$ non-negative integers $a_0,a_1,\ldots,a_{n-1}$。 - The $(i+3)$-th line ($0\le i

# Hint ### Sample $1$ Explanation - The tree corresponding to interval $[0,3)$ has $5$ nodes, and its Prüfer sequence is $[2,0,2]$. The edge set is $\{(1,2),(0,3),(0,2),(2,4)\}$. Therefore, nodes $0,2$ are adjacent. - The tree corresponding to interval $[3,5)$ has $4$ nodes, and its Prüfer sequence is $[3,0]$. The edge set is $\{(1,3),(0,2),(0,3)\}$. Therefore, nodes $1,2$ are not adjacent. - The tree corresponding to interval $[0,0)$ has $2$ nodes, and its Prüfer sequence is empty. The only edge is $(0,1)$. Therefore, nodes $0,1$ are adjacent. ### Sample $2$ See `kapok/kapok2.in` and `kapok/kapok2.ans` in the contestants' directory. This sample satisfies the constraints of test points $3\sim5$。 ### Sample $3$ See `kapok/kapok3.in` and `kapok/kapok3.ans` in the contestants' directory. This sample satisfies the constraints of test points $3\sim5$。 ### Constraints For all testdata: - $1\le n,m\le2\times10^5$。 - For all $0\le i

### Sample $1$ Explanation - The tree corresponding to interval $[0,3)$ has $5$ nodes, and its Prüfer sequence is $[2,0,2]$. The edge set is $\{(1,2),(0,3),(0,2),(2,4)\}$. Therefore, nodes $0,2$ are adjacent. - The tree corresponding to interval $[3,5)$ has $4$ nodes, and its Prüfer sequence is $[3,0]$. The edge set is $\{(1,3),(0,2),(0,3)\}$. Therefore, nodes $1,2$ are not adjacent. - The tree corresponding to interval $[0,0)$ has $2$ nodes, and its Prüfer sequence is empty. The only edge is $(0,1)$. Therefore, nodes $0,1$ are adjacent. ### Sample $2$ See `kapok/kapok2.in` and `kapok/kapok2.ans` in the contestants' directory. This sample satisfies the constraints of test points $3\sim5$。 ### Sample $3$ See `kapok/kapok3.in` and `kapok/kapok3.ans` in the contestants' directory. This sample satisfies the constraints of test points $3\sim5$。 ### Constraints For all testdata: - $1\le n,m\le2\times10^5$。 - For all $0\le i