给你一个正整数 $n$ 和一个由正整数组成的序列 $a_1, a_2, \dots, a_n$，满足 $\frac{i(i-1)}{2} < a_i \le \frac{i(i+1)}{2}$。

该序列通过以下方式参数化了一棵拥有 $\frac{(n+1)(n+2)}{2}$ 个节点的树，该树由 $n + 1$ 层组成，各层分别包含 $1, 2, \dots, n + 1$ 个节点：

由 $a = (1, 2, 6)$ 参数化的树。

第 $i$ 层包含节点 $\frac{i(i-1)}{2} + 1, \dots, \frac{i(i+1)}{2}$。节点 $a_i$ 有两个子节点，而该层上的其余节点各有一个子节点。

我们需要回答 $q$ 次询问，每次询问的形式为“$x$ 和 $y$ 的最大公共祖先是什么”，即编号最大且同时是 $x$ 和 $y$ 祖先的节点。

输入格式

第一行包含三个整数 $n, q$ 和 $t$（$1 \le n, q \le 200\,000$，$t \in \{0, 1\}$），分别表示参数的数量、询问的数量，以及一个用于确定询问中节点编号的值。

第二行包含一个由 $n$ 个整数组成的序列 $a_i$（$\frac{i(i-1)}{2} < a_i \le \frac{i(i+1)}{2}$），用于参数化这棵树。

接下来的 $q$ 行中，第 $i$ 行包含两个整数 $\tilde{x}_i$ 和 $\tilde{y}_i$（$1 \le \tilde{x}_i, \tilde{y}_i \le \frac{(n+1)(n+2)}{2}$），用于确定询问中节点的编号。

设 $z_i$ 为第 $i$ 次询问的答案，且令 $z_0 = 0$。第 $i$ 次询问中的节点编号 $x_i$ 和 $y_i$ 为：

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

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

其中 $\bmod$ 表示整数除法的余数。

备注：注意，如果 $t = 0$，则有 $x_i = \tilde{x}_i$ 且 $y_i = \tilde{y}_i$，因此所有询问在输入中都是已知的。如果 $t = 1$，则询问不是提前预知的，而是需要根据之前询问的答案来确定。

输出格式

输出 $q$ 行。在第 $i$ 行中，输出 $x_i$ 和 $y_i$ 的最大公共祖先。

子任务

样例

输入样例 1

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

输出样例 1

1
5
1
6
1

输入样例 2

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

输出样例 2

1
6
2
1
1

说明

两个样例中的树均如题目描述中的插图所示。

第二个样例中每次询问的节点编号分别为：

• $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 = 4$