Balls and Pockets

There is a strip with an infinite number of cells. Cells are numbered starting with 0. Initially the cell i contains a ball with the number i.

There are n pockets located at cells a_1, …, a_n. Each cell contains at most one pocket.

Filtering is the following sequence of operations:

• All pockets at cells a_1, …, a_n open simultaneously, which makes balls currently located at those cells disappear. After the balls disappear, the pockets close again.
• For each cell i from 0 to ∞, if the cell i contains a ball, we move that ball to the free cell j with the lowest number. If there is no free cell j < i, the ball stays at the cell i.

Note that after each filtering operation each cell will still contain exactly one ball.

For example, let the cells 1, 3 and 4 contain pockets. The initial configuration of balls is shown below (underscores display the cells with pockets):

0 1 2 3 4 5 6 7 8 9 ...

After opening and closing the pockets, balls 1, 3 and 4 disappear:

0 2 5 6 7 8 9 ...

After moving all the balls to the left, the configuration looks like this:

0 2 5 6 7 8 9 10 11 12 ...

Another filtering repetition results in the following:

0 5 8 9 10 11 12 13 14 15 ...

You have to answer m questions. The i-th of these questions is "what is the number of the ball located at the cell x_i after k_i repetitions of the filtering operation?"

Input

The first line contains two integers n and m — the number of pockets and questions respectively (1 ≤ n, m ≤ 10^5).

The following line contains n integers a_1, …, a_n — the numbers of cells containing pockets (0 ≤ a_1 < … < a_n ≤ 10^9).

The following m lines describe questions. The i-th of these lines contains two integers x_i and k_i (0 ≤ x_i, k_i ≤ 10^9).

Output

Print m numbers — answers to the questions, in the same order as given in the input.

Example

Input

3 15 1 3 4 0 0 1 0 2 0 3 0 4 0 0 1 1 1 2 1 3 1 4 1 0 2 1 2 2 2 3 2 4 2

Output

0 1 2 3 4 0 2 5 6 7 0 5 8 9 10

inputFormat

Input

The first line contains two integers n and m — the number of pockets and questions respectively (1 ≤ n, m ≤ 10^5).

The following line contains n integers a_1, …, a_n — the numbers of cells containing pockets (0 ≤ a_1 < … < a_n ≤ 10^9).

The following m lines describe questions. The i-th of these lines contains two integers x_i and k_i (0 ≤ x_i, k_i ≤ 10^9).

outputFormat

Output

Print m numbers — answers to the questions, in the same order as given in the input.

Example

Input

3 15 1 3 4 0 0 1 0 2 0 3 0 4 0 0 1 1 1 2 1 3 1 4 1 0 2 1 2 2 2 3 2 4 2

Output

0 1 2 3 4 0 2 5 6 7 0 5 8 9 10

样例

3 15
1 3 4
0 0
1 0
2 0
3 0
4 0
0 1
1 1
2 1
3 1
4 1
0 2
1 2
2 2
3 2
4 2

0
1
2
3
4
0
2
5
6
7
0
5
8
9
10

</p>