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 = 100005;
int t[N], n;
void change(int x, int v) {
  for (; x <= n; x += x & (-x)) t[x] += v;
}
int ask(int x) {
  int ans = 0;
  for (; x; x -= x & (-x)) ans += t[x];
  return ans;
}
int erase(int x) {
  int l = 1, r = n, ans = n + 1;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (ask(mid) > x)
      ans = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  change(ans, -1);
  return ans - 1;
}
int T[N], ed[N];
long long sum[N];
pair<long long, long long> check(int p, int k, int x) {
  x += T[p] - k;
  int id = upper_bound(T, T + n, x) - T;
  return pair<long long, long long>(1ll * x * id - sum[id], id);
}
int Qblock(int x, int k) {
  int l = 1, r = n - 1, ans = 0;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (check(mid, k, 0).first <= x)
      ans = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  return ans;
}
int Qat(int x, int k, int be) {
  int l = 1, r = T[be + 1] - T[be], ans = 0;
  if (be == n - 1) r = x / n + k + 1;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (check(be, k, mid).first <= x)
      ans = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  return ans;
}
const int M = 3000005;
int nd, sz[M], ls[M], rs[M], rt[N];
void change(int &nk, int k, int l, int r, int p) {
  nk = ++nd;
  sz[nk] = sz[k] + 1;
  ls[nk] = ls[k];
  rs[nk] = rs[k];
  if (l == r) return;
  int mid = (l + r) / 2;
  if (p <= mid)
    change(ls[nk], ls[k], l, mid, p);
  else
    change(rs[nk], rs[k], mid + 1, r, p);
}
int findkth(int k, int l, int r, int rk) {
  if (l == r) return l;
  int mid = (l + r) / 2;
  if (rk < sz[ls[k]]) return findkth(ls[k], l, mid, rk);
  return findkth(rs[k], mid + 1, r, rk - sz[ls[k]]);
}
int asksum(int k, int l, int r, int p) {
  if (r == p || !k) return sz[k];
  int mid = (l + r) / 2;
  if (p <= mid) return asksum(ls[k], l, mid, p);
  return asksum(rs[k], mid + 1, r, p) + sz[ls[k]];
}
int Q, a[N], id[N];
int main() {
  scanf("%d%d", &n, &Q);
  for (int i = (int)(0); i <= (int)(n - 1); i++) scanf("%d", &a[i]);
  int st = a[0];
  for (int i = (int)(0); i <= (int)(n - 1); i++) a[i] -= st;
  for (int i = (int)(1); i <= (int)(n - 1); i++) {
    T[i] = T[i - 1] + (a[i] - ed[i - 1]) / i;
    ed[i] = ed[i - 1] + (a[i] - ed[i - 1]) / i * i;
    sum[i + 1] = sum[i] + T[i];
  }
  for (int i = (int)(1); i <= (int)(n); i++) change(i, 1);
  for (int i = (int)(n - 1); i >= (int)(0); i--) id[i] = erase(a[i] - ed[i]);
  for (int i = (int)(0); i <= (int)(n - 1); i++)
    change(rt[i + 1], rt[i], 0, n - 1, id[i]);
  while (Q--) {
    int x, k;
    scanf("%d%d", &x, &k);
    if (x < st) {
      printf("%d\n", x);
      continue;
    }
    x -= st;
    int be = Qblock(x, k);
    int at = Qat(x, k, be);
    pair<long long, long long> res = check(be, k, at);
    int rest = x - res.first, pre = res.second;
    int rank = findkth(rt[pre], 0, n - 1, rest);
    int count = (rank ? asksum(rt[be + 1], 0, n - 1, rank - 1) : 0);
    printf("%lld\n", st + ed[be] + 1ll * at * (be + 1) + count);
  }
}