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 long long oo = 1e15;
struct node {
  node *ch[2];
  int siz;
  long long tag, x;
  node() : siz(1), tag(0) { memset(ch, 0, sizeof ch); }
  void pull() {
    siz = ch[0]->siz + ch[1]->siz;
    return;
  }
  void push() {
    if (tag) {
      for (int i = 0; i < 2; ++i) ch[i]->tag += tag, ch[i]->x += tag;
      tag = 0;
    }
    return;
  }
};
struct segment_tree {
  int n;
  node *root;
  segment_tree() {}
  segment_tree(vector<long long> &a) {
    n = a.size();
    function<void(node *&, int, int)> B = [&](node *&u, int l, int r) {
      u = new node;
      if (l == r) {
        u->x = a[l];
        return;
      }
      int mid = l + r >> 1;
      return B(u->ch[0], l, mid), B(u->ch[1], mid + 1, r), u->pull();
    };
    B(root, 0, n - 1);
    return;
  }
  void M(int a, int b, long long x) {
    if (a <= b) M(a, b, x, root, 0, n - 1);
    return;
  }
  void D(int i) { return D(i, root, 0, n - 1); }
  int Qi(int k) { return Qi(k, root, 0, n - 1); }
  long long Qx(int i) { return Qx(i, root, 0, n - 1); }

 private:
  void M(int a, int b, long long x, node *&u, int l, int r) {
    if (a <= l && r <= b) {
      u->tag += x;
      u->x += x;
      return;
    }
    int mid = l + r >> 1;
    u->push();
    if (a <= mid) M(a, b, x, u->ch[0], l, mid);
    if (mid < b) M(a, b, x, u->ch[1], mid + 1, r);
    return u->pull();
  }
  void D(int i, node *&u, int l, int r) {
    if (l == r) {
      assert(u->siz);
      u->x = -1;
      u->siz = 0;
      return;
    }
    int mid = l + r >> 1;
    u->push();
    if (i <= mid)
      D(i, u->ch[0], l, mid);
    else
      D(i, u->ch[1], mid + 1, r);
    return u->pull();
  }
  int Qi(int k, node *&u, int l, int r) {
    if (l == r) return l;
    int mid = l + r >> 1;
    u->push();
    return (u->ch[0]->siz >= k) ? Qi(k, u->ch[0], l, mid)
                                : Qi(k - u->ch[0]->siz, u->ch[1], mid + 1, r);
  }
  long long Qx(int i, node *&u, int l, int r) {
    if (l == r) return u->x;
    int mid = l + r >> 1;
    u->push();
    return i <= mid ? Qx(i, u->ch[0], l, mid) : Qx(i, u->ch[1], mid + 1, r);
  }
};
int main() {
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  vector<long long> b(n);
  for (int i = 0; i < n; ++i) cin >> a[i], b[i] = oo + i;
  segment_tree seg(b);
  long long t = 0;
  vector<long long> ans(m);
  vector<pair<pair<int, int>, int> > q1(m);
  vector<pair<pair<long long, int>, int> > q2;
  for (int i = 0; i < m; ++i)
    cin >> q1[i].first.first >> q1[i].first.second, q1[i].second = i;
  for (int i = 0; i < q1.size();) {
    if (q1[i].first.first < a[0] || q1[i].first.second == 0)
      ans[q1[i].second] = q1[i].first.first, swap(q1[i], q1.back()),
      q1.pop_back();
    else
      ++i;
  }
  sort(q1.begin(), q1.end());
  while (q1.size()) {
    long long l = seg.Qx(seg.Qi(1)), r = seg.Qx(seg.Qi(seg.root->siz));
    while (q1.size() && q1.back().first.first >= l &&
           q1.back().first.first <= r) {
      q2.push_back(make_pair(make_pair(t - q1.back().first.second,
                                       seg.Qi(q1.back().first.first - l + 1)),
                             q1.back().second));
      q1.pop_back();
    }
    if (!q1.size()) break;
    ++t;
    int i = lower_bound(a.begin(), a.end(), l) - a.begin() - 1, j;
    long long lst = l - 1;
    for (j = i + 1; j < a.size(); ++j) {
      if (a[j] > r) break;
      if (lst + 1 < a[j])
        seg.M(seg.Qi(lst + 1 - l + 1), seg.Qi(a[j] - 1 - l + 1), -j);
      lst = a[j];
    }
    if (lst + 1 <= r) seg.M(seg.Qi(lst + 1 - l + 1), seg.Qi(r - l + 1), -j);
    for (int fuck = 0, j = i + 1; j < a.size(); ++j) {
      if (a[j] > r) break;
      seg.D(seg.Qi(a[j] - l + 1 - fuck));
      ++fuck;
    }
    l = seg.Qx(seg.Qi(1)), r = seg.Qx(seg.Qi(seg.root->siz));
    i = lower_bound(a.begin(), a.end(), l) - a.begin();
    if (i < a.size() && a[i] <= r || !i) continue;
    if (q1.back().first.first >= l && q1.back().first.second <= r) continue;
    long long nxt = max(a[i - 1], q1.back().first.first);
    long long dlt = (l - nxt) / i + 5;
    while (l - dlt * i <= nxt) --dlt;
    ++dlt;
    if (dlt <= 2) continue;
    seg.M(0, n - 1, -dlt * i);
    t += dlt;
  }
  seg = segment_tree(b);
  t = 0;
  sort(q2.begin(), q2.end());
  reverse(q2.begin(), q2.end());
  while (q2.size()) {
    long long l = seg.Qx(seg.Qi(1)), r = seg.Qx(seg.Qi(seg.root->siz));
    while (q2.size() && q2.back().first.first == t) {
      ans[q2.back().second] = seg.Qx(q2.back().first.second);
      q2.pop_back();
    }
    if (!q2.size()) break;
    ++t;
    int i = lower_bound(a.begin(), a.end(), l) - a.begin() - 1, j;
    long long lst = l - 1;
    for (j = i + 1; j < a.size(); ++j) {
      if (a[j] > r) break;
      if (lst + 1 < a[j])
        seg.M(seg.Qi(lst + 1 - l + 1), seg.Qi(a[j] - 1 - l + 1), -j);
      lst = a[j];
    }
    if (lst + 1 <= r) seg.M(seg.Qi(lst + 1 - l + 1), seg.Qi(r - l + 1), -j);
    for (int fuck = 0, j = i + 1; j < a.size(); ++j) {
      if (a[j] > r) break;
      seg.D(seg.Qi(a[j] - l + 1 - fuck));
      ++fuck;
    }
    l = seg.Qx(seg.Qi(1)), r = seg.Qx(seg.Qi(seg.root->siz));
    i = lower_bound(a.begin(), a.end(), l) - a.begin();
    if (i < a.size() && a[i] <= r || !i) continue;
    if (q2.back().first.first == t) continue;
    long long nxt = a[i - 1];
    long long dlt = (l - nxt) / i + 5;
    while (l - dlt * i <= nxt) --dlt;
    ++dlt;
    dlt = min(dlt, q2.back().first.first - t);
    if (dlt <= 2) continue;
    seg.M(0, n - 1, -dlt * i);
    t += dlt;
  }
  copy(ans.begin(), ans.end(), ostream_iterator<long long>(cout, "\n"));
  return 0;
}