#include <bits/stdc++.h>
using namespace std;
const long long inf = (long long)1e17;
class LeftHeap {
 public:
  pair<long long, int> key;
  int npl;
  LeftHeap *lson, *rson;
  LeftHeap() {
    lson = rson = 0;
    npl = 0;
  }
};
long long res[100005], x, p[100005], spT[2][200005][30], fp[200005],
    dlt[200005], s[200005], e[200005];
pair<int, int> qs[100005];
int n, q;
LeftHeap *cur[100005][2];
template <typename T>
T MAX(T a, T b) {
  return a > b ? a : b;
}
template <typename T>
T MIN(T a, T b) {
  return a < b ? a : b;
}
template <typename T>
T ABS(T a) {
  return a > 0 ? a : -a;
}
template <typename T>
void Swap(T &a, T &b) {
  T p = a;
  a = b;
  b = p;
}
LeftHeap *create(pair<long long, int> val) {
  LeftHeap *ret = new LeftHeap;
  ret->key = val;
  return ret;
}
inline int cal(LeftHeap *t) { return (t ? t->npl : 0); }
inline void restore(LeftHeap *t) {
  if (cal(t->lson) < cal(t->rson)) {
    swap(t->lson, t->rson);
  }
}
LeftHeap *merge(LeftHeap *a, LeftHeap *b) {
  if (!a || !b) return a ? a : b;
  if (a->key > b->key) swap(a, b);
  a->rson = merge(a->rson, b);
  restore(a);
  return a;
}
inline void popmin(LeftHeap *&P) {
  LeftHeap *ls = P->lson, *rs = P->rson;
  delete P;
  P = merge(ls, rs);
}
inline void insert(LeftHeap *&P, pair<long long, int> val) {
  P = merge(P, create(val));
}
void initalize(long long *arr, int len, int id) {
  int xb, x2;
  for (xb = 0; xb < 200005; xb++)
    fill(spT[id][xb], spT[id][xb] + 30, (id ? (-inf) : inf));
  for (xb = 0; xb < len; xb++) {
    spT[id][xb][0] = (long long)arr[xb];
  }
  for (x2 = 1; (1 << x2) <= len; x2++) {
    for (xb = 0; xb + (1 << x2) <= len; xb++) {
      if (id == 1)
        spT[id][xb][x2] =
            MAX(spT[id][xb][x2 - 1], spT[id][xb + (1 << (x2 - 1))][x2 - 1]);
      else
        spT[id][xb][x2] =
            MIN(spT[id][xb][x2 - 1], spT[id][xb + (1 << (x2 - 1))][x2 - 1]);
    }
  }
  fp[1] = 0;
  for (xb = 2; xb <= len; xb++) {
    fp[xb] = fp[xb - 1];
    while ((1 << fp[xb]) <= xb) fp[xb]++;
    fp[xb]--;
  }
}
inline long long Query(int F, int T, int id) {
  if (id == 1)
    return MAX(spT[id][F][fp[T - F + 1]],
               spT[id][T - (1 << fp[T - F + 1]) + 1][fp[T - F + 1]]);
  else
    return MIN(spT[id][F][fp[T - F + 1]],
               spT[id][T - (1 << fp[T - F + 1]) + 1][fp[T - F + 1]]);
}
inline int getn(int pos, long long val) {
  int low = pos, hig = n - 1, mid;
  if (pos > 0) val -= dlt[pos - 1];
  if ((long long)val + (long long)Query(pos, n - 1, 1) < (long long)x) return n;
  while (low < hig) {
    mid = ((low + hig) >> 1);
    if ((long long)val + (long long)Query(pos, mid, 1) >= (long long)x)
      hig = mid;
    else
      low = mid + 1;
  }
  return low;
}
inline int getz(int pos, long long val) {
  int low = pos, hig = n - 1, mid;
  if (pos > 0) val -= dlt[pos - 1];
  if ((long long)val + (long long)Query(pos, n - 1, 0) > 0LL) return n;
  while (low < hig) {
    mid = ((low + hig) >> 1);
    if ((long long)val + (long long)Query(pos, mid, 0) > 0LL)
      low = mid + 1;
    else
      hig = mid;
  }
  return low;
}
inline int fndp(long long val) {
  int low = 0, hig = n - 1, mid;
  if (val < p[0]) return -1;
  while (low < hig) {
    mid = (low + hig + 1) >> 1;
    if (p[mid] <= val)
      low = mid;
    else
      hig = mid - 1;
  }
  return low;
}
int main() {
  scanf("%I64d %d", &x, &n);
  int xb, x2;
  for (xb = 0; xb < n; xb++) scanf("%I64d", p + xb);
  p[n++] = 2000000007;
  scanf("%d", &q);
  for (xb = 0; xb < q; xb++) {
    scanf("%d%d", &qs[xb].first, &qs[xb].second);
  }
  for (xb = 0; xb < n; xb++) {
    dlt[xb] = p[xb] - (xb > 0 ? p[xb - 1] : 0);
    if (!(xb & 1)) dlt[xb] = -dlt[xb];
    s[xb] = (xb == 0 ? 0 : p[xb - 1]);
    e[xb] = p[xb] - 1;
  }
  for (xb = 1; xb < n; xb++) dlt[xb] += dlt[xb - 1];
  memset(cur, NULL, sizeof(cur));
  initalize(dlt, n, 0);
  initalize(dlt, n, 1);
  for (xb = 0; xb < q; xb++) {
    long long t = qs[xb].first, v = qs[xb].second;
    int vn = getn(0, v), vz = getz(0, v);
    if (p[MIN(vn, vz)] > t) {
      int ps = fndp(t);
      if (ps == -1)
        res[xb] = (long long)v - (long long)t;
      else
        res[xb] =
            (long long)v + (long long)dlt[ps] +
            (long long)((ps & 1LL) ? (-1LL) : 1LL) * (long long)(t - p[ps]);
    } else if (vn < vz) {
      insert(cur[vn][1], make_pair(t, xb));
    } else {
      insert(cur[vz][0], make_pair(t, xb));
    }
  }
  for (xb = 0; xb < n; xb++) {
    for (x2 = 0; x2 < 2; x2++) {
      if (cur[xb][x2]) {
        int vn = getn(xb + 1, (x2 ? (x) : 0)),
            vz = getz(xb + 1, (x2 ? (x) : 0)), nx = MIN(vn, vz),
            ny = (vn < vz) ? 1 : 0;
        while (cur[xb][x2]) {
          if (cur[xb][x2]->key.first < p[nx]) {
            int ps = fndp(cur[xb][x2]->key.first);
            res[cur[xb][x2]->key.second] =
                (long long)(x2 ? (x) : 0) + dlt[ps] +
                (long long)((ps & 1LL) ? (-1LL) : 1LL) *
                    (long long)((long long)cur[xb][x2]->key.first -
                                (long long)p[ps]) -
                dlt[xb];
            popmin(cur[xb][x2]);
          } else
            break;
        }
        cur[nx][ny] = merge(cur[nx][ny], cur[xb][x2]);
      }
    }
  }
  for (xb = 0; xb < q; xb++) {
    res[xb] = MIN(x, MAX(0LL, res[xb]));
    printf("%I64d\n", res[xb]);
  }
  return 0;
}
