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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int T, n, m, t = 0, a[100010];
long long ans[100010];
struct ask {
  long long k, x;
  int id;
} q[100010];
int tr[100010];
void add(int x, int c) {
  for (; x <= n; x += (x & -x)) tr[x] += c;
}
int qry(int x) {
  int res = 0;
  for (; x; x -= (x & -x)) res += tr[x];
  return res;
}
int rnk(int v) {
  int nw = 0;
  for (int j = 16; j >= 0; j--)
    if (nw + (1 << j) <= n && tr[nw + (1 << j)] < v) {
      nw += (1 << j), v -= tr[nw];
    }
  return nw + 1;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1, x, k; i <= m; i++) {
    scanf("%d%d", &x, &k);
    if (x < a[1])
      ans[i] = x;
    else
      q[++t] = (ask){k, x, i};
  }
  sort(q + 1, q + t + 1, [&](ask a, ask b) { return a.x < b.x; });
  for (int i = 1; i <= n; i++) add(i, 1);
  long long nw = 1e15, nwt = 0;
  for (int i = n, j = t; i;) {
    long long d = (nw - a[i] + i - 1) / i, nxt = nw - d * i;
    while (j && q[j].x >= nxt) {
      q[j].k = nwt + (nw - q[j].x + i - 1) / i - q[j].k;
      q[j].x = rnk(i - (nw - q[j].x + i - 1) % i);
      j--;
    }
    nw = nxt, nwt += d;
    while (i && a[i] >= nw) add(rnk(a[i] - nw + 1), -1), i--;
  }
  sort(q + 1, q + t + 1, [&](ask a, ask b) { return a.k < b.k; });
  for (int i = 1; i <= n; i++) add(i, 1);
  nw = 1e15, nwt = 0;
  for (int i = n, j = 1; i;) {
    long long d = (nw - a[i] + i - 1) / i, nxt = nw - d * i;
    while (j <= t && q[j].k <= nwt + d) {
      ans[q[j].id] = nw + qry(q[j].x) - 1 - (q[j].k - nwt) * i;
      j++;
    }
    nw = nxt, nwt += d;
    while (i && a[i] >= nw) add(rnk(a[i] - nw + 1), -1), i--;
  }
  for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
}