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;
inline long long read() {
  long long x = 0, f = 1, c = getchar();
  while (c < 48) c == '-' && (f = -1), c = getchar();
  while (c > 47) x = x * 10 + c - '0', c = getchar();
  return x * f;
}
const int MAXN = 100005;
int rep[MAXN], enp[MAXN], arr[MAXN];
int idx[MAXN], rt[MAXN];
int n, q, stp;
long long pre[MAXN];
namespace Bit {
int c[MAXN];
inline void modify(int x, int k) {
  while (x <= n) c[x] += k, x += x & -x;
}
inline int query(int x) {
  int res = 0;
  while (x) res += c[x], x -= x & -x;
  return res;
}
inline int calc_idx(int x) {
  int l = 1, r = n, res = n + 1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (query(mid) > x)
      res = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  return modify(res, -1), res;
}
}  // namespace Bit
namespace Seg {
int tot;
int ls[MAXN * 200], rs[MAXN * 200], sum[MAXN * 200];
void modify(int &x, int y, int l, int r, int k) {
  ls[x = ++tot] = ls[y];
  rs[x] = rs[y];
  sum[x] = sum[y] + 1;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (k <= mid) modify(ls[x], ls[y], l, mid, k);
  if (k > mid) modify(rs[x], rs[y], mid + 1, r, k);
}
int qrnk(int x, int l, int r, int k) {
  if (l == r) return l;
  int mid = (l + r) >> 1;
  if (sum[ls[x]] > k) return qrnk(ls[x], l, mid, k);
  return qrnk(rs[x], mid + 1, r, k - sum[ls[x]]);
}
int qsum(int x, int l, int r, int k) {
  if (r <= k) return sum[x];
  int mid = (l + r) >> 1, res = 0;
  if (k > mid) res += qsum(rs[x], mid + 1, r, k);
  return res + qsum(ls[x], l, mid, k);
}
}  // namespace Seg
pair<long long, int> calc(int t, int in, int k) {
  in += rep[t] - k;
  int res = upper_bound(rep, rep + n, in) - rep;
  return make_pair((long long)in * res - pre[res], res);
}
inline int query_out(int x, int k) {
  int l = 0, r = n - 1, res = -1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (calc(mid, 0, k).first <= x)
      res = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  return res;
}
inline int query_in(int t, int x, int k) {
  int l = 0, r = rep[t + 1] - rep[t], res = -1;
  if (t == n - 1) r = x / n + k + 1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (calc(t, mid, k).first <= x)
      res = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  return res;
}
inline void sol(int x, int k) {
  if (x < stp) return printf("%d\n", x), void();
  int a = query_out(x -= stp, k), b = query_in(a, x, k);
  auto res = calc(a, b, k);
  int rem = x - res.first, rk = Seg::qrnk(rt[res.second], 0, n - 1, rem);
  int t = (rk ? Seg::qsum(rt[a + 1], 0, n - 1, rk - 1) : 0);
  printf("%lld\n", stp + enp[a] + (long long)b * (a + 1) + t);
}
int main(int argc, char const *argv[]) {
  n = read();
  q = read();
  for (int i = 0; i < n; ++i) arr[i] = read();
  stp = arr[0];
  for (int i = 0; i < n; ++i) arr[i] -= stp;
  for (int i = 1; i < n; ++i) {
    rep[i] = rep[i - 1] + (arr[i] - enp[i - 1]) / i;
    enp[i] = enp[i - 1] + (rep[i] - rep[i - 1]) * i;
    pre[i + 1] = pre[i] + rep[i];
  }
  for (int i = 1; i <= n; ++i) Bit::modify(i, 1);
  for (int i = n - 1; ~i; --i) idx[i] = Bit::calc_idx(arr[i] - enp[i]) - 1;
  for (int i = 0; i < n; ++i) Seg::modify(rt[i + 1], rt[i], 0, n - 1, idx[i]);
  for (int i = 1, x; i <= q; ++i) x = read(), sol(x, read());
  return 0;
}