题目描述

译自 COCI 2020/2021 Contest #3 T5. Specijacija

给定一个长度为 $n$ 的正整数序列 $a_{1 \ldots n}$ ，满足 $\frac{i(i-1)}{2} < a_i \le \frac{i(i+1)}{2}$ 。

通过这一个序列构造一个有 $\frac{(n+1)(n+2)}{2}$ 个节点的二叉树。该二叉树有 $n+1$ 层，第 $i$ 层有 $i$ 个节点。

第 $i$ 层包含编号为 $\frac{i(i-1)}{2} + 1, \ldots,\frac{i(i+1)}{2}$ 的节点。节点 $a_i$ 有两个儿子，而同一层的其他节点则只有一个儿子。

比如，序列 $\{1,2,6\}$ 所构造的树就是这样的。

有 $q$ 组询问，给定 $x, y$ ，你需要求出节点 $x, y$ 的最近公共祖先。

输入格式

第一行包含三个整数 $n,q,t$ ，分别表示序列的长度、询问次数和关于强制在线的参数。

第二行有 $n$ 个正整数，第 $i$ 个数为 $a_i$ 。

接下来的 $q$ 行中每一行有两个正整数 $\tilde{x_i}, \tilde{y_i}$ ，即询问的参数 $x_i, y_i$ 加密后的结果。

其中：

$$\begin{array}{l} 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 \end{array} $$

$z_i$ 为第 $i$ 组询问的答案，如果 $i = 0$ ，则置 $z_i$ 为 $0$ 。

注意到当 $t = 0$ 时 $x_i = \tilde{x_i}$ 而 $y_i = \tilde{y_i}$ 。

输出格式

输出共 $q$ 行，其中第 $i$ 行一个正整数，表示 $x_i, y_i$ 的最近公共祖先。

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

数据范围与提示

对于所有子任务，保证 $1 \le n,q \le 2 \times 10^5, t \in \{0,1\}$ 。

详细子任务附加限制与分值如下表：

子任务	附加限制	分值
$1$	$q = 1, t = 0$	$10/110$
$2$	$n \le 1000, t = 0$	$10/110$
$3$	$t = 0$	$30/110$
$4$	$t = 1$	$60/110$