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>
std::mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());
struct Treap {
  int priority;
  int64_t key, key_lazy;
  int val, val_min, val_lazy;
  int size;
  struct Treap *left, *right;
  int id;
  static struct Treap* nil;
  Treap()
      : priority(-1),
        key(0),
        key_lazy(0),
        val(1e9 + 7),
        val_min(1e9 + 7),
        val_lazy(0),
        size(0),
        left(nil),
        right(nil),
        id(-1) {}
  Treap(int64_t key, int val, int id)
      : priority(std::uniform_int_distribution<int>(0, INT_MAX)(rng)),
        key(key),
        key_lazy(0),
        val(val),
        val_min(val),
        val_lazy(0),
        size(1),
        left(nil),
        right(nil),
        id(id) {}
  void pull() {
    if (this != nil) {
      left->push();
      right->push();
      size = left->size + right->size + 1;
      val_min = std::min(val, std::min(left->val_min, right->val_min));
    }
  }
  void push() {
    if (this != nil) {
      left->key_lazy += key_lazy;
      right->key_lazy += key_lazy;
      key += key_lazy;
      key_lazy = 0;
      left->val_lazy += val_lazy;
      right->val_lazy += val_lazy;
      val_min += val_lazy;
      val += val_lazy;
      val_lazy = 0;
    }
  }
  static void dump(struct Treap* x) {
    x->push();
    if (x != nil) {
      printf("[");
      dump(x->left);
      printf("%I64d:%d", x->key, x->val);
      dump(x->right);
      printf("]");
    }
  }
  static void split(struct Treap* x, int k, struct Treap*& L,
                    struct Treap*& R) {
    assert(k >= 0 && k <= x->size);
    x->push();
    L = R = nil;
    if (x == nil) return;
    if (k <= x->left->size) {
      split(x->left, k, L, x->left);
      R = x;
    } else {
      split(x->right, k - x->left->size - 1, x->right, R);
      L = x;
    }
    x->pull();
  }
  static struct Treap* concat(struct Treap* x, struct Treap* y) {
    x->push();
    y->push();
    if (x == nil) return y;
    if (y == nil) return x;
    if (x->priority > y->priority) {
      x->right = concat(x->right, y);
      x->pull();
      return x;
    } else {
      y->left = concat(x, y->left);
      y->pull();
      return y;
    }
  }
  static int lower_bound(struct Treap* x, int64_t key) {
    x->push();
    if (x == nil) return 0;
    if (key <= x->key) {
      return lower_bound(x->left, key);
    } else {
      return lower_bound(x->right, key) + x->left->size + 1;
    }
  }
  static int upper_bound(struct Treap* x, int64_t key) {
    x->push();
    if (x == nil) return 0;
    if (key < x->key) {
      return upper_bound(x->left, key);
    } else {
      return upper_bound(x->right, key) + x->left->size + 1;
    }
  }
  static int argmin(struct Treap* x) {
    if (x == nil) return 0;
    x->push();
    x->left->push();
    x->right->push();
    if (x->left != nil && x->val_min == x->left->val_min) {
      return argmin(x->left);
    } else if (x->val_min == x->val) {
      return x->left->size;
    } else if (x->right != nil && x->val_min == x->right->val_min) {
      return argmin(x->right) + x->left->size + 1;
    } else {
      assert(false);
    }
  }
  static struct Treap* kth(struct Treap* x, int k) {
    assert(k >= 0 && k < x->size);
    x->push();
    if (k < x->left->size) {
      return kth(x->left, k);
    } else if (k > x->left->size) {
      return kth(x->right, k - x->left->size - 1);
    } else {
      return x;
    }
  }
  static struct Treap* extract(struct Treap*& x, int l, int r) {
    struct Treap *L, *R;
    split(x, r, x, R);
    split(x, l, L, x);
    struct Treap* res = x;
    x = concat(L, R);
    return res;
  }
  static struct Treap* extract(struct Treap*& x, int l) {
    return extract(x, l, l + 1);
  }
  static struct Treap* merge(struct Treap* x, struct Treap* y) {
    struct Treap* res = nil;
    while (true) {
      if (x == nil) return concat(res, y);
      if (y == nil) return concat(res, x);
      if (kth(x, 0)->key > kth(y, 0)->key) {
        std::swap(x, y);
      }
      int k = upper_bound(x, kth(y, 0)->key);
      assert(k > 0);
      struct Treap* L;
      split(x, k, L, x);
      res = concat(res, L);
    }
  }
};
struct Treap* Treap::nil = new Treap();
int64_t holes[100005];
int64_t ans[100005];
int main() {
  int N, Q;
  scanf("%d %d", &N, &Q);
  for (int i = 0; i < N; i++) {
    scanf("%I64d", &holes[i]);
  }
  struct Treap* curr = Treap::nil;
  for (int i = 0; i < Q; i++) {
    int X, K;
    scanf("%d %d", &X, &K);
    if (X < holes[0]) {
      ans[i] = X;
    } else {
      curr = Treap::merge(curr, new Treap(X, K, i));
    }
  }
  holes[N] = 1e18;
  for (int i = 1; i <= N; i++) {
    struct Treap* next = Treap::nil;
    {
      int k = Treap::lower_bound(curr, holes[i]);
      struct Treap* eject;
      Treap::split(curr, k, curr, eject);
      next = Treap::merge(next, eject);
    }
    while (curr != Treap::nil) {
      int64_t moves = std::min<int64_t>(
          curr->val_min,
          (holes[i] - Treap::kth(curr, curr->size - 1)->key + i - 1) / i);
      curr->key_lazy += moves * i;
      curr->val_lazy -= moves;
      curr->push();
      {
        int k = Treap::lower_bound(curr, holes[i]);
        struct Treap* eject;
        Treap::split(curr, k, curr, eject);
        if (eject != Treap::nil) {
          eject->key_lazy -= i;
          eject->val_lazy++;
          eject->push();
          next = Treap::merge(next, eject);
        }
      }
      if (curr != Treap::nil && curr->val_min == 0) {
        struct Treap* tmp = Treap::extract(curr, Treap::argmin(curr));
        ans[tmp->id] = tmp->key;
      }
    }
    std::swap(curr, next);
  }
  for (int i = 0; i < Q; i++) {
    printf("%I64d\n", ans[i]);
  }
}