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 mod = 1e9 + 7;
struct fastio {
  char s[100000];
  int it, len;
  fastio() { it = len = 0; }
  inline char get() {
    if (it < len) return s[it++];
    it = 0;
    len = fread(s, 1, 100000, stdin);
    if (len == 0)
      return EOF;
    else
      return s[it++];
  }
  bool notend() {
    char c = get();
    while (c == ' ' || c == '\n') c = get();
    if (it > 0) it--;
    return c != EOF;
  }
} _buff;
inline long long getnum() {
  long long r = 0;
  bool ng = 0;
  char c;
  c = _buff.get();
  while (c != '-' && (c < '0' || c > '9')) c = _buff.get();
  if (c == '-') ng = 1, c = _buff.get();
  while (c >= '0' && c <= '9') r = r * 10 + c - '0', c = _buff.get();
  return ng ? -r : r;
}
template <class T>
inline void putnum(T x) {
  if (x < 0) putchar('-'), x = -x;
  register short a[20] = {}, sz = 0;
  while (x) a[sz++] = x % 10, x /= 10;
  if (sz == 0) putchar('0');
  for (int i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
}
inline char getreal() {
  char c = _buff.get();
  while (c <= 32) c = _buff.get();
  return c;
}
long long qpow(long long x, long long k) {
  return k == 0 ? 1
                : 1ll * qpow(1ll * x * x % mod, k >> 1) * (k & 1 ? x : 1) % mod;
}
const int maxn = 100111;
struct BIT {
  int a[maxn];
  void add(int x, int v) {
    for (int i = x; i < maxn; i += i & (-i)) a[i] += v;
  }
  int querykth(int k) {
    assert(k > 0);
    k--;
    int x = 0, sum = 0;
    for (int i = 19; i >= 0; i--) {
      if (x + (1 << i) < maxn && sum + (1 << i) - a[x + (1 << i)] <= k) {
        x += 1 << i;
        sum += (1 << i) - a[x];
      }
    }
    return x + 1;
  }
} BIT;
struct SGT {
  struct node {
    int tl, tr, v;
  } a[maxn * 4 * 20];
  int tot;
  int newnode(int q) {
    int p = ++tot;
    a[p].tl = a[q].tl;
    a[p].tr = a[q].tr;
    a[p].v = a[q].v;
    return p;
  }
  int modify(int x, int v, int l, int r, int q) {
    int p = newnode(q);
    a[p].v += v;
    if (l == r) return p;
    int m = l + r >> 1;
    if (x <= m)
      a[p].tl = modify(x, v, l, m, a[q].tl);
    else
      a[p].tr = modify(x, v, m + 1, r, a[q].tr);
    return p;
  }
  int K;
  int querykth(int l, int r, int qr, int ql) {
    int cur = (r - l + 1) - (a[qr].v - a[ql].v) - (l == 0);
    if (cur <= K) {
      K -= cur;
      return r + 1;
    }
    if (l == r) return l;
    int m = l + r >> 1;
    int ret = querykth(l, m, a[qr].tl, a[ql].tl);
    if (ret == m + 1) ret = querykth(m + 1, r, a[qr].tr, a[ql].tr);
    return ret;
  }
  int query(int x, int y, int l, int r, int p) {
    if (x <= l && r <= y) return a[p].v;
    int m = l + r >> 1, ret = 0;
    if (x <= m) ret += query(x, y, l, m, a[p].tl);
    if (m < y) ret += query(x, y, m + 1, r, a[p].tr);
    return ret;
  }
} sgt;
int n, m, sz;
long long a[maxn];
int b[maxn], rt[maxn];
struct seg {
  long long p, d, cnt;
  seg(long long P = 0, long long D = 0, long long CNT = 0) {
    p = P;
    d = D;
    cnt = CNT;
  }
};
vector<seg> V;
long long pt[maxn], scnt[maxn], pid[maxn];
long long queryid(long long p) {
  int i = upper_bound(pt, pt + sz, p) - pt - 1;
  assert(i >= 0 && i < sz);
  return scnt[i] + (p - V[i].p) / V[i].d;
}
pair<int, long long> queryloc(long long p) {
  int i = upper_bound(pt, pt + sz, p) - pt - 1;
  assert(i >= 0 && i < sz);
  return make_pair(i, (p - V[i].p) % V[i].d);
}
pair<long long, long long> queryseg(long long id) {
  int i = upper_bound(scnt, scnt + sz, id) - scnt - 1;
  assert(i >= 0 && i < sz);
  long long l = V[i].p + (id - scnt[i]) * V[i].d;
  return make_pair(l, l + V[i].d);
}
void prework() {
  long long p = 1e15;
  for (int i = n; i >= 1; i--) {
    if (p >= a[i]) {
      long long cnt = (p - a[i]) / i + 1;
      V.push_back(seg(p - cnt * i, i, cnt));
      p -= cnt * i;
    }
  }
  reverse(V.begin(), V.end());
  sz = V.size();
  for (int i = 0; i < sz; i++) pt[i] = V[i].p;
  for (int i = 1; i <= sz; i++) scnt[i] = scnt[i - 1] + V[i - 1].cnt;
  for (int i = n; i >= 1; i--) {
    pair<int, long long> loc = queryloc(a[i] - 1);
    loc.second++;
    b[i] = BIT.querykth(loc.second);
    BIT.add(b[i], 1);
    pid[i] = scnt[loc.first];
  }
  for (int i = 1; i <= n; i++) rt[i] = sgt.modify(b[i], 1, 0, n, rt[i - 1]);
}
long long query(long long x, long long k) {
  if (x < pt[0] || k == 0)
    return x;
  else {
    pair<int, long long> xl = queryloc(x);
    pair<long long, long long> s = queryseg(queryid(x) + k);
    int ld = V[xl.first].d;
    int rd = s.second - s.first;
    if (ld == rd) return xl.second + s.first;
    sgt.K = xl.second;
    int pos = sgt.querykth(0, n, rt[n], rt[ld]);
    pos -= sgt.query(1, pos, 0, n, rt[n]) - sgt.query(1, pos, 0, n, rt[rd]);
    return pos - 1 + s.first;
  }
}
int main() {
  n = getnum(), m = getnum();
  for (int i = 1; i <= n; i++) a[i] = getnum(), a[i]++;
  prework();
  for (int i = 1; i <= m; i++) {
    long long x, k;
    x = getnum(), k = getnum();
    putnum(query(x, k)), putchar('\n');
  }
  return 0;
}