Specialization

You are given a positive integer $n$ and a sequence $a_1, a_2, \dots, a_n$ of positive integers, such that $\frac{i(i-1)}{2} < a_i \le \frac{i(i+1)}{2}$.

The sequence defines a tree with $\frac{(n+1)(n+2)}{2}$ vertices. The tree has $n+1$ levels with $1, 2, \dots, n+1$ vertices each.

The tree defined by $a = (1, 2, 6)$.

The $i$-th level contains vertices $\frac{i(i-1)}{2} + 1, \dots, \frac{i(i+1)}{2}$. Vertex $a_i$ has two children. Every other vertex on that level has one child.

You must answer $q$ queries. Each query asks for the largest common ancestor of $x$ and $y$, that is, the ancestor of both with the largest label.

The first line contains three integers $n$, $q$, and $t$ ($1 \le n, q \le 200\,000$, $t \in \{0, 1\}$). They are the number of parameters, the number of queries, and a value used to compute the query labels.

The second line contains $n$ integers $a_i$ ($\frac{i(i-1)}{2} \le a_i \le \frac{i(i+1)}{2}$) that define the tree.

The next $q$ lines each contain two integers $\tilde{x}_i$ and $\tilde{y}_i$ ($1 \le \tilde{x}_i, \tilde{y}_i \le \frac{(n+1)(n+2)}{2}$). The query labels are computed as follows.

$x_i = \left(\left(\tilde{x}_i - 1 + t \cdot z_{i-1}\right) \bmod \frac{(n+1)(n+2)}{2}\right) + 1$

$y_i = \left(\left(\tilde{y}_i - 1 + t \cdot z_{i-1}\right) \bmod \frac{(n+1)(n+2)}{2}\right) + 1$

Here $z_i$ is the answer to the $i$-th query, and $z_0 = 0$. The mod operator is the remainder of integer division.

If $t = 0$, then $x_i = \tilde{x}_i$ and $y_i = \tilde{y}_i$, so every query is known from the input. If $t = 1$, each query depends on the previous answer, so the queries cannot be known in advance.

Print $q$ lines. The $i$-th line contains the largest common ancestor of $x_i$ and $y_i$.

The figure shows the tree defined by $a = (1, 2, 6)$.