#include <bits/stdc++.h>
using namespace std;
int x, k, q;
int t[400010], tset[400010], tadd[400010];
int a[100010], r[100010];
struct query {
  int t, a, it;
  query(int t, int a, int it) : t(t), a(a), it(it) {}
};
vector<query> in;
void build(int v, int vl, int vr) {
  if (vl == vr) {
    t[v] = a[vl];
    return;
  }
  int vm = (vl + vr) >> 1;
  build(2 * v, vl, vm);
  build(2 * v + 1, vm + 1, vr);
  t[v] = t[2 * v] + t[2 * v + 1];
}
void push(int v, int vl, int vr) {
  if (tset[v] != -1) {
    t[v] = (vr - vl + 1) * tset[v];
    if (vl != vr) {
      tset[2 * v] = tset[v];
      tset[2 * v + 1] = tset[v];
    }
    tset[v] = -1;
  }
  if (tadd[v] != 0) {
    t[v] += (vr - vl + 1) * tadd[v];
    if (vl != vr) {
      tadd[2 * v] += tadd[v];
      tadd[2 * v + 1] += tadd[v];
    }
    tadd[v] = 0;
  }
}
void update(int v, int vl, int vr, int l, int r, int set, int add) {
  push(v, vl, vr);
  if (l > vr || r < vl) return;
  if (l <= vl && vr <= r) {
    tset[v] = set;
    tadd[v] += add;
    return;
  }
  int vm = (vl + vr) >> 1;
  update(2 * v, vl, vm, l, r, set, add);
  update(2 * v + 1, vm + 1, vr, l, r, set, add);
  t[v] = t[2 * v] + t[2 * v + 1];
}
int get(int v, int vl, int vr, int l, int r) {
  push(v, vl, vr);
  if (l > vr || r < vl) return 0;
  if (l <= vl && vr <= r) {
    return t[v];
  }
  int vm = (vl + vr) >> 1;
  int q1 = get(2 * v, vl, vm, l, r);
  int q2 = get(2 * v + 1, vm + 1, vr, l, r);
  return q1 + q2;
}
bool cmp(const query &lhs, const query &rhs) {
  if (lhs.a != rhs.a) return lhs.a < rhs.a;
  return lhs.t < rhs.t;
}
bool cmp2(const pair<pair<int, int>, int> lhs,
          const pair<pair<int, int>, int> rhs) {
  if (lhs.first.first != rhs.first.first)
    return lhs.first.first < rhs.first.first;
  return lhs.second > rhs.second;
}
vector<pair<pair<int, int>, int> > moments;
int ans[100010];
int change[100010];
int main() {
  ios_base::sync_with_stdio(0);
  for (int i = 0; i < 400000; i++) tset[i] = -1;
  cin >> x >> k;
  for (int i = 0; i < k; i++) {
    cin >> r[i];
  }
  cin >> q;
  for (int i = 0; i < q; i++) {
    int tq, ta;
    cin >> tq >> ta;
    in.push_back(query(tq, ta, i));
  }
  sort(in.begin(), in.end(), cmp);
  for (int i = 0; i < q; i++) {
    change[in[i].it] = i;
  }
  for (int i = 0; i < q; i++) {
    a[i] = in[i].a;
  }
  build(1, 0, q - 1);
  for (int i = 0; i < k; i++) {
    moments.push_back(make_pair(make_pair(r[i], -1), 1));
  }
  for (int i = 0; i < q; i++) {
    moments.push_back(make_pair(make_pair(in[i].t, in[i].it), 0));
  }
  moments.push_back(make_pair(make_pair(0, -1), 1));
  sort(moments.begin(), moments.end(), cmp2);
  int last = 0;
  int turn = 1;
  for (int i = 0; i < moments.size(); i++) {
    int len = moments[i].first.first - last;
    if (turn == 0) {
      int lo = -1, hi = q;
      while (lo != hi) {
        int mi = (lo + hi + 1) >> 1;
        if (get(1, 0, q - 1, mi, mi) - len > 0)
          hi = mi - 1;
        else
          lo = mi;
      }
      update(1, 0, q - 1, 0, lo, 0, 0);
      update(1, 0, q - 1, lo + 1, q - 1, -1, -len);
    } else {
      int lo = -1, hi = q;
      while (lo != hi) {
        int mi = (lo + hi + 1) >> 1;
        if (get(1, 0, q - 1, mi, mi) + len > x)
          hi = mi - 1;
        else
          lo = mi;
      }
      update(1, 0, q - 1, 0, lo, -1, len);
      update(1, 0, q - 1, lo + 1, q - 1, x, 0);
    }
    if (moments[i].second == 0) {
      int it = change[moments[i].first.second];
      ans[moments[i].first.second] = get(1, 0, q - 1, it, it);
    }
    if (moments[i].second == 1) {
      turn ^= 1;
    }
    last = moments[i].first.first;
  }
  for (int i = 0; i < q; i++) {
    cout << ans[i] << endl;
  }
  return 0;
}
