Specijacija

문제

You are given a positive integer $nn$ and a sequence $a_1,a_2,\dots ,a_{n}a\_1,\; a\_2,\; \backslash dots\; ,\; a\_n$ of positive integers, such that \frac{i(i&minus;1)}{2} < a_i \le \frac{i(i+1)}{2}.

The sequence parameterizes a tree with $\frac{(n+1)(n+2)}{2}\backslash frac\{(n+1)(n+2)\}\{2\}$ vertices, consisting of $n+1n\; +\; 1$ levels with $1,2,\dots ,n+11,\; 2,\; \backslash dots\; ,\; n\; +\; 1$ vertices, in the following way:

The tree parameterized by $a=(1,2,6)a\; =\; (1,\; 2,\; 6)$.

The $ii$-th level contains vertices \frac{i(i&minus;1)}{2} + 1, \dots , \frac{i(i+1)}{2}. The vertex $a_{i}a\_i$ has two children, and the rest of the vertices on the level have one child each.

We want to answer $qq$ queries of the form “what is the largest common ancestor of $xx$ and $yy$”, i.e. the vertex with the largest label which is an ancestor of both $xx$ and $yy$.

입력

The first line contains integers $nn$, $qq$ and $tt$ ($1\le n,q\le 200000,t\in \{0,1\}1\; \backslash le\; n,\; q\; \backslash le\; 200\; 000,\; t\; \backslash in\; \backslash \{0,\; 1\backslash \}$), the number of parameters, the number of queries, and a value which will be used to determine the labels of vertices in the queries.

The second line contains a sequence of $nn$ integers $a_{i}a\_i$ (\frac{i(i&minus;1)}{2} \le a_i \le \frac{i(i+1)}{2}) which parameterize the tree.

The $ii$-th of the following $qq$ lines contains two integers ${\tilde{x}}_i\backslash tilde\{x\}\_i$ and ${\tilde{y}}_i\backslash tilde\{y\}\_i$ (1 &le; \tilde{x}_i, \tilde{y}_i &le; \frac{(n+1)(n+2)}{2}) which will be used to determine the labels of vertices in the queries.

Let $z_{i}z\_i$ be the answer to the $ii$-th query, and let $z_0=0z\_0\; =\; 0$. The labels in the $ii$-th query $x_{i}x\_i$ and $y_{i}y\_i$ are:

$x_i=\left(({\tilde{x}}_i-1+t\cdot z_{i-1})\mathrm{m}\mathrm{o}\mathrm{d}\frac{(n+1)(n+2)}{2}\right)+1\text{,}x\_i\; =\; \backslash left(\backslash left(\backslash tilde\{x\}\_i\; -\; 1\; +\; t\; \backslash cdot\; z\_\{i-1\}\backslash right)\; \backslash mod\; \backslash frac\{(n+1)(n+2)\}\{2\}\backslash right)\; +\; 1\; \backslash text\{,\}$

$y_i=\left(({\tilde{y}}_i-1+t\cdot z_{i-1})\mathrm{m}\mathrm{o}\mathrm{d}\frac{(n+1)(n+2)}{2}\right)+1\text{,}y\_i\; =\; \backslash left(\backslash left(\backslash tilde\{y\}\_i\; -\; 1\; +\; t\; \backslash cdot\; z\_\{i-1\}\backslash right)\; \backslash mod\; \backslash frac\{(n+1)(n+2)\}\{2\}\backslash right)\; +\; 1\; \backslash text\{,\}$

where $\text{mod}\backslash text\{mod\}$ is the remainder of integer divison.

Remark: Note that if $t=0t\; =\; 0$, it holds $x_i={\tilde{x}}_{i}x\_i\; =\; \backslash tilde\{x\}\_i$ and $y_i={\tilde{y}}_{i}y\_i\; =\; \backslash tilde\{y\}\_i$, so all queries are known from input. If $t=1t\; =\; 1$, the queries are not known in advance, but are determined using answers to previous queries.

출력

Output $qq$ lines. In the $ii$-th line, output the largest common ancestor of $x_{i}x\_i$ and $y_{i}y\_i$.

힌트

Clarification of the examples: The tree from both examples is shown on the figure in the statement. Labels of verticies in queries in the second example are: $x_1=7,y_1=10,x_2=9,y_2=6,x_3=2,y_3=8,x_4=1,y_4=2,x_5=3,y_5=4x\_1\; =\; 7,\; y\_1\; =\; 10,\; \backslash \backslash \; x\_2\; =\; 9,\; y\_2\; =\; 6,\backslash \backslash \; x\_3\; =\; 2,\; y\_3\; =\; 8,\backslash \backslash \; x\_4\; =\; 1,\; y\_4\; =\; 2,\backslash \backslash \; x\_5\; =\; 3,\; y\_5\; =\; 4$.

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

1
5
1
6
1

3 5 1
1 2 6
7 10
8 5
6 2
9 10
2 3

1
6
2
1
1