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 maxn = 110000;
long long nn;
long long c[maxn];
void init_c() {
  memset(c, 0, sizeof(c));
  for (long long i = 1; i <= nn; ++i) {
    for (long long j = i; j <= nn; j += (j & -j)) {
      c[j]++;
    }
  }
}
void sub_c(long long k) {
  for (long long i = k; i <= nn; i += (i & -i)) {
    c[i]--;
  }
}
long long sum_c(long long k) {
  long long ret = 0;
  for (long long i = k; i > 0; i -= (i & -i)) {
    ret += c[i];
  }
  return ret;
}
long long kth_c(long long k) {
  long long x = 1, y = nn;
  while (y > x) {
    long long m = x + (y - x) / 2;
    if (sum_c(m) >= k) {
      y = m;
    } else {
      x = m + 1;
    }
  }
  return y;
}
long long start[maxn], len[maxn], step[maxn];
vector<long long> bucket[maxn];
long long cnt;
long long rev_start[maxn];
long long s[maxn];
void init() {
  init_c();
  start[0] = s[nn] - nn + 1;
  len[0] = nn;
  step[0] = 0;
  cnt = 1;
  long long n = nn;
  while (true) {
    long long a = start[cnt - 1];
    while (n > 0 && s[n] >= a) {
      long long idx_at_cur = s[n] - a + 1;
      long long idx_at_all = kth_c(idx_at_cur);
      bucket[cnt - 1].push_back(idx_at_all);
      sub_c(idx_at_all);
      n--;
    }
    if (n == 0) {
      break;
    }
    long long k = (a - s[n] + n - 1) / n;
    start[cnt] = a - n * k;
    len[cnt] = n;
    step[cnt] = step[cnt - 1] + k;
    cnt++;
  }
  for (long long i = 0; i < cnt; ++i) {
    rev_start[cnt - i - 1] = start[i];
  }
}
vector<long long> step1[maxn];
void gao(long long m, long long p, long long k) {
  long long tmp = upper_bound(rev_start, rev_start + cnt, p) - rev_start;
  assert(tmp != 0);
  long long i = cnt - tmp;
  long long a = start[i], n = len[i];
  long long dk = (p - a) / n;
  long long np = p - dk * n, nk = k + dk;
  long long ii = lower_bound(step, step + cnt, step[i] - nk) - step;
  step1[i].push_back(m);
  long long idx_at_cur = np - a + 1;
  step1[i].push_back(idx_at_cur);
  step1[i].push_back(ii);
  step1[i].push_back(nk - (step[i] - step[ii]));
}
vector<long long> step2[maxn];
long long ans[maxn];
void solve() {
  init_c();
  for (long long i = 0; i < cnt; ++i) {
    const vector<long long>& tmp = step1[i];
    for (long long j = 0; j < tmp.size(); j += 4) {
      long long ii = tmp[j + 2];
      long long idx_at_all = kth_c(tmp[j + 1]);
      step2[ii].push_back(tmp[j]);
      step2[ii].push_back(idx_at_all);
      step2[ii].push_back(tmp[j + 3]);
    }
    const vector<long long>& item = bucket[i];
    for (long long j = 0; j < item.size(); ++j) {
      sub_c(item[j]);
    }
  }
  init_c();
  for (long long i = 0; i < cnt; ++i) {
    const vector<long long>& tmp = step2[i];
    for (long long j = 0; j < tmp.size(); j += 3) {
      long long idx_at_cur = sum_c(tmp[j + 1]);
      ans[tmp[j]] = start[i] + idx_at_cur - 1 + len[i] * tmp[j + 2];
    }
    const vector<long long>& item = bucket[i];
    for (long long j = 0; j < item.size(); ++j) {
      sub_c(item[j]);
    }
  }
}
int main() {
  int m;
  scanf("%I64d %d", &nn, &m);
  for (int i = 1; i <= nn; ++i) {
    scanf("%I64d", &s[i]);
    s[i]++;
  }
  init();
  long long p, k;
  for (int i = 1; i <= m; ++i) {
    scanf("%I64d %I64d", &p, &k);
    p++;
    if (p < s[1]) {
      ans[i] = p;
    } else {
      gao(i, p, k);
    }
  }
  solve();
  for (int i = 1; i <= m; ++i) {
    printf("%I64d\n", ans[i] - 1);
  }
  return 0;
}