#include <bits/stdc++.h>
using namespace std;
template <class T>
using vv = vector<vector<T>>;
template <class T>
inline bool MX(T &l, const T &r) {
  return l < r ? l = r, 1 : 0;
}
template <class T>
inline bool MN(T &l, const T &r) {
  return l > r ? l = r, 1 : 0;
}
const long long MOD = 1e9 + 7;
long long first;
int K;
int Q;
long long rs[114514];
long long ts[114514];
long long as[114514];
long long ans[114514];
struct LazySeg {
  int size;
  vector<char> has_lazy;
  vector<long long> seg;
  vector<long long> lazy;
  vector<long long> width;
  vector<long long> assi;
  const long long INF = 0x3fffffffff;
  LazySeg(vector<long long> A) {
    int n = A.size();
    size = 1;
    while (size < n) size *= 2;
    seg.resize(size);
    seg.insert(seg.end(), A.begin(), A.end());
    seg.resize(size * 2);
    lazy.resize(size * 2);
    has_lazy.resize(size * 2);
    width.resize(size * 2);
    assi.resize(size * 2);
    for (int(i) = (size)-1; (i) >= 0; --(i)) {
      seg[i] = max(seg[i * 2], seg[i * 2 + 1]);
      width[i] = width[i * 2] + width[i * 2 + 1];
    }
  }
  void LazyPropagate(int k) {
    if (has_lazy[k]) {
      seg[k] = assi[k];
      if (k < size - 1) {
        has_lazy[k * 2] = true;
        has_lazy[k * 2 + 1] = true;
        assi[k * 2] = assi[k];
        assi[k * 2 + 1] = assi[k];
        lazy[k * 2] = 0;
        lazy[k * 2 + 1] = 0;
      }
      has_lazy[k] = false;
    }
    seg[k] += lazy[k];
    if (k < size - 1) {
      lazy[k * 2] += lazy[k];
      lazy[k * 2 + 1] += lazy[k];
    }
    lazy[k] = 0;
  }
  void Add(int wishl, int wishr, int k, int watchl, int watchr, long long x) {
    if (wishr <= watchl || watchr <= wishl) {
      LazyPropagate(k);
      return;
    }
    if (wishl <= watchl && watchr <= wishr) {
      lazy[k] += x;
      LazyPropagate(k);
      return;
    }
    LazyPropagate(k);
    int mid = (watchl + watchr) / 2;
    Add(wishl, wishr, k * 2, watchl, mid, x);
    Add(wishl, wishr, k * 2 + 1, mid, watchr, x);
    seg[k] = max(seg[k * 2], seg[k * 2 + 1]);
  }
  void Move(int wishl, int wishr, int k, int watchl, int watchr, long long x) {
    if (wishr <= watchl || watchr <= wishl) {
      LazyPropagate(k);
      return;
    }
    if (wishl <= watchl && watchr <= wishr) {
      has_lazy[k] = true;
      lazy[k] = 0;
      assi[k] = x;
      LazyPropagate(k);
      return;
    }
    LazyPropagate(k);
    int mid = (watchl + watchr) / 2;
    Move(wishl, wishr, k * 2, watchl, mid, x);
    Move(wishl, wishr, k * 2 + 1, mid, watchr, x);
    seg[k] = max(seg[k * 2], seg[k * 2 + 1]);
  }
  void Add(int wishl, int wishr, long long x) {
    return Add(wishl, wishr, 1, 0, size, x);
  }
  void Move(int wishl, int wishr, long long x) {
    return Move(wishl, wishr, 1, 0, size, x);
  }
  long long Get(int wishl, int wishr, int k, int watchl, int watchr) {
    long long lval, rval;
    if (wishr <= watchl || watchr <= wishl) return -INF;
    if (wishl <= watchl && watchr <= wishr) {
      LazyPropagate(k);
      return seg[k];
    }
    LazyPropagate(k);
    int mid = (watchl + watchr) / 2;
    lval = Get(wishl, wishr, k * 2, watchl, mid);
    rval = Get(wishl, wishr, k * 2 + 1, mid, watchr);
    return max(lval, rval);
  }
  long long Get(int wishl, int wishr) { return Get(wishl, wishr, 1, 0, size); }
};
int main() {
  scanf("%lld", &first);
  scanf("%d", &K);
  priority_queue<long long, vector<long long>, greater<long long>> R;
  priority_queue<pair<long long, long long>, vector<pair<long long, long long>>,
                 greater<pair<long long, long long>>>
      W;
  vector<long long> T, A;
  for (int(i) = 0; (i) < (K); ++(i)) {
    scanf("%lld", &rs[i]);
    R.push(rs[i]);
    T.emplace_back(rs[i]);
  }
  scanf("%d", &Q);
  for (int(i) = 0; (i) < (Q); ++(i)) {
    scanf("%lld%lld", &ts[i], &as[i]);
    A.emplace_back(as[i]);
    T.emplace_back(ts[i]);
    W.push(pair<long long, long long>(ts[i], i));
  }
  sort((A).begin(), (A).end());
  A.erase(unique((A).begin(), (A).end()), A.end());
  LazySeg seg(A);
  sort((T).begin(), (T).end());
  long long sgn = -1;
  long long prevt = 0;
  for (long long t : T) {
    seg.Add(0, A.size(), sgn * (t - prevt));
    if (sgn == -1) {
      int low = -1;
      int high = A.size();
      while (high - low > 1) {
        int mid = (high + low) / 2;
        long long val = seg.Get(mid, mid + 1);
        if (val <= 0)
          low = mid;
        else
          high = mid;
      }
      seg.Move(0, low + 1, 0);
    } else {
      int low = -1;
      int high = A.size();
      while (high - low > 1) {
        int mid = (high + low) / 2;
        long long val = seg.Get(mid, mid + 1);
        if (val >= first)
          high = mid;
        else
          low = mid;
      }
      seg.Move(high, A.size(), first);
    }
    while (!W.empty() && W.top().first == t) {
      int idx = W.top().second;
      W.pop();
      int k = lower_bound((A).begin(), (A).end(), as[idx]) - A.begin();
      ans[idx] = seg.Get(k, k + 1);
    }
    while (!R.empty() && R.top() == t) {
      sgn = -sgn;
      R.pop();
    }
    prevt = t;
  }
  for (int(i) = 0; (i) < (Q); ++(i)) {
    printf("%lld\n", ans[i]);
  }
}
