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>
int N, a[100000], b[100000];
int Q;
long long O[100000];
struct query_t {
  int x, k, id;
} query[100000];
struct heap {
  int tag;
  struct element {
    int times, id;
    inline bool operator<(const element &a) const { return times > a.times; }
  };
  std::priority_queue<element> queue;
  inline void insert(int times, int id) { queue.push({times - tag, id}); }
  inline bool empty() { return queue.empty(); }
  inline element top() {
    if (empty()) return {1000000000, 0};
    element t = queue.top();
    return {t.times + tag, t.id};
  }
  inline void pop() { queue.pop(); }
};
struct splay_node {
  int fa, son[2], tag, size, min;
  heap h;
} T[100001];
int root;
inline void up(int p) {
  T[p].size = T[T[p].son[0]].size + T[T[p].son[1]].size + 1;
  T[p].min = std::min(std::min(T[T[p].son[0]].min, T[T[p].son[1]].min),
                      T[p].h.top().times);
}
inline void down(int p) {
  if (T[p].son[0]) {
    T[T[p].son[0]].tag += T[p].tag;
    T[T[p].son[0]].min += T[p].tag;
    T[T[p].son[0]].h.tag += T[p].tag;
  }
  if (T[p].son[1]) {
    T[T[p].son[1]].tag += T[p].tag;
    T[T[p].son[1]].min += T[p].tag;
    T[T[p].son[1]].h.tag += T[p].tag;
  }
  T[p].tag = 0;
}
inline void rotate(int p) {
  int f = T[p].fa, g = T[f].fa, w = T[f].son[1] == p;
  (g ? T[g].son[T[g].son[1] == f] : root) = p;
  T[p].fa = g;
  T[f].fa = p;
  T[T[p].son[w ^ 1]].fa = f;
  T[f].son[w] = T[p].son[w ^ 1];
  T[p].son[w ^ 1] = f;
  up(f);
  up(p);
}
void splay(int p, int to = 0) {
  static int q[100001];
  int D;
  q[D = 1] = p;
  while (T[q[D]].fa != to) {
    q[D + 1] = T[q[D]].fa;
    D++;
  }
  while (D) down(q[D--]);
  while (T[p].fa != to)
    if (T[T[p].fa].fa == to)
      rotate(p);
    else if ((T[T[T[p].fa].fa].son[1] == T[p].fa) == (T[T[p].fa].son[1] == p)) {
      rotate(T[p].fa);
      rotate(p);
    } else {
      rotate(p);
      rotate(p);
    }
}
int kth(int p, int k) {
  while (1) {
    down(p);
    if (k < T[T[p].son[0]].size)
      p = T[p].son[0];
    else if (k == T[T[p].son[0]].size)
      return p;
    else
      k -= T[T[p].son[0]].size + 1, p = T[p].son[1];
  }
}
int get_node(int l, int r) {
  if (l == 0 && r == T[root].size - 1) return root;
  if (l == 0) {
    splay(kth(root, r + 1));
    return T[root].son[0];
  }
  if (r == T[root].size - 1) {
    splay(kth(root, l - 1));
    return T[root].son[1];
  }
  splay(kth(root, l - 1));
  splay(kth(root, r + 1), root);
  return T[T[root].son[1]].son[0];
}
void insert_after(int p, int k) {
  splay(kth(root, k));
  if (T[root].son[1] == 0) {
    T[root].son[1] = p;
    T[p].fa = root;
    up(root);
    return;
  }
  splay(kth(root, k + 1), root);
  T[T[root].son[1]].son[0] = p;
  T[p].fa = T[root].son[1];
  up(T[root].son[1]);
  up(root);
}
int rotate_tag, position;
void find_all(int p, int l, int r) {
  down(p);
  int pos = l + T[T[p].son[0]].size;
  while (!T[p].h.empty()) {
    heap::element e = T[p].h.top();
    T[p].h.pop();
    O[e.id] = position + (long long)(e.times - (pos != rotate_tag)) * N +
              (pos - rotate_tag + N) % N;
  }
  if (T[p].son[0]) find_all(T[p].son[0], l, l + T[T[p].son[0]].size - 1);
  if (T[p].son[1]) find_all(T[p].son[1], r - T[T[p].son[1]].size + 1, r);
}
int find_a_violating_node(int p) {
  down(p);
  if (T[p].h.top().times <= 0) return p;
  if (T[T[p].son[0]].min <= 0)
    return find_a_violating_node(T[p].son[0]);
  else
    return find_a_violating_node(T[p].son[1]);
}
int main() {
  T[0].size = 0;
  T[0].min = 1000000000;
  scanf("%d%d", &N, &Q);
  for (int i = 0; i < N; i++) {
    scanf("%d", a + i);
    b[i] = a[i] - i;
  }
  for (int i = 0; i < Q; i++) {
    scanf("%d%d", &query[i].x, &query[i].k);
    query[i].id = i;
  }
  std::sort(query, query + Q,
            [](const query_t &x, const query_t &y) { return x.x < y.x; });
  int cur_q = 0;
  while (cur_q < Q && query[cur_q].x < a[0]) {
    O[query[cur_q].id] = query[cur_q].x;
    cur_q++;
  }
  for (int i = 0; i < N; i++) {
    if (i == 0) {
      T[root = 1] = {0, 0, 0, 0, 1, 1000000000};
      rotate_tag = 0;
      position = a[0];
    } else {
      T[i + 1] = {0, 0, 0, 0, 1, 1000000000};
      insert_after(i + 1, rotate_tag);
      rotate_tag++;
      position++;
    }
    while (cur_q < Q && (i == N - 1 || query[cur_q].x < a[i + 1])) {
      if (i == N - 1 ||
          (a[i + 1] - 1 - query[cur_q].x) / (i + 1) >= query[cur_q].k)
        O[query[cur_q].id] =
            query[cur_q].x + (long long)(i + 1) * query[cur_q].k;
      else {
        int steps = (query[cur_q].x - a[i] + i) / (i + 1);
        int ord = (query[cur_q].x - a[i] + rotate_tag) % (i + 1);
        splay(kth(root, ord));
        T[root].h.insert(query[cur_q].k + steps, query[cur_q].id);
        up(root);
      }
      cur_q++;
    }
    if (i == N - 1)
      find_all(root, 0, i);
    else {
      T[root].min -= (a[i + 1] - a[i] - 1) / (i + 1);
      T[root].tag -= (a[i + 1] - a[i] - 1) / (i + 1);
      T[root].h.tag -= (a[i + 1] - a[i] - 1) / (i + 1);
      if ((a[i + 1] - a[i] - 1) % (i + 1)) {
        int l = (rotate_tag + 1) % (i + 1),
            r = (rotate_tag + a[i + 1] - a[i] - 1) % (i + 1);
        if (l <= r) {
          int p = get_node(l, r);
          T[p].min--;
          T[p].tag--;
          T[p].h.tag--;
          while (p = T[p].fa) up(p);
        } else {
          int p = get_node(l, i);
          T[p].min--;
          T[p].tag--;
          T[p].h.tag--;
          while (p = T[p].fa) up(p);
          p = get_node(0, r);
          T[p].min--;
          T[p].tag--;
          T[p].h.tag--;
          while (p = T[p].fa) up(p);
        }
      }
      rotate_tag = (rotate_tag + a[i + 1] - a[i] - 1) % (i + 1);
      position = a[i + 1] - 1;
      while (T[root].min <= 0) {
        int p = find_a_violating_node(root);
        splay(p);
        int pos = T[T[p].son[0]].size;
        while (T[p].h.top().times <= 0) {
          heap::element e = T[p].h.top();
          T[p].h.pop();
          O[e.id] = position +
                    (long long)(e.times - (pos != rotate_tag)) * (i + 1) +
                    (pos - rotate_tag + i + 1) % (i + 1);
        }
        up(p);
      }
    }
  }
  for (int i = 0; i < Q; i++) printf("%lld\n", O[i]);
  return 0;
}