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 200\,000, 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 ~\tilde{x_i}~ and ~\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~ 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{align*} 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, \end{align*}$$

where mod is the remainder of integer division.

Remark: Note that if ~t = 0~, it holds ~x_i = \tilde{x_i}~ and ~y_i = \tilde{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~.