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 = 1e6 + 7;
bool fl[N];
map<int, int> s;
int n, q, k, lt, p[N], w[N], ft[N], gt[N], st[N], pos[N];
long long sum, vq, ans[N], v[N << 2], f[N << 2], tg[N << 2];
struct query {
  long long x, k, t, g;
} e[N];
inline int read() {
  int num = 0;
  char g = getchar();
  while (g < 48 || 57 < g) g = getchar();
  while (47 < g && g < 58)
    num = (num << 1) + (num << 3) + g - 48, g = getchar();
  return num;
}
inline void build(int l, int r, int t) {
  tg[t] = 0;
  if (l == r) {
    v[t] = l + 10000000000000000ll, f[t] = v[t], pos[l] = t, ft[t] = l;
    return;
  }
  int d = (l + r) >> 1;
  build(l, d, t << 1), build(d + 1, r, t << 1 | 1),
      v[t] = min(v[t << 1], v[t << 1 | 1]),
      f[t] = max(f[t << 1], f[t << 1 | 1]);
}
inline void addx(int l, int r, int t, int ql, int qr, long long c) {
  if (tg[t]) {
    v[t << 1] += tg[t], v[t << 1 | 1] += tg[t];
    f[t << 1] += tg[t], f[t << 1 | 1] += tg[t];
    tg[t << 1] += tg[t], tg[t << 1 | 1] += tg[t], tg[t] = 0;
  }
  if (l == ql && r == qr) {
    if (c >= 10000000000000000ll)
      f[t] = 0;
    else
      f[t] += c;
    v[t] += c, tg[t] += c;
    return;
  }
  int d = (l + r) >> 1;
  if (ql <= d) addx(l, d, t << 1, ql, min(qr, d), c);
  if (d + 1 <= qr) addx(d + 1, r, t << 1 | 1, max(d + 1, ql), qr, c);
  v[t] = min(v[t << 1], v[t << 1 | 1]);
  f[t] = max(f[t << 1], f[t << 1 | 1]);
}
inline void update(int u) { addx(1, n, 1, u, u, 100000000000000000ll); }
inline int getpos(int t, long long c) {
  if (tg[t]) {
    v[t << 1] += tg[t], v[t << 1 | 1] += tg[t];
    f[t << 1] += tg[t], f[t << 1 | 1] += tg[t];
    tg[t << 1] += tg[t], tg[t << 1 | 1] += tg[t], tg[t] = 0;
  }
  if (ft[t]) {
    if (v[t] == c) return ft[t];
    return -1;
  }
  if (v[t << 1] <= c && c <= f[t << 1])
    return getpos(t << 1, c);
  else
    return getpos(t << 1 | 1, c);
}
inline void updatex() {
  vq = min(vq, v[1]);
  while (e[lt].x >= vq && lt > 0) {
    if (p[s[e[lt].x]])
      e[lt].x = p[s[e[lt].x]], e[lt].k = sum - e[lt].k;
    else {
      int z = getpos(1, e[lt].x);
      if (z > 0)
        e[lt].x = z, e[lt].k = sum - e[lt].k;
      else {
        long long c = (e[lt].x - vq) / k, z = e[lt].x - c * k;
        while (z < vq) c--, z += k;
        while (z >= vq + k) z -= k, c++;
        e[lt].x = getpos(1, z), e[lt].k = sum - c - e[lt].k;
      }
    }
    lt--;
  }
}
inline int getpos(int l, int r, int t, int x) {
  if (tg[t]) {
    v[t << 1] += tg[t], v[t << 1 | 1] += tg[t];
    f[t << 1] += tg[t], f[t << 1 | 1] += tg[t];
    tg[t << 1] += tg[t], tg[t << 1 | 1] += tg[t], tg[t] = 0;
  }
  if (l == r) return v[t];
  int d = (l + r) >> 1;
  if (x <= d) return getpos(l, d, t << 1, x);
  return getpos(d + 1, r, t << 1 | 1, x);
}
inline void updatey() {
  while (e[lt].k <= sum && lt > 0) {
    if (e[lt].g) {
      lt--;
      continue;
    }
    if (gt[e[lt].x])
      ans[e[lt].t] = gt[e[lt].x];
    else {
      long long c = getpos(1, n, 1, e[lt].x);
      ans[e[lt].t] = c + (sum - e[lt].k) * k;
    }
    lt--;
  }
}
inline bool tmp(query a, query b) { return a.x < b.x; }
inline bool cmp(query a, query b) { return a.k > b.k; }
int main() {
  n = read(), q = read();
  for (int i = 1; i <= n; i++) w[i] = read() + 1, s[w[i]] = i;
  for (int i = 1; i <= q; i++) {
    e[i].x = read() + 1, e[i].k = read(), e[i].t = i;
    if (e[i].x < w[1]) ans[i] = e[i].x, e[i].g = 1;
  }
  sort(e + 1, e + q + 1, tmp), lt = q;
  build(1, n, 1), sum = 0, vq = v[1];
  for (int i = n; i >= 1; i--) {
    if (fl[i]) continue;
    k = i;
    long long c = v[1], t = (c - w[i]) / i, s = c - t * i;
    while (s > w[i]) s -= i, t++;
    while (s + i < w[i]) s += i, t--;
    addx(1, n, 1, 1, n, -t * i), sum += t;
    updatex();
    int j = i;
    st[0] = 0;
    while (v[1] <= w[j - 1] && j - 1 > 0) j--;
    for (int x = j; x <= i; x++)
      st[++st[0]] = getpos(1, w[x]), update(st[st[0]]), p[x] = st[st[0]];
    vq = min(vq, 1ll * w[j]);
    addx(1, n, 1, 1, n, -(j - 1)), sum++;
    for (int x = 1; x <= st[0]; x++) addx(1, n, 1, st[x], n, -1);
    updatex();
    i = j;
  }
  sort(e + 1, e + q + 1, cmp), lt = q;
  build(1, n, 1), sum = 0;
  for (int i = n; i >= 1; i--) {
    if (fl[i]) continue;
    k = i;
    long long c = v[1], t = (c - w[i]) / i, s = c - t * i;
    while (s > w[i]) s -= i, t++;
    while (s + i < w[i]) s += i, t--;
    addx(1, n, 1, 1, n, -t * i), sum += t;
    updatey();
    int j = i;
    while (v[1] <= w[j - 1] && j - 1 > 0) j--;
    st[0] = 0;
    for (int x = j; x <= i; x++)
      st[++st[0]] = getpos(1, w[x]), update(st[st[0]]), p[x] = st[st[0]];
    addx(1, n, 1, 1, n, -(j - 1)), sum++;
    for (int x = 1; x <= st[0]; x++) addx(1, n, 1, st[x], n, -1);
    i = j;
  }
  for (int i = 1; i <= q; i++) printf("%lld\n", ans[i] - 1);
}