#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int ST_ADD = 0x00;
const int ST_SET = 0x01;
int R;
struct Segment_Tree {
  struct TreeNode {
    bool pA, pS;
    int mx, toAdd, toSet;
    TreeNode() {
      pA = pS = 0;
      mx = toAdd = toSet = 0;
    }
  } st[N << 2];
  void push(int x, int lx, int rx) {
    if (st[x].pS) {
      st[x].pA = 0;
      st[x].mx = st[x].toSet;
      if (lx < rx) {
        st[x + x].pA = st[x + 1 + x].pA = 0;
        st[x + x].pS = st[x + 1 + x].pS = 1;
        st[x + x].toSet = st[x].toSet;
        st[x + 1 + x].toSet = st[x].toSet;
      }
      st[x].pS = 0;
    } else if (st[x].pA) {
      st[x].mx += st[x].toAdd;
      if (lx < rx) {
        if (st[x + x].pS) {
          st[x + x].toSet += st[x].toAdd;
        } else if (st[x + x].pA) {
          st[x + x].toAdd += st[x].toAdd;
        } else {
          st[x + x].pA = 1;
          st[x + x].toAdd = st[x].toAdd;
        }
        if (st[x + 1 + x].pS) {
          st[x + 1 + x].toSet += st[x].toAdd;
        } else if (st[x + 1 + x].pA) {
          st[x + 1 + x].toAdd += st[x].toAdd;
        } else {
          st[x + 1 + x].pA = 1;
          st[x + 1 + x].toAdd = st[x].toAdd;
        }
      }
      st[x].pA = 0;
    }
  }
  int u, v, ty, val;
  void upd(int x = 1, int lx = 1, int rx = R) {
    push(x, lx, rx);
    if (lx > v or rx < u) return;
    if (u <= lx and rx <= v) {
      if (ty == ST_ADD) {
        st[x].pA = 1;
        st[x].toAdd = val;
      } else if (ty == ST_SET) {
        st[x].pS = 1;
        st[x].toSet = val;
      }
      return;
    }
    int mid = (lx + rx) / 2;
    upd(x + x, lx, mid);
    upd(x + 1 + x, mid + 1, rx);
    st[x].mx = max(st[x + x].mx, st[x + 1 + x].mx);
  }
  void update(int _u, int _v, int _ty, int _val) {
    u = _u;
    v = _v;
    ty = _ty;
    val = _val;
    upd();
  }
  int qry(int x = 1, int lx = 1, int rx = R) {
    push(x, lx, rx);
    if (lx == rx) return st[x].mx;
    int mid = (lx + rx) / 2;
    if (u <= mid) return qry(x + x, lx, mid);
    return qry(x + 1 + x, mid + 1, rx);
  }
  int query(int pos) {
    u = pos;
    return qry();
  }
  int upbd(int x = 1, int lx = 1, int rx = R) {
    push(x, lx, rx);
    if (lx == rx) {
      if (st[x].mx <= val) return 1;
      return 0;
    }
    int mid = (lx + rx) / 2;
    push(x + x, lx, mid);
    push(x + 1 + x, mid + 1, rx);
    if (st[x + x].mx <= val) return mid - lx + 1 + upbd(x + 1 + x, mid + 1, rx);
    return upbd(x + x, lx, mid);
  }
  int upper_bound(int cut) {
    val = cut;
    return upbd();
  }
  int lwbd(int x = 1, int lx = 1, int rx = R) {
    push(x, lx, rx);
    if (lx == rx) {
      if (st[x].mx >= val) return 1;
      return 0;
    }
    int mid = (lx + rx) / 2;
    push(x + x, lx, mid);
    push(x + 1 + x, mid + 1, rx);
    if (st[x + x].mx < val) return lwbd(x + 1 + x, mid + 1, rx);
    return rx - mid + lwbd(x + x, lx, mid);
  }
  int lower_bound(int cut) {
    val = cut;
    return lwbd();
  }
} T;
int X, K, r[N], Q, t[N], a[N], rev[N], ans[N];
pair<int, int> temp[N], foo[N];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> X >> K;
  for (int i = 1; i <= K; i++) cin >> r[i];
  cin >> Q;
  R = Q;
  for (int q = 1; q <= Q; q++) {
    cin >> t[q] >> a[q];
    temp[q] = {a[q], q};
    foo[q] = {t[q], q};
  }
  sort(temp + 1, temp + 1 + Q);
  for (int i = 1; i <= Q; i++) {
    T.update(i, i, ST_SET, temp[i].first);
    rev[temp[i].second] = i;
  }
  sort(foo + 1, foo + 1 + Q);
  int lpt = 1;
  int timer = 0;
  bool dec = 1;
  r[K + 1] = 2e9;
  for (int i = 1; i <= K; i++) {
    for (; lpt <= Q and timer <= foo[lpt].first and foo[lpt].first < r[i];
         lpt++) {
      int idx = foo[lpt].second;
      int Tidx = rev[idx];
      int val = T.query(Tidx);
      int qDelta = foo[lpt].first - timer;
      if (dec) {
        ans[idx] = max(val - qDelta, 0);
      } else {
        ans[idx] = min(val + qDelta, X);
      }
    }
    int delta = r[i] - timer;
    if (dec) {
      int idx = T.upper_bound(delta);
      T.update(1, idx, ST_SET, 0);
      T.update(idx + 1, Q, ST_ADD, -delta);
    } else {
      int idx = T.lower_bound(X - delta);
      T.update(Q + 1 - idx, Q, ST_SET, X);
      T.update(1, Q - idx, ST_ADD, delta);
    }
    timer = r[i];
    dec ^= 1;
  }
  for (; lpt <= Q; lpt++) {
    int idx = foo[lpt].second;
    int Tidx = rev[idx];
    int val = T.query(Tidx);
    int qDelta = foo[lpt].first - timer;
    if (dec) {
      ans[idx] = max(val - qDelta, 0);
    } else {
      ans[idx] = min(val + qDelta, X);
    }
  }
  for (int i = 1; i <= Q; i++) cout << ans[i] << '\n';
  return 0;
};
