#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int inf = 2e9;
int mx[N << 2], mn[N << 2], lazy_to[N << 2], lazy_add[N << 2];
int id[N];
int t[N], a[N], r[N], ans[N], tab[N];
int X, q, k;
inline void pushup(int x) {
  mx[x] = max(mx[(x << 1)], mx[(x << 1 | 1)]);
  mn[x] = min(mn[(x << 1)], mn[(x << 1 | 1)]);
}
inline void pushdown(int x) {
  if (lazy_to[x] == inf) {
    if (!lazy_add[x]) return;
    if (lazy_to[(x << 1)] == inf)
      lazy_add[(x << 1)] += lazy_add[x];
    else
      lazy_to[(x << 1)] += lazy_add[x];
    if (lazy_to[(x << 1 | 1)] == inf)
      lazy_add[(x << 1 | 1)] += lazy_add[x];
    else
      lazy_to[(x << 1 | 1)] += lazy_add[x];
    mx[(x << 1)] += lazy_add[x];
    mn[(x << 1)] += lazy_add[x];
  } else {
    lazy_to[(x << 1)] = lazy_to[(x << 1 | 1)] = mx[(x << 1)] =
        mx[(x << 1 | 1)] = mn[(x << 1)] = mn[(x << 1 | 1)] = lazy_to[x];
    lazy_add[(x << 1)] = lazy_add[(x << 1 | 1)] = 0;
  }
  lazy_to[x] = inf;
  lazy_add[x] = 0;
}
inline void build(int x, int l, int r) {
  lazy_to[x] = inf;
  if (l == r) {
    mx[x] = mn[x] = tab[l];
    return;
  }
  int mid = (l + r) >> 1;
  build((x << 1), l, mid);
  build((x << 1 | 1), mid + 1, r);
  pushup(x);
}
inline void adjust_to_zero(int x, int l, int r) {
  if (mx[x] <= 0) {
    lazy_to[x] = lazy_add[x] = mx[x] = mn[x] = 0;
    return;
  }
  pushdown(x);
  int mid = (l + r) >> 1;
  if (mn[(x << 1)] < 0) adjust_to_zero((x << 1), l, mid);
  if (mn[(x << 1 | 1)] < 0) adjust_to_zero((x << 1 | 1), mid + 1, r);
  pushup(x);
}
inline void adjust_to_x(int x, int l, int r) {
  if (mn[x] >= X) {
    lazy_to[x] = mx[x] = mn[x] = X;
    lazy_add[x] = 0;
    return;
  }
  pushdown(x);
  int mid = (l + r) >> 1;
  if (mx[(x << 1)] > X) adjust_to_x((x << 1), l, mid);
  if (mx[(x << 1 | 1)] > X) adjust_to_x((x << 1 | 1), mid + 1, r);
  pushup(x);
}
inline int query(int x, int l, int r, int pos) {
  if (l == r) return mx[x];
  pushdown(x);
  int mid = (l + r) >> 1, ret;
  if (pos <= mid)
    ret = query((x << 1), l, mid, pos);
  else
    ret = query((x << 1 | 1), mid + 1, r, pos);
  pushup(x);
  return ret;
}
inline bool cmp(int a, int b) { return t[a] < t[b]; }
int main() {
  scanf("%d%d", &X, &k);
  for (int i = 1; i <= k; i++) scanf("%d", &r[i]);
  scanf("%d", &q);
  for (int i = 1; i <= q; id[i] = i, i++) {
    scanf("%d%d", &t[i], &a[i]);
    tab[i] = a[i];
  }
  sort(id + 1, id + q + 1, cmp);
  sort(tab + 1, tab + q + 1);
  if (t[id[q]] > r[k]) r[++k] = t[id[q]] + 1;
  build(1, 1, q);
  int pos = 1, tmp, ppp;
  for (int i = 1; i <= k && pos <= q; i++) {
    while (t[id[pos]] <= r[i] && pos <= q) {
      ppp = lower_bound(tab + 1, tab + q + 1, a[id[pos]]) - tab;
      tmp = query(1, 1, q, ppp);
      if (i & 1)
        ans[id[pos]] = max(tmp - (t[id[pos]] - r[i - 1]), 0);
      else
        ans[id[pos]] = min(tmp + (t[id[pos]] - r[i - 1]), X);
      pos++;
    }
    int ttt = r[i] - r[i - 1];
    if (i & 1) {
      mx[1] -= ttt;
      mn[1] -= ttt;
      if (lazy_to[1] == inf)
        lazy_add[1] -= ttt;
      else
        lazy_to[1] -= ttt, lazy_add[1] = 0;
      adjust_to_zero(1, 1, q);
    } else {
      mx[1] += ttt;
      mn[1] += ttt;
      if (lazy_to[1] == inf)
        lazy_add[1] += ttt;
      else
        lazy_to[1] += ttt, lazy_add[1] = 0;
      adjust_to_x(1, 1, q);
    }
  }
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
  return 0;
}
