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;
int a[100000];
struct event {
  int x, k, i;
};
bool comp(event a, event b) {
  if (a.x == b.x)
    return a.k < b.k;
  else
    return a.x < b.x;
}
vector<event> events;
long long int ans[100000];
struct node {
  node *l, *r;
  int p, k, s, c, lazy;
  long long int x, m;
};
node *root = NULL;
int size(node *n) {
  if (n != NULL)
    return n->s;
  else
    return 0;
}
long long int mm(node *n) {
  if (n != NULL)
    return n->m;
  else
    return 5e18;
}
int update(node *n) {
  if (n != NULL) {
    n->s = size(n->l) + size(n->r) + n->c;
    n->m = min(n->x, min(mm(n->l), mm(n->r)));
  }
  return 0;
}
int prop(node *n) {
  if (n != NULL) {
    n->x += n->lazy, n->m += n->lazy;
    if (n->l != NULL) n->l->lazy += n->lazy;
    if (n->r != NULL) n->r->lazy += n->lazy;
    n->lazy = 0;
  }
  return 0;
}
int split(node *n, node *&l, node *&r, int s) {
  prop(n);
  if (n == NULL)
    l = r = NULL;
  else if (s >= size(n->l) + n->c)
    prop(n->l), split(n->r, n->r, r, s - size(n->l) - n->c), l = n;
  else
    prop(n->r), split(n->l, l, n->l, s), r = n;
  update(l), update(r);
  return 0;
}
int merge(node *l, node *r, node *&n) {
  prop(l), prop(r);
  if (l == NULL)
    n = r;
  else if (r == NULL)
    n = l;
  else if (l->p > r->p)
    prop(l->l), merge(l->r, r, l->r), n = l;
  else
    prop(r->r), merge(l, r->l, r->l), n = r;
  if (n != NULL) prop(n->l), prop(n->r), assert(n->lazy == 0);
  update(n);
  return 0;
}
int main() {
  int i;
  int n, m, x, k;
  scanf("%d %d", &n, &m);
  for (i = 0; i < n; i++)
    scanf("%d", &a[i]), events.push_back((event){a[i], -1, -1});
  for (i = 0; i < m; i++) {
    scanf("%d %d", &x, &k);
    if ((x < a[0]) || (k == 0))
      ans[i] = x;
    else
      events.push_back((event){x, k, i});
  }
  sort(events.begin(), events.end(), comp);
  int j, c = 0;
  for (i = 0; i < events.size(); i++) {
    if (i > 0) {
      int t = ((events[i].k == -1) ? events[i].x - 1 : events[i].x) -
              events[i - 1].x;
      node *l, *r;
      int a = events[i - 1].x;
      while (1) {
        split(root, l, r, t % c);
        if (mm(l) == 1) {
          merge(l, r, root);
          node *n = root;
          int s = 0;
          vector<node *> vv;
          while (1) {
            vv.push_back(n), prop(n), prop(n->l), prop(n->r);
            if (mm(n->l) == 1)
              n = n->l;
            else if (mm(n->r) == 1)
              s += size(n->l) + n->c, n = n->r;
            else {
              s += size(n->l);
              break;
            }
          }
          ans[n->k] = a - c + (long long int)c * mm(n) + s;
          node *n2;
          merge(n->l, n->r, n2);
          if (vv.size() == 1)
            root = n2;
          else {
            if (vv[vv.size() - 2]->l == vv.back())
              vv[vv.size() - 2]->l = n2;
            else
              vv[vv.size() - 2]->r = n2;
            for (j = vv.size() - 2; j >= 0; j--) update(vv[j]);
          }
        } else {
          if (l != NULL) l->lazy--;
          merge(r, l, root);
          a += t % c, t -= t % c;
          break;
        }
      }
      assert((t % c) == 0);
      while (mm(root) <= t / c) {
        node *n = root;
        int s = 0;
        vector<node *> vv;
        while (1) {
          vv.push_back(n), prop(n), prop(n->l), prop(n->r);
          if (mm(n->l) == mm(n))
            n = n->l;
          else if (mm(n->r) == mm(n))
            s += size(n->l) + n->c, n = n->r;
          else {
            s += size(n->l);
            break;
          }
        }
        ans[n->k] = a - c + (long long int)c * mm(n) + s;
        node *n2;
        merge(n->l, n->r, n2);
        if (vv.size() == 1)
          root = n2;
        else {
          if (vv[vv.size() - 2]->l == vv.back())
            vv[vv.size() - 2]->l = n2;
          else
            vv[vv.size() - 2]->r = n2;
          for (j = vv.size() - 2; j >= 0; j--) update(vv[j]);
        }
      }
      root->lazy -= t / c;
      prop(root);
    }
    if (events[i].k == -1) {
      node *n = new node;
      n->l = n->r = NULL, n->p = rand(), n->s = n->c = 1, n->lazy = 0;
      n->k = -1, n->x = n->m = 5e18, c++;
      merge(root, n, root);
    } else {
      node *n = new node;
      n->l = n->r = NULL, n->p = rand(), n->s = n->c = 0, n->lazy = 0;
      n->k = events[i].i, n->x = n->m = events[i].k;
      merge(root, n, root);
    }
  }
  int a = events.back().x;
  while (mm(root) < 2e18) {
    node *n = root;
    int s = 0;
    vector<node *> vv;
    while (1) {
      vv.push_back(n), prop(n), prop(n->l), prop(n->r);
      if (mm(n->l) == mm(n))
        n = n->l;
      else if (mm(n->r) == mm(n))
        s += size(n->l) + n->c, n = n->r;
      else {
        s += size(n->l);
        break;
      }
    }
    ans[n->k] = a - c + (long long int)c * mm(n) + s;
    node *n2;
    merge(n->l, n->r, n2);
    if (vv.size() == 1)
      root = n2;
    else {
      if (vv[vv.size() - 2]->l == vv.back())
        vv[vv.size() - 2]->l = n2;
      else
        vv[vv.size() - 2]->r = n2;
      for (j = vv.size() - 2; j >= 0; j--) update(vv[j]);
    }
  }
  for (i = 0; i < m; i++) printf("%I64d\n", ans[i]);
  return 0;
}