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 parameterizes a tree with $\frac{(n+1)(n+2)}{2}$ vertices, consisting of $n+1$ levels with $1,2,\dots ,n+1$ vertices, in the following way:

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

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

We want to answer $q$ queries of the form "what is the largest common ancestor of $x$ and $y$", i.e. the vertex with the largest label which is an ancestor of both $x$ and $y$.

Input

The first line contains integers $n,q$ and $t$ $(1\le n,q\le 200000,t\in \{0,1\})$, 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 $n$ integers $a_i$ $(\frac{i(i-1)}{2}<a_i\le \frac{i(i+1)}{2})$ which parameterize the tree.

The $i$-th of the following $q$ lines contains two integers $\widetilde{x_i}$ and $\widetilde{y_i}$ $(1\le \widetilde{x_i},\widetilde{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$ be the answer to the $i$-th query, and let $z_0=0$. The labels in the $i$-th query $x_i$ and $y_i$ are:

$${\displaystyle \begin{array}{rl}{x}_i& =((\widetilde{x_i}-1+t\cdot z_{i-1})mod\frac{(n+1)(n+2)}{2})+1,\\ y_i& =((\widetilde{y_i}-1+t\cdot z_{i-1})mod\frac{(n+1)(n+2)}{2})+1,\end{array}}$$

where mod is the remainder of integer division.

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

Output

Output $q$ lines. In the $i$-th line, output the largest common ancestor of $x_i$ and $y_i$.

Scoring

Subtask	Score	Constraints
$1$	$10$	$q=1,t=0$
$2$	$10$	$n\le 1000,t=0$
$3$	$30$	$t=0$
$4$	$60$	$t=1$

Sample Input 1

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

Sample Output 1

1
5
1
6
1

Explanation for Sample Output 1

The tree from Sample Input 1 is shown in the figure in the statement.

Sample Input 2

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

Sample Output 2

1
6
2
1
1

Explanation for Sample Output 2

The tree from Sample Input 2 is shown in the figure in the statement.

Labels of vertices 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=4$.