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

*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 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:

## Comments