#include <bits/stdc++.h>
using namespace std;
struct data {
  int x, y, z;
  int operator<(const data& d) const { return y < d.y; }
} d[100100];
int n, X, K, Q, t[100100], a[100100], anses[100100], id[100100], s[100100 << 2];
int rev, mx[100100 << 2], mn[100100 << 2], ctg[100100 << 2], atg[100100 << 2],
    stg[100100];
vector<data> v[100100];
void pd(int o, int x) {
  if (stg[o] != -1) stg[x] = mx[x] = mn[x] = stg[o], atg[x] = ctg[x] = 0;
  if (ctg[o])
    ctg[x] ^= 1, swap(mx[x], mn[x]), atg[x] *= -1, mx[x] *= -1, mn[x] *= -1;
  if (atg[o]) atg[x] += atg[o], mx[x] += atg[o], mn[x] += atg[o];
}
void upd(int o) {
  mx[o] = max(mx[o << 1], mx[o << 1 | 1]);
  mn[o] = min(mn[o << 1], mn[o << 1 | 1]);
}
void clr(int o) { stg[o] = -1, ctg[o] = atg[o] = 0; }
void mdy(int o, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) {
    pd(0, o);
    return;
  }
  int mid = l + r >> 1;
  pd(o, o << 1), pd(o, o << 1 | 1), clr(o);
  if (ql <= mid) mdy(o << 1, l, mid, ql, qr);
  if (qr > mid) mdy(o << 1 | 1, mid + 1, r, ql, qr);
  upd(o);
}
int qry(int o, int l, int r, int x, int flag) {
  if (mx[o] < x) return flag ? r + 1 : l - 1;
  if (l == r) return l;
  int mid = l + r >> 1;
  pd(o, o << 1), pd(o, o << 1 | 1), clr(o);
  if (flag) {
    if (mx[o << 1] >= x)
      return qry(o << 1, l, mid, x, flag);
    else
      return qry(o << 1 | 1, mid + 1, r, x, flag);
  } else {
    if (mx[o << 1 | 1] >= x)
      return qry(o << 1 | 1, mid + 1, r, x, flag);
    else
      return qry(o << 1, l, mid, x, flag);
  }
}
void build(int o, int l, int r) {
  clr(o);
  if (l == r) {
    mx[o] = mn[o] = d[l].y;
    return;
  }
  int mid = l + r >> 1;
  build(o << 1, l, mid), build(o << 1 | 1, mid + 1, r), upd(o);
}
int _qry(int o, int l, int r, int x) {
  if (l == r) return mx[o];
  int mid = l + r >> 1;
  pd(o, o << 1), pd(o, o << 1 | 1), clr(o);
  if (x <= mid)
    return _qry(o << 1, l, mid, x);
  else
    return _qry(o << 1 | 1, mid + 1, r, x);
}
int main() {
  scanf("%d%d", &X, &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &t[i]);
  t[0] = 0;
  scanf("%d", &Q);
  for (int i = 1, ai, ti; i <= Q; ++i)
    scanf("%d%d", &ti, &ai), d[i] = data{ti, X - ai, i};
  sort(d + 1, d + Q + 1);
  for (int i = 1; i <= Q; ++i) id[d[i].z] = i;
  for (int i = 1; i <= Q; ++i)
    v[upper_bound(t, t + n + 1, d[i].x) - t - 1].push_back(d[i]);
  build(1, 1, Q);
  for (int i = 0, lst = 0; i <= n; ++i) {
    if (i & 1) {
      int l = qry(1, 1, Q, t[i] - lst, 0);
      if (l >= 1) clr(0), atg[0] = lst - t[i], mdy(1, 1, Q, 1, l);
      if (l < Q) clr(0), stg[0] = 0, mdy(1, 1, Q, l + 1, Q);
    } else {
      int l = qry(1, 1, Q, t[i] - lst, 1);
      if (l <= Q) clr(0), atg[0] = lst - t[i], mdy(1, 1, Q, l, Q);
      if (l > 1) clr(0), stg[0] = 0, mdy(1, 1, Q, 1, l - 1);
    }
    ctg[0] = 1, atg[0] = X, stg[0] = -1, mdy(1, 1, Q, 1, Q);
    for (int j = 0; j < v[i].size(); ++j)
      anses[v[i][j].z] =
          min(X, max(0, (~i & 1 ? _qry(1, 1, Q, id[v[i][j].z])
                                : X - _qry(1, 1, Q, id[v[i][j].z])) +
                            (i & 1 ? 1 : -1) * (v[i][j].x - t[i])));
    lst = t[i];
  }
  for (int i = 1; i <= Q; ++i) printf("%d\n", anses[i]);
}
