A1385 | [COCI-2020-2021-contest3]#4 Specijacija

You are given a positive integer n and a sequence a1, a2, . . . , an of positive integers, such that i(i−1) 2 < ai ≤ i(i+1) The sequence parameterizes a tree with (n+1)(n+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+1) 2 . The vertex ai 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

The first line contains integers n, q and t (1 ≤ n, q ≤ 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 ai (
i(i−1)2 < ai ≤i(i+1) 2 ) which parameterize the tree.
The i-th of the following q lines contains two integers xei and yei (1 ≤ xei , yei ≤ (n+1)(n+2) 2 ) which will be used to determine the labels of vertices in the queries.
Let zi be the answer to the i-th query, and let z0 = 0. The labels in the i-th query xi and yi are: xi = (xei − 1 + t · zi−1) mod (n+1)(n+2) 2 + 1,
yi = (yei − 1 + t · zi−1) mod (n+1)(n+2) 2 + 1,
where mod is the remainder of integer divison.
Remark: Note that if t = 0, it holds xi = xei and yi = yei , 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 xi and yi.