COCI '20 Contest 3 #5 Specijacija

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 4.0s
Memory limit: 1G

Problem types

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 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 divison.

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 on 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 on the figure in the statement.

Labels of verticies 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.


Comments

There are no comments at the moment.