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;
unsigned int seed;
unsigned int getrand() {
  seed ^= seed << 13;
  seed ^= seed >> 17;
  seed ^= seed << 5;
  return seed;
}
int get() {
  char ch;
  while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-')
    ;
  if (ch == '-') {
    int s = 0;
    while (ch = getchar(), ch >= '0' && ch <= '9') s = s * 10 + ch - '0';
    return -s;
  }
  int s = ch - '0';
  while (ch = getchar(), ch >= '0' && ch <= '9') s = s * 10 + ch - '0';
  return s;
}
const int N = 1e5 + 5;
int n, m;
long long a[N], start;
long long st[N];
struct treap_node {
  unsigned int key;
  int l, r, tot;
  void init() {
    key = getrand();
    tot = 1;
    l = r = 0;
  }
} treap[N];
int rt;
void update(int now) {
  treap[now].tot = treap[treap[now].l].tot + treap[treap[now].r].tot + 1;
}
pair<int, int> split(int now, int k) {
  if (!k || !now) return make_pair(0, now);
  if (k >= treap[treap[now].l].tot + 1) {
    pair<int, int> u = split(treap[now].r, k - treap[treap[now].l].tot - 1);
    treap[now].r = u.first;
    update(now);
    return make_pair(now, u.second);
  }
  pair<int, int> u = split(treap[now].l, k);
  treap[now].l = u.second;
  update(now);
  return make_pair(u.first, now);
}
int merge(int x, int y) {
  if (!x || !y) return x | y;
  if (treap[x].key < treap[y].key) {
    treap[x].r = merge(treap[x].r, y);
    update(x);
    return x;
  }
  treap[y].l = merge(x, treap[y].l);
  update(y);
  return y;
}
struct node {
  int l, r, tot;
} tree[N * 20];
int Rt[N], tot;
int que[N], u;
void getque(int now) {
  if (!now) return;
  getque(treap[now].l);
  que[++u] = now;
  getque(treap[now].r);
}
void add(int &now, int qf, int l, int r, int x) {
  tree[now = ++tot] = tree[qf];
  tree[now].tot++;
  if (l == r) return;
  int mid = (l + r) / 2;
  if (x <= mid)
    add(tree[now].l, tree[qf].l, l, mid, x);
  else
    add(tree[now].r, tree[qf].r, mid + 1, r, x);
}
int query(int now, int l, int r, int x, int y) {
  if (x <= l && r <= y) return tree[now].tot;
  int mid = (l + r) / 2, ret = 0;
  if (x <= mid) ret = query(tree[now].l, l, mid, x, y);
  if (y > mid) ret = ret + query(tree[now].r, mid + 1, r, x, y);
  return ret;
}
long long times[N];
long long pre[N];
long long getans(int x, int k) {
  int blk = 0;
  {
    int l = 1, r = n;
    while (l <= r) {
      int mid = (l + r) / 2;
      int L = 1, R = mid, kw = 0;
      while (L <= R) {
        int M = (L + R) / 2;
        if (times[M] - times[mid + 1] >= k)
          kw = M, L = M + 1;
        else
          R = M - 1;
      }
      long long all = pre[kw] - times[mid + 1] * kw - 1ll * k * kw;
      if (all >= x)
        blk = mid, r = mid - 1;
      else
        l = mid + 1;
    }
  }
  int key = 0;
  {
    int l = 1, r = times[blk] - times[blk + 1];
    while (l <= r) {
      int mid = (l + r) / 2;
      int L = 1, R = blk, kw = 0;
      while (L <= R) {
        int M = (L + R) / 2;
        if (times[M] - times[blk] + mid >= k)
          kw = M, L = M + 1;
        else
          R = M - 1;
      }
      long long all = pre[kw] - times[blk] * kw + 1ll * mid * kw - 1ll * k * kw;
      if (all >= x)
        key = mid, r = mid - 1;
      else
        l = mid + 1;
    }
  }
  int kw = 0;
  {
    int L = 1, R = blk;
    while (L <= R) {
      int M = (L + R) / 2;
      if (times[M] - times[blk] + key - 1 >= k)
        kw = M, L = M + 1;
      else
        R = M - 1;
    }
  }
  long long all =
      pre[kw] - times[blk] * kw + 1ll * (key - 1) * kw - 1ll * k * kw;
  int ans = 0;
  {
    int l = 1, r = n;
    while (l <= r) {
      int mid = (l + r) / 2;
      if (all + query(Rt[mid], 1, n, 1, kw) >= x)
        ans = mid, r = mid - 1;
      else
        l = mid + 1;
    }
  }
  ans = query(Rt[ans], 1, n, 1, blk);
  return st[blk] - 1 + 1ll * blk * (key - 1) + ans;
}
int main() {
  seed = 74851365;
  n = get();
  m = get();
  for (int i = 1; i <= n; i++) a[i] = get();
  start = a[1];
  for (int i = 1; i <= n; i++) a[i] -= start;
  st[1] = 0;
  treap[rt = 1].init();
  for (int i = 2; i <= n; i++) {
    int w = (a[i] - st[i - 1]) % (i - 1);
    st[i] = a[i] - w;
    pair<int, int> u = split(rt, w);
    treap[i].init();
    rt = merge(merge(u.first, i), u.second);
  }
  getque(rt);
  for (int i = 1; i <= n; i++) add(Rt[i], Rt[i - 1], 1, n, que[i]);
  for (int i = 1; i <= n - 1; i++) times[i] = (st[i + 1] - st[i]) / i;
  times[n] = 1e9;
  for (int i = n; i >= 1; i--) times[i] += times[i + 1];
  for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + times[i];
  for (int cas = 1; cas <= m; cas++) {
    int x = get(), k = get();
    if (x < start) {
      printf("%d\n", x);
      continue;
    }
    x = x - start + 1;
    printf("%I64d\n", getans(x, k) + start);
  }
  return 0;
}