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;
const int N = 1e5 + 5;
;
typedef class Query {
 public:
  long long t, x;
  int id;
  Query() {}
  Query(long long t, long long x, int id) : t(t), x(x), id(id) {}
} Query;
typedef class Fenwick {
 public:
  int n;
  int a[N];
  void init(int n) {
    this->n = n;
    memset(a, 0, sizeof(int) * (n + 1));
  }
  void add(int idx, int val) {
    for (; idx <= n; idx += (idx & (-idx))) a[idx] += val;
  }
  int query(int k) {
    int rt = 0, sum = 0, b = 1;
    while ((b << 1) <= n) b <<= 1;
    while (b) {
      if (rt + b <= n && sum + a[rt + b] < k) {
        sum += a[rt += b];
      }
      b >>= 1;
    }
    return rt + 1;
  }
  int get_sum(int idx) {
    int rt = 0;
    for (; idx; idx -= (idx & (-idx))) rt += a[idx];
    return rt;
  }
} Fenwick;
int n, m, _m;
int a[N];
long long ans[N];
Fenwick fen;
Query q1[N], q2[N];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
  }
  sort(a + 1, a + n + 1);
  for (int i = 1, x, k; i <= m; i++) {
    scanf("%d%d", &x, &k);
    if (x < a[1]) {
      ans[i] = x;
    } else {
      q1[++_m] = Query(k, x, i);
    }
  }
  swap(m, _m);
  sort(q1 + 1, q1 + m + 1,
       [&](const Query& a, const Query& b) { return a.x < b.x; });
  long long now = 1e15, curt = 0;
  int i = n, j = m;
  fen.init(n);
  for (int k = 1; k <= n; k++) fen.add(k, 1);
  while (j) {
    long long dt = (now - a[i] + i - 1) / i;
    long long L = now - dt * i;
    while (j && q1[j].x >= L) {
      q2[j].t = curt + (now - q1[j].x + i - 1) / i - q1[j].t;
      q2[j].x = fen.query(i - (now - q1[j].x + i - 1) % i);
      q2[j].id = q1[j].id;
      j--;
    }
    now = L, curt += dt;
    while (i && a[i] >= L) {
      fen.add(fen.query(a[i] - L + 1), -1);
      i--;
    }
  }
  sort(q2 + 1, q2 + m + 1,
       [&](const Query& a, const Query& b) { return a.t < b.t; });
  fen.init(n);
  for (int k = 1; k <= n; k++) fen.add(k, 1);
  i = n, j = 0;
  now = 1e15, curt = 0;
  while (j <= m) {
    long long dt = (now - a[i] + i - 1) / i;
    long long L = now - dt * i;
    while (j <= m && q2[j].t <= curt + dt) {
      ans[q2[j].id] = now + fen.get_sum(q2[j].x) - 1 - (q2[j].t - curt) * i;
      j++;
    }
    now = L, curt += dt;
    while (i && a[i] >= L) {
      fen.add(fen.query(a[i] - L + 1), -1);
      i--;
    }
  }
  swap(m, _m);
  for (int i = 1; i <= m; i++) {
    printf("%lld\n", ans[i]);
  }
  return 0;
}