#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
;
typedef class Query {
 public:
  long long t, x;
  int id;
  Query() {}
  Query(long long t, long long x, int id) : t(t), x(x), id(id) {}
} Query;
typedef class Fenwick {
 public:
  int n;
  int a[N];
  void init(int n) {
    this->n = n;
    memset(a, 0, sizeof(int) * (n + 1));
  }
  void add(int idx, int val) {
    for (; idx <= n; idx += (idx & (-idx))) a[idx] += val;
  }
  int query(int k) {
    int rt = 0, sum = 0, b = 1;
    while ((b << 1) <= n) b <<= 1;
    while (b) {
      if (rt + b <= n && sum + a[rt + b] < k) {
        sum += a[rt += b];
      }
      b >>= 1;
    }
    return rt + 1;
  }
  int get_sum(int idx) {
    int rt = 0;
    for (; idx; idx -= (idx & (-idx))) rt += a[idx];
    return rt;
  }
} Fenwick;
int n, m, _m;
int a[N];
long long ans[N];
Fenwick fen;
Query q1[N], q2[N];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
  }
  sort(a + 1, a + n + 1);
  for (int i = 1, x, k; i <= m; i++) {
    scanf("%d%d", &x, &k);
    if (x < a[1]) {
      ans[i] = x;
    } else {
      q1[++_m] = Query(k, x, i);
    }
  }
  swap(m, _m);
  sort(q1 + 1, q1 + m + 1,
       [&](const Query& a, const Query& b) { return a.x < b.x; });
  long long now = 1e15, curt = 0;
  int i = n, j = m;
  fen.init(n);
  for (int k = 1; k <= n; k++) fen.add(k, 1);
  while (j) {
    long long dt = (now - a[i] + i - 1) / i;
    long long L = now - dt * i;
    while (j && q1[j].x >= L) {
      q2[j].t = curt + (now - q1[j].x + i - 1) / i - q1[j].t;
      q2[j].x = fen.query(i - (now - q1[j].x + i - 1) % i);
      q2[j].id = q1[j].id;
      j--;
    }
    now = L, curt += dt;
    while (i && a[i] >= L) {
      fen.add(fen.query(a[i] - L + 1), -1);
      i--;
    }
  }
  sort(q2 + 1, q2 + m + 1,
       [&](const Query& a, const Query& b) { return a.t < b.t; });
  fen.init(n);
  for (int k = 1; k <= n; k++) fen.add(k, 1);
  i = n, j = 0;
  now = 1e15, curt = 0;
  while (j <= m) {
    long long dt = (now - a[i] + i - 1) / i;
    long long L = now - dt * i;
    while (j <= m && q2[j].t <= curt + dt) {
      ans[q2[j].id] = now + fen.get_sum(q2[j].x) - 1 - (q2[j].t - curt) * i;
      j++;
    }
    now = L, curt += dt;
    while (i && a[i] >= L) {
      fen.add(fen.query(a[i] - L + 1), -1);
      i--;
    }
  }
  swap(m, _m);
  for (int i = 1; i <= m; i++) {
    printf("%lld\n", ans[i]);
  }
  return 0;
}
