#include <bits/stdc++.h>
const int N = 1e5 + 2;
int n, op, rev[N];
inline int nxi() {
  int x = 0;
  char c;
  while ((c = getchar()) > '9' || c < '0')
    ;
  while (x = x * 10 + c - 48, (c = getchar()) >= '0' && c <= '9')
    ;
  return x;
}
int main() {
  n = nxi(), op = nxi();
  for (int i = 1; i <= op; ++i) {
    rev[i] = nxi();
  }
  int q = nxi();
  std::sort(rev + 1, rev + op + 1);
  while (q--) {
    int p = 0, nw = 0, tp, t = nxi(), sa = nxi(), sb = n - sa;
    using std::min;
    for (int i = 1; i <= op && rev[i] < t; ++i) {
      if (nw) {
        tp = min(sb, rev[i] - p);
        sb -= tp;
        sa += tp;
      } else {
        tp = min(sa, rev[i] - p);
        sa -= tp;
        sb += tp;
      }
      p = rev[i];
      nw ^= 1;
    }
    if (nw) {
      tp = min(sb, t - p);
      sb -= tp;
      sa += tp;
    } else {
      tp = min(sa, t - p);
      sa -= tp;
      sb += tp;
    }
    printf("%d\n", sa);
  }
  return 0;
}
