#include <bits/stdc++.h>
using namespace std;
const long long maxn = 1e5 + 10;
long long ans[maxn];
long long pl[maxn];
long long segt[4 * maxn];
long long f1[4 * maxn], f2[4 * maxn];
inline long long lz1(long long v, long long s, long long e, long long val) {
  f2[v] = 0;
  segt[v] = (e - s) * val;
  f1[v] = val;
}
inline long long lz2(long long v, long long s, long long e, long long val) {
  f2[v] += val;
  segt[v] += (e - s) * val;
}
inline long long shift(long long v, long long s, long long e) {
  long long lc = 2 * v, rc = 2 * v + 1, m = (e + s) / 2;
  if (f1[v] != 0) {
    lz1(lc, s, m, f1[v]);
    lz1(rc, m, e, f1[v]);
    f1[v] = 0;
  }
  if (f2[v] != 0) {
    lz2(lc, s, m, f2[v]);
    lz2(rc, m, e, f2[v]);
    f2[v] = 0;
  }
  return 0;
}
long long set1(long long v, long long l, long long r, long long s, long long e,
               long long val) {
  if (r <= l) return 0;
  if (s >= r || e <= l) return 0;
  if (s >= l && e <= r) {
    lz1(v, s, e, val);
    return 0;
  }
  shift(v, s, e);
  long long m = (e + s) / 2;
  set1(2 * v, l, r, s, m, val);
  set1(2 * v + 1, l, r, m, e, val);
  segt[v] = segt[2 * v] + segt[2 * v + 1];
  return 0;
}
long long update(long long v, long long l, long long r, long long s,
                 long long e, long long val) {
  if (r <= l) return 0;
  if (s >= r || e <= l) return 0;
  if (s >= l && e <= r) {
    lz2(v, s, e, val);
    return 0;
  }
  shift(v, s, e);
  long long m = (e + s) / 2;
  update(2 * v, l, r, s, m, val);
  update(2 * v + 1, l, r, m, e, val);
  segt[v] = segt[2 * v] + segt[2 * v + 1];
  return 0;
}
long long query(long long v, long long ind, long long s, long long e) {
  if (ind < s || ind >= e) return 0;
  if (e - s == 1) {
    return segt[v];
  }
  shift(v, s, e);
  long long m = (e + s) / 2;
  return query(2 * v, ind, s, m) + query(2 * v + 1, ind, m, e);
}
long long build(long long v, long long s, long long e) {
  f1[v] = f2[v] = 0;
  if (e - s == 1) return 0;
  long long m = (e + s) / 2;
  build(2 * v, s, m);
  build(2 * v + 1, m, e);
}
long long q, x;
long long bs(long long lo, long long hi, long long t, long long v) {
  long long m, found = (t == 0) ? lo - 1 : hi + 1;
  while (lo <= hi) {
    m = (lo + hi) / 2;
    long long as = query(1, m, 0, q);
    if (t) {
      if (as + v > x) {
        found = m;
        hi = m - 1;
      } else
        lo = m + 1;
    } else {
      if (as < v) {
        found = m;
        lo = m + 1;
      } else
        hi = m - 1;
    }
  }
  return found;
}
int32_t main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  long long k;
  cin >> x >> k;
  long long r;
  vector<long long> swp;
  swp.push_back(1e9 + 1);
  for (long long i = 0; i < k; i++) {
    cin >> r;
    swp.push_back(r);
  }
  sort(swp.begin(), swp.end());
  cin >> q;
  long long t, a, sz = q - 1;
  vector<pair<long long, long long> > qs;
  vector<pair<long long, long long> > ts;
  for (long long i = 0; i < q; i++) {
    cin >> t >> a;
    qs.push_back({a, i});
    ts.push_back({-t, i});
  }
  sort(qs.begin(), qs.end());
  sort(ts.begin(), ts.end());
  build(1, 0, q);
  for (long long i = 0; i < q; i++) {
    pl[qs[i].second] = i;
    set1(1, i, i + 1, 0, q, qs[i].first);
  }
  long long sw = 0, ca;
  long long lt = 0;
  for (long long i = 0; i < swp.size(); i++) {
    while (sz >= 0 && -ts[sz].first <= swp[i]) {
      ca = query(1, pl[ts[sz].second], 0, q);
      long long t = -ts[sz].first;
      if (i % 2) {
        ca = min(x, ca + (t - lt));
      } else {
        ca = max(0ll, ca - (t - lt));
      }
      ans[ts[sz].second] = ca;
      sz--;
      ts.pop_back();
    }
    long long in = bs(0, q - 1, i % 2, swp[i] - lt);
    if (i % 2) {
      set1(1, in, q, 0, q, x);
      update(1, 0, in, 0, q, swp[i] - lt);
    } else {
      set1(1, 0, in + 1, 0, q, 0);
      update(1, in + 1, q, 0, q, -(swp[i] - lt));
    }
    lt = swp[i];
  }
  for (long long i = 0; i < q; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}
