#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 500;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int LOG = 20;
const int OFF = 1 << LOG;
struct queryy {
  int first, second, i;
};
bool cmp(queryy A, queryy B) { return A.first < B.first; }
int tour[3 * OFF], prop1[3 * OFF], prop2[3 * OFF], sol[2 * OFF];
int X, n, t, q, y;
vector<int> a;
vector<int> r;
vector<queryy> qu;
void refresh(int i) {
  if (i >= 2 * OFF) return;
  if (prop1[i] == 0 && prop2[i] == -1) return;
  if (prop2[i] != -1) tour[i] = prop2[i];
  tour[i] += prop1[i];
  if (i < OFF) {
    prop1[2 * i] += prop1[i];
    if (prop2[i] != -1) {
      prop2[2 * i] = prop2[i];
      prop1[2 * i + 1] = 0;
    }
    prop1[2 * i + 1] += prop1[i];
    if (prop2[i] != -1) {
      prop2[2 * i + 1] = prop2[i];
      prop1[2 * i + 1] = 0;
    }
  }
  prop1[i] = 0;
  prop2[i] = -1;
}
void update(int i, int a, int b, int lo, int hi, int x, int y) {
  refresh(i);
  refresh(2 * i);
  refresh(2 * i + 1);
  if (hi < lo) return;
  if (lo <= a && b <= hi) {
    prop1[i] += x;
    if (y >= 0) prop2[i] = y;
    refresh(i);
    return;
  }
  if (a > hi || b < lo) return;
  if (i >= OFF) return;
  update(2 * i, a, (a + b) / 2, lo, hi, x, y);
  update(2 * i + 1, (a + b + 2) / 2, b, lo, hi, x, y);
  tour[i] = max(tour[2 * i], tour[2 * i + 1]);
}
int query(int i, int a, int b, int lo, int hi) {
  refresh(i);
  refresh(2 * i);
  refresh(2 * i + 1);
  if (lo <= a && b <= hi) return tour[i];
  if (a > hi || b < lo) return 0;
  return max(query(2 * i, a, (a + b) / 2, lo, hi),
             query(2 * i + 1, (a + b + 2) / 2, b, lo, hi));
}
int tourbin(int i, int x) {
  refresh(i);
  refresh(2 * i);
  refresh(2 * i + 1);
  if (i >= OFF) return i - OFF;
  int l = tour[2 * i];
  int r = tour[2 * i + 1];
  if (l >= x) {
    return tourbin(2 * i, x);
  }
  return tourbin(2 * i + 1, x);
}
int main() {
  memset(prop2, -1, sizeof(prop2));
  scanf("%d %d", &X, &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &y);
    r.push_back(y);
  }
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    int c, d;
    scanf("%d%d", &c, &d);
    queryy nw;
    nw.first = c;
    nw.second = d;
    nw.i = i;
    qu.push_back(nw);
    a.push_back(d);
  }
  sort(a.begin(), a.end());
  int m = a.size();
  for (int i = OFF; i < OFF + m; i++) {
    tour[i] = a[i - OFF];
  }
  for (int i = OFF - 1; i; i--) {
    tour[i] = max(tour[2 * i], tour[2 * i + 1]);
  }
  r.push_back(0);
  sort(r.begin(), r.end());
  sort(qu.begin(), qu.end(), cmp);
  r.push_back(0x3f3f3f3f);
  int sm = 0, j = 0, lst = 0;
  for (int i = 0; i < n + 1; i++) {
    if (sm) {
      int ind = tourbin(1, r[i] - lst);
      update(1, 0, OFF - 1, ind, m - 1, -(r[i] - lst), -1);
      update(1, 0, OFF - 1, 0, ind - 1, 0, 0);
    } else {
      int ind = tourbin(1, X - (r[i] - lst));
      update(1, 0, OFF - 1, ind, m - 1, 0, X);
      update(1, 0, OFF - 1, 0, ind - 1, r[i] - lst, -1);
    }
    while (j < qu.size() && qu[j].first >= r[i] && qu[j].first < r[i + 1]) {
      int ind = lower_bound(a.begin(), a.end(), qu[j].second) - a.begin();
      int kol = query(1, 0, OFF - 1, ind, ind);
      int lft = qu[j].first - r[i];
      if (sm)
        kol = min(kol + lft, X);
      else
        kol = max(kol - lft, 0);
      sol[qu[j].i] = kol;
      j++;
    }
    sm = !sm;
    lst = r[i];
  }
  for (int i = 0; i < q; i++) {
    printf("%d\n", sol[i]);
  }
}
