Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

G. Balls and Pockets

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputThere 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, \ldots, a_n$$$. Each cell contains at most one pocket.

Filtering is the following sequence of operations:

- All pockets at cells $$$a_1, \ldots, 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 $$$\infty$$$, 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):

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

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

Another filtering repetition results in the following:

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 \leq n, m \leq 10^5$$$).

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

The following $$$m$$$ lines describe questions. The $$$i$$$-th of these lines contains two integers $$$x_i$$$ and $$$k_i$$$ ($$$0 \leq x_i, k_i \leq 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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2018 02:17:23 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|