#include <bits/stdc++.h>
int X, K;
int r[100010];
int Q;
int t[100010], a[100010];
int idxt[100010], idxa[100010];
int res[100010];
int left, right;
int aia[100010];
int cmpt(const void *aa, const void *bb) {
  int i1 = *((int *)aa);
  int i2 = *((int *)bb);
  return t[i1] - t[i2];
}
int cmpa(const void *aa, const void *bb) {
  int i1 = *((int *)aa);
  int i2 = *((int *)bb);
  return a[i1] - a[i2];
}
int bsrch_l(int ll, int rr, int val) {
  int mm;
  while (ll < rr) {
    mm = (ll + rr) / 2;
    if (a[idxa[mm]] >= val)
      rr = mm;
    else
      ll = mm + 1;
  }
  return ll;
}
void solve() {
  int i, j;
  for (i = 0; i < Q; i++) idxt[i] = i;
  qsort(idxt, Q, sizeof(int), cmpt);
  for (i = 0; i < Q; i++) idxa[i] = i;
  qsort(idxa, Q, sizeof(int), cmpa);
  for (i = 0; i < Q; i++) {
    aia[idxa[i]] = i;
  }
  int addv = 0;
  int l2 = 0, r2 = Q;
  j = 0;
  while (j < Q && r[0] >= t[idxt[j]]) {
    if (a[idxt[j]] <= t[idxt[j]])
      res[idxt[j]] = 0;
    else
      res[idxt[j]] = a[idxt[j]] - t[idxt[j]];
    j++;
  }
  l2 = bsrch_l(l2, r2, r[0] + 1);
  addv -= r[0];
  left = 0;
  right = X;
  for (i = 1; i < K + 1; i++) {
    while (j < Q && ((i < K && r[i] >= t[idxt[j]]) || (i == K))) {
      if (i % 2 == 0) {
        if (aia[idxt[j]] < l2) {
          res[idxt[j]] = left - (t[idxt[j]] - r[i - 1]);
        } else if (aia[idxt[j]] >= r2) {
          res[idxt[j]] = right - (t[idxt[j]] - r[i - 1]);
        } else {
          res[idxt[j]] = a[idxt[j]] + addv - (t[idxt[j]] - r[i - 1]);
        }
        if (res[idxt[j]] < 0) res[idxt[j]] = 0;
      } else {
        if (aia[idxt[j]] < l2) {
          res[idxt[j]] = left + (t[idxt[j]] - r[i - 1]);
        } else if (aia[idxt[j]] >= r2) {
          res[idxt[j]] = right + (t[idxt[j]] - r[i - 1]);
        } else {
          res[idxt[j]] = a[idxt[j]] + addv + (t[idxt[j]] - r[i - 1]);
        }
        if (res[idxt[j]] > X) res[idxt[j]] = X;
      }
      j++;
    }
    if (i == K) break;
    if (i % 2 == 0) {
      l2 = bsrch_l(l2, r2, r[i] - r[i - 1] + 1);
      right -= r[i] - r[i - 1];
      if (right < 0) right = 0;
      left -= r[i] - r[i - 1];
      if (left < 0) left = 0;
      addv -= r[i] - r[i - 1];
    } else {
      r2 = bsrch_l(l2, r2, X - (r[i] - r[i - 1]));
      left += r[i] - r[i - 1];
      if (left > X) left = X;
      right += r[i] - r[i - 1];
      if (right > X) right = X;
      addv += r[i] - r[i - 1];
    }
  }
  for (i = 0; i < Q; i++) printf("%d\n", res[i]);
}
int main() {
  int i;
  scanf("%d%d", &X, &K);
  for (i = 0; i < K; i++) scanf("%d", &r[i]);
  scanf("%d", &Q);
  for (i = 0; i < Q; i++) {
    scanf("%d%d", &t[i], &a[i]);
  }
  solve();
  return 0;
}
