#include <bits/stdc++.h>
const int md = 1e9 + 7;
using namespace std;
struct eve {
  int l, a, r, b;
  bool inc;
  eve(int l = 0, int a = 0, int r = 0, int b = 0) : l(l), a(a), r(r), b(b){};
  int eval(int x) {
    if (x <= l) return a;
    if (x >= r) return b;
    return a + (x - l);
  }
};
int compute(int lim, int x, int t, bool inc) {
  if (inc)
    return min(lim, x + t);
  else
    return max(0, x - t);
}
int x, k, q, r[100003];
map<int, eve> m;
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> x >> k;
  r[0] = 0;
  for (int i = 1; i <= k; i++) cin >> r[i];
  eve prev = eve(0, 0, x, x);
  prev.inc = false;
  m[0] = prev;
  for (int i = 1; i <= k; i++) {
    int diff = r[i] - r[i - 1], diff2 = diff;
    bool dec = (i & 1);
    eve e = prev;
    int preva = e.a, prevb = e.b;
    if (dec) {
      e.a = max(0, e.a - diff);
      diff -= (preva - e.a);
      e.l = min(x, e.l + diff);
      diff = diff2;
      e.b = max(0, e.b - diff);
      diff -= (prevb - e.b);
      e.r = max(0, e.r - diff);
      if (e.l > e.r) e.l = e.r;
    } else {
      e.a = min(x, e.a + diff);
      diff -= (e.a - preva);
      e.l = min(x, e.l + diff);
      diff = diff2;
      e.b = min(x, e.b + diff);
      diff -= (e.b - prevb);
      e.r = min(x, e.r + diff);
    }
    e.inc = !prev.inc;
    prev = e;
    m[r[i]] = prev;
  }
  cin >> q;
  int p1, p2;
  while (q--) {
    cin >> p1 >> p2;
    auto it = m.upper_bound(p1);
    it--;
    eve e = it->second;
    int st = it->first;
    int curr = e.eval(p2);
    cout << compute(x, curr, p1 - st, e.inc) << '\n';
  }
}
