You are given a positive integer and a sequence of positive integers, such that .
The sequence parameterizes a tree with vertices, consisting of levels with vertices, in the following way:
The tree parameterized by .
The -th level contains vertices . The vertex has two children, and the rest of the vertices on the level have one child each.
We want to answer queries of the form "what is the largest common ancestor of and ", i.e. the vertex with the largest label which is an ancestor of both and .
Input
The first line contains integers and , 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 integers which parameterize the tree.
The -th of the following lines contains two integers and which will be used to determine the labels of vertices in the queries.
Let be the answer to the -th query, and let . The labels in the -th query and are:
where mod is the remainder of integer division.
Remark: Note that if , it holds and , so all queries are known from input. If , the queries are not known in advance, but are determined using answers to previous queries.
Output
Output lines. In the -th line, output the largest common ancestor of and .
Scoring
Subtask | Score | Constraints |
---|---|---|
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:
,
,
,
,
.
Comments