4 secon\(ds / 1\) G\(iB / 110\) points
You are given a positive integer \(n\) and a sequence \(a\)1, a2, . . . , a\(n\) of positive integers, such that ^{i}{i}}^{1)
2
<
\(a_{i}\) ≤^{i}{i}
2
.
The sequence parameterizes a tree with ^{(}{+1)(}}^{+2)
2
vertices, consisting of \(n + 1\) levels with 1, 2, . . . , \(n + 1\)
vertices, in the following way:
1
2
4
7
5
8
3
6
9
10
The tree parameterized by \(a\) = (1, 2, 6).
The \(i-th\) level contains vertices ^{i}{i}}^{1)
2
+ 1, . . . , ^{i}{i}
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\).

Subtask 1 (10 points): \(q = 1\), \(t = 0\)

Subtask 2 (10 points): \(n \le 1000\), \(t = 0\)

Subtask 3 (30 points): \(t = 0\)

Subtask 4 (60 points): \(t = 1\)

The first line contains integers \(n\), \(q\) and \(t\) (\(1 \le n\), \(q \le 200\,000\), \(t\) ∈{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@@RISE_MATH_BLOCK_0@@i\) and e\(y@@RISE_MATH_BLOCK_1@@x@@RISE_MATH_BLOCK_2@@i\) ≤^{(}{+1)(}}^{+2)
2
) which will be
used to determine the labels of vertices in the queries.
Let \(z@@RISE_MATH_BLOCK_3@@0 = 0\). The labels in the \(i-th\) query \(x@@RISE_MATH_BLOCK_4@@i\) are:
\(x_{i}\) =

(e\(x_{i} - 1 + t \cdot z_{i}\){−}) mod ^{(}{+1)(}}^{+2)
2

+ 1,
\(y_{i}\) =

(e\(y_{i} - 1 + t \cdot z_{i}\){−}) mod ^{(}{+1)(}}^{+2)
2

+ 1,
where mod is the remainder of integer divison.
Remark: Note that if \(t = 0\), it holds \(x@@RISE_MATH_BLOCK_5@@x@@RISE_MATH_BLOCK_6@@i = e@@RISE_MATH_BLOCK_7@@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 \(q\) lines. In the \(i-th\) line, output the largest common ancestor of \(x@@RISE_MATH_BLOCK_0@@i\).
4 secon\(ds / 1\) G\(iB / 110\) points

생성자가 기록되지 않았습니다.

출처 COCI 2020/2021 Contest 3