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;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 100000;
const int MAXQ = 100000;
int n, nq;
int x[MAXN];
int qx[MAXQ], qt[MAXQ];
long long qans[MAXQ];
pair<int, int> o[MAXQ];
priority_queue<pair<int, pair<int, int>>> pq;
struct TreapNode {
  int prio, sz, l, r, par;
};
struct Treap {
  int n, root;
  vector<TreapNode> nodes;
  void init(int _n) {
    n = _n, root = -1;
    nodes = vector<TreapNode>(n);
    for (int i = (0); i < (n); ++i)
      nodes[i].prio =
          rand() % 1000 * 1000000 + rand() % 1000 * 1000 + rand() % 1000,
      nodes[i].sz = 1, nodes[i].l = nodes[i].r = nodes[i].par = -1;
  }
  int get(int offset) {
    int at = root;
    while (true) {
      assert(at != -1 && offset < nodes[at].sz);
      int l = nodes[at].l, r = nodes[at].r;
      if (l != -1) {
        if (offset < nodes[l].sz) {
          at = l;
          continue;
        }
        offset -= nodes[l].sz;
      }
      if (offset == 0)
        return at;
      else
        --offset;
      if (r != -1) {
        if (offset < nodes[r].sz) {
          at = r;
          continue;
        }
        offset -= nodes[r].sz;
      }
      assert(false);
    }
  }
  int find(int at) {
    int ret = 0;
    if (nodes[at].l != -1) ret += nodes[nodes[at].l].sz;
    while (nodes[at].par != -1) {
      int to = nodes[at].par;
      if (at == nodes[to].r) ret += 1 + getsz(nodes[to].l);
      at = to;
    }
    return ret;
  }
  int getsz(int a) { return a == -1 ? 0 : nodes[a].sz; }
  void setpar(int a, int b) {
    if (a != -1) nodes[a].par = b;
  }
  void split(int res, int &l, int &r, int sz) {
    if (res == -1) {
      assert(sz == 0);
      l = r = -1;
    } else if (sz <= getsz(nodes[res].l))
      split(nodes[res].l, l, nodes[res].l, sz), setpar(nodes[res].l, res),
          r = res;
    else
      split(nodes[res].r, nodes[res].r, r, sz - 1 - getsz(nodes[res].l)),
          setpar(nodes[res].r, res), l = res;
    if (l != -1) nodes[l].par = -1;
    if (r != -1) nodes[r].par = -1;
    if (res != -1)
      nodes[res].sz = 1 + getsz(nodes[res].l) + getsz(nodes[res].r);
  }
  void merge(int &res, int l, int r) {
    if (l == -1)
      res = r;
    else if (r == -1)
      res = l;
    else if (nodes[l].prio > nodes[r].prio)
      merge(nodes[l].r, nodes[l].r, r), setpar(nodes[l].r, l), res = l;
    else
      merge(nodes[r].l, l, nodes[r].l), setpar(nodes[r].l, r), res = r;
    if (res != -1)
      nodes[res].sz = 1 + getsz(nodes[res].l) + getsz(nodes[res].r);
  }
};
Treap treap;
void initpockets(int sz) {
  treap.init(sz);
  treap.root = 0;
}
int getpocket(int offset) { return treap.get(offset); }
int getoffset(int pocket) { return treap.find(pocket); }
void insertpocket(int offset, int pocket) {
  int l, r;
  treap.split(treap.root, l, r, offset);
  treap.merge(l, l, pocket);
  treap.merge(treap.root, l, r);
}
void solve() {
  for (int i = (0); i < (nq); ++i) o[i] = make_pair(qx[i], i);
  sort(o, o + nq);
  int at = 0;
  while (at < nq && o[at].first < x[0]) {
    int id = o[at++].second;
    qans[id] = qx[id];
  }
  int cround = 0, coffset = 0, cseen = 1;
  initpockets(n);
  pq = priority_queue<pair<int, pair<int, int>>>();
  for (int i = (0); i < (n); ++i) {
    int cx = x[i], nx = i == n - 1 ? INT_MAX : x[i + 1];
    while (at < nq && (nx == INT_MAX || o[at].first < nx)) {
      int id = o[at++].second;
      int qoffset = (coffset + qx[id] - cx) % cseen;
      int qround =
          cround + (qx[id] - cx) / cseen + (qoffset < coffset ? 1 : 0) + qt[id];
      int qpocket = getpocket(qoffset);
      pq.push(make_pair(-qround, make_pair(id, qpocket)));
    }
    int dx = nx == INT_MAX ? INT_MAX : nx - cx;
    if (dx != INT_MAX && coffset + dx < cseen) {
      cx += dx, coffset += dx;
    } else {
      int rem = cseen - coffset;
      cx += rem, coffset = 0, ++cround;
      if (dx != INT_MAX) dx -= rem;
      int full = dx == INT_MAX ? INT_MAX : dx / cseen;
      while (!pq.empty() &&
             (full == INT_MAX || -pq.top().first < cround + full)) {
        int qround = -pq.top().first, id = pq.top().second.first,
            qpocket = pq.top().second.second;
        pq.pop();
        int qoffset = getoffset(qpocket);
        qans[id] = cx + (long long)(qround - cround) * cseen + qoffset;
      }
      if (full == INT_MAX) break;
      cround += full, cx += full * cseen, dx -= full * cseen, coffset += dx,
          cx += dx, dx = 0;
    }
    insertpocket(coffset, i + 1), ++cseen;
  }
}
void run() {
  scanf("%d%d", &n, &nq);
  for (int i = (0); i < (n); ++i) scanf("%d", &x[i]);
  for (int i = (0); i < (nq); ++i) scanf("%d%d", &qx[i], &qt[i]);
  solve();
  for (int i = (0); i < (nq); ++i) printf("%lld\n", qans[i]);
}
long long bfans[MAXQ];
void bf() {
  int sz = 0;
  for (int i = (0); i < (n); ++i) sz = max(sz, x[i] + 1);
  for (int i = (0); i < (nq); ++i) sz = max(sz, qx[i] + 1);
  vector<int> cur(sz);
  for (int i = (0); i < (sz); ++i) cur[i] = i;
  int nxt = sz;
  int t = 0;
  int rem = nq;
  while (rem > 0) {
    for (int i = (0); i < (nq); ++i)
      if (qt[i] == t) {
        bfans[i] = cur[qx[i]];
        --rem;
      }
    int at = 0, idx = 0;
    for (int i = (0); i < (sz); ++i) {
      if (at < n && x[at] == i) {
        ++at;
        continue;
      }
      cur[idx++] = cur[i];
    }
    while (idx < sz) cur[idx++] = nxt++;
    ++t;
  }
}
void stress() {
  for (int rep = (0); rep < (10000); ++rep) {
    n = 100;
    nq = 50;
    int lim = 5 * n;
    for (int i = (0); i < (n); ++i) x[i] = rand() % (lim - n);
    sort(x, x + n);
    for (int i = (0); i < (n); ++i) x[i] += i;
    for (int i = (0); i < (nq); ++i) {
      qx[i] = rand() % lim;
      qt[i] = rand() % 5;
    }
    solve();
    bf();
    bool ok = true;
    for (int i = (0); i < (nq); ++i)
      if (bfans[i] != qans[i]) ok = false;
    if (ok) {
      printf(".");
      continue;
    }
    printf("err\n");
    printf("have:");
    for (int i = (0); i < (nq); ++i) printf(" %lld", qans[i]);
    puts("");
    printf("want:");
    for (int i = (0); i < (nq); ++i) printf(" %lld", bfans[i]);
    puts("");
    printf("%d %d\n", n, nq);
    for (int i = (0); i < (n); ++i) {
      if (i != 0) printf(" ");
      printf("%d", x[i]);
    }
    puts("");
    for (int i = (0); i < (nq); ++i) printf("%d %d\n", qx[i], qt[i]);
    break;
  }
}
int main() {
  run();
  return 0;
}