#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
const long long oo = 1e18;
const int N = 200011;
const int MX = 19;
int x, k, r[N], q;
map<int, int> org, sign;
vector<int> ac;
pair<int, int> qu[N];
long long seg[N];
map<pair<int, int>, long long> ans;
vector<int> da;
vector<pair<int, long long> > lzy[N];
void ps(pair<int, long long> cur, int n) {
  if (lzy[n].size() && lzy[n].back().first > 1) {
    cur.second += lzy[n].back().second;
    lzy[n].pop_back();
  }
  lzy[n].push_back(cur);
}
void push(int n, int second, int e) {
  if (!lzy[n].size()) return;
  for (int i = 0; i < lzy[n].size(); ++i) {
    int type = lzy[n][i].first;
    if (type == 0 || type == 1) {
      seg[n] = type * ((1ll) * e - second + 1) * x;
      if (second != e) {
        lzy[2 * n].clear();
        lzy[2 * n + 1].clear();
        lzy[2 * n].push_back(lzy[n][i]);
        lzy[2 * n + 1].push_back(lzy[n][i]);
      }
    } else {
      seg[n] += ((1ll) * e - second + 1) * lzy[n][i].second;
      if (second != e) {
        ps(lzy[n][i], 2 * n);
        ps(lzy[n][i], 2 * n + 1);
      }
    }
  }
  lzy[n].clear();
}
void update(int type, int n, int second, int e, int l, int r, long long val) {
  if (l > r) return;
  push(n, second, e);
  if (second > r || e < l) return;
  if (second >= l && e <= r) {
    lzy[n].push_back(make_pair(type, 1ll * val));
    push(n, second, e);
    return;
  }
  update(type, 2 * n, second, (second + e) / 2, l, r, val);
  update(type, 2 * n + 1, (second + e) / 2 + 1, e, l, r, val);
  seg[n] = seg[2 * n] + seg[2 * n + 1];
}
int idx(int ti) {
  return lower_bound(da.begin(), da.end(), ti) - da.begin() + 1;
}
long long get(int n, int second, int e, int at) {
  push(n, second, e);
  if (second > at || e < at) return 0;
  if (second == e) {
    return seg[n];
  }
  return get(2 * n, second, (second + e) / 2, at) +
         get(2 * n + 1, (second + e) / 2 + 1, e, at);
}
int lb(int x) {
  int lo = 1, hi = da.size();
  int best = da.size() + 1;
  while (lo <= hi) {
    int mid = (lo + hi) / 2;
    if (get(1, 1, da.size(), mid) >= x) {
      best = mid;
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  return best;
}
int main() {
  scanf("%d%d", &x, &k);
  for (int i = 0; i < k; i++) {
    scanf("%d", &r[i]);
    org[r[i]] = 1;
    ac.push_back(r[i]);
  }
  scanf("%d", &q);
  for (int i = 0; i < q; ++i) {
    scanf("%d%d", &qu[i].first, &qu[i].second);
    ac.push_back(qu[i].first);
    da.push_back(qu[i].second);
  }
  sort(ac.begin(), ac.end());
  ac.resize(unique(ac.begin(), ac.end()) - ac.begin());
  sort(da.begin(), da.end());
  da.resize(unique(da.begin(), da.end()) - da.begin());
  for (int i = 0; i < da.size(); ++i) {
    update(3, 1, 1, da.size(), idx(da[i]), idx(da[i]), da[i]);
  }
  bool add = 0;
  for (int i = 0; i < ac.size(); ++i) {
    sign[ac[i]] = add;
    if (org[ac[i]]) add = !add;
  }
  int id = 0;
  for (int i = 0; i < ac.size(); ++i) {
    int amount = ac[i] - (i ? ac[i - 1] : 0);
    if (!sign[ac[i]]) {
      int mf = lb(amount);
      update(3, 1, 1, da.size(), mf, da.size(), -amount);
      update(0, 1, 1, da.size(), 1, mf - 1, 0ll);
    } else {
      int mf = lb(x - amount);
      update(3, 1, 1, da.size(), 1, mf - 1, amount);
      update(1, 1, 1, da.size(), mf, da.size(), 0ll);
    }
    while (id < q && qu[id].first == ac[i]) {
      ans[qu[id]] = get(1, 1, da.size(), idx(qu[id].second));
      id++;
    }
  }
  for (int i = 0; i < q; ++i) {
    printf("%d\n", (int)ans[qu[i]]);
  }
  return 0;
}
