#include <bits/stdc++.h>
using namespace std;
int rangetree[100000][3];
void push(int curr) {
  if (rangetree[curr][2]) {
    rangetree[2 * curr][2] = rangetree[2 * curr + 1][2] = 1;
    rangetree[2 * curr][1] = rangetree[2 * curr + 1][1] = rangetree[curr][1];
    rangetree[2 * curr][0] = rangetree[2 * curr + 1][0] = rangetree[curr][0];
  } else {
    rangetree[2 * curr][1] += rangetree[curr][1];
    rangetree[2 * curr + 1][1] += rangetree[curr][1];
    rangetree[2 * curr][0] += rangetree[curr][1];
    rangetree[2 * curr + 1][0] += rangetree[curr][1];
  }
  rangetree[curr][2] = rangetree[curr][1] = 0;
}
void update(int start, int end, int val, bool set, int curr = 1, int cstart = 0,
            int cend = 100010) {
  if (start <= cstart && cend <= end) {
    if (set) {
      rangetree[curr][2] = true;
      rangetree[curr][1] = rangetree[curr][0] = val;
    } else {
      rangetree[curr][0] += val;
      rangetree[curr][1] += val;
    }
    return;
  }
  push(curr);
  int mid = (cstart + cend) / 2;
  if (end <= mid)
    update(start, end, val, set, 2 * curr, cstart, mid);
  else if (start > mid)
    update(start, end, val, set, 2 * curr + 1, mid + 1, cend);
  else {
    update(start, end, val, set, 2 * curr, cstart, mid);
    update(start, end, val, set, 2 * curr + 1, mid + 1, cend);
  }
  rangetree[curr][0] = max(rangetree[2 * curr][0], rangetree[2 * curr + 1][0]);
}
int firstgreater(int val, int curr = 1, int cstart = 0, int cend = 100010) {
  if (cstart == cend) return cstart;
  push(curr);
  int mid = (cstart + cend) / 2;
  if (rangetree[2 * curr][0] >= val)
    return firstgreater(val, 2 * curr, cstart, mid);
  else
    return firstgreater(val, 2 * curr + 1, mid + 1, cend);
}
int query(int node, int curr = 1, int cstart = 0, int cend = 100010) {
  if (cstart == cend) return rangetree[curr][0];
  push(curr);
  int mid = (cstart + cend) / 2;
  if (node <= mid)
    return query(node, 2 * curr, cstart, mid);
  else
    return query(node, 2 * curr + 1, mid + 1, cend);
}
map<int, int> compress;
map<pair<int, int>, int> ans;
int k, q, flips[100010], x;
pair<int, int> queries[100010];
set<pair<int, int> > inorder;
bool status;
int pretime;
int main() {
  scanf("%d%d", &x, &k);
  for (int i = 0; i < k; i++) scanf("%d", &flips[i]);
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    scanf("%d%d", &queries[i].first, &queries[i].second);
    compress[queries[i].second] = 0;
    inorder.insert(make_pair(queries[i].first, queries[i].second));
  }
  int i = 1;
  for (auto it = compress.begin(); it != compress.end(); ++it) {
    update(i, i, it->first, true);
    it->second = i++;
  }
  auto it = inorder.begin();
  for (int i = 0; i < k; i++) {
    int t = flips[i];
    while (it != inorder.end() && it->first < flips[i]) {
      int pos = compress.find(it->second)->second;
      int val = query(pos);
      if (status) {
        val += it->first - pretime;
      } else
        val -= it->first - pretime;
      val = min(val, x);
      val = max(val, 0);
      ans[*it] = val;
      it++;
    }
    if (!status) {
      int f = firstgreater(t - pretime);
      if (f) update(0, f - 1, 0, 1);
      if (f != 100010) update(f, 100000, -(t - pretime), 0);
    } else {
      int f = firstgreater(x - (t - pretime));
      if (f != 100010) update(f, 100000, x, 1);
      if (f) update(0, f - 1, (t - pretime), 0);
    }
    status = !status;
    pretime = t;
  }
  while (it != inorder.end()) {
    int pos = compress.find(it->second)->second;
    int val = query(pos);
    if (status) {
      val += it->first - pretime;
    } else
      val -= it->first - pretime;
    val = min(val, x);
    val = max(val, 0);
    ans[*it] = val;
    it++;
  }
  for (int i = 0; i < q; i++) {
    printf("%d\n", ans[queries[i]]);
  }
}
