#include <bits/stdc++.h>
using namespace std;
int main() {
  int X;
  int n, q;
  int r[100010], d[100010], d2[100010];
  int max_d2[100010];
  int t, a, dic[100010];
  pair<pair<int, int>, int> query[100010];
  scanf("%d%d", &X, &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", r + i);
  }
  scanf("%d", &q);
  int p = 0;
  for (int i = 0; i < q; i++) {
    scanf("%d%d", &t, &a);
    query[i] = {{a, t}, i};
    while (p < n && t > r[p]) p++;
    dic[i] = p;
  }
  sort(query, query + q);
  int now_a = 0;
  int last_r = 0;
  int left = 0;
  int now_d2 = 0;
  for (int i = 0; i < n; i++) {
    if (i % 2 == 0) {
      now_a = max(0, now_a - (r[i] - last_r));
      now_d2 -= r[i] - last_r;
    } else {
      now_a = min(X, now_a + (r[i] - last_r));
      now_d2 += r[i] - last_r;
    }
    last_r = r[i];
    d[i] = now_a;
    d2[i] = now_d2;
  }
  max_d2[0] = d2[0];
  for (int i = 0; i < n; i++) {
    max_d2[i] = max(max_d2[i - 1], d2[i]);
  }
  int ans[100010];
  int left_ri = 0;
  int last_a = 0;
  set<int> ss;
  priority_queue<pair<int, int> > pq;
  int min_ff = n;
  int l_ans[100010];
  for (int i = 0; i < q; i++) {
    a = query[i].first.first;
    int da = (a - last_a);
    t = query[i].first.second;
    int id = query[i].second;
    if (left + da < r[left_ri]) {
      left += da;
    } else {
      while (left_ri < n && d2[left_ri] + a >= 0) {
        pq.push({d2[left_ri], left_ri});
        left_ri++;
        left = r[left_ri] + (d2[left_ri] + a);
      }
    }
    while (pq.size() && pq.top().second > min_ff) pq.pop();
    while (pq.size() && pq.top().first + a >= X) {
      int pl = pq.top().second;
      int pr = min_ff;
      ss.insert(r[pq.top().second]);
      min_ff = pq.top().second;
      pq.pop();
      now_a = X;
      for (int j = pl + 1; j <= pr; j++) {
        if (j % 2 == 0) {
          now_a = max(0, now_a - (r[j] - r[j - 1]));
        } else {
          now_a = min(X, now_a + (r[j] - r[j - 1]));
        }
        l_ans[j] = now_a;
      }
      while (pq.size() && pq.top().second > min_ff) pq.pop();
    }
    if (min_ff < dic[id] - 1) {
      if (dic[id] % 2 == 0) {
        ans[id] = max(0, l_ans[dic[id] - 1] - (t - r[dic[id] - 1]));
      } else {
        ans[id] = min(X, l_ans[dic[id] - 1] + (t - r[dic[id] - 1]));
      }
    } else if (left_ri < dic[id]) {
      if (dic[id] - 1 == -1) {
        ans[id] = max(0, a - t);
      } else {
        if (dic[id] % 2 == 0) {
          ans[id] = max(0, d[dic[id] - 1] - (t - r[dic[id] - 1]));
        } else {
          ans[id] = min(X, d[dic[id] - 1] + (t - r[dic[id] - 1]));
        }
      }
    } else {
      if (dic[id] % 2 == 0)
        ans[id] = max(0, a + d2[dic[id] - 1] - (t - r[dic[id] - 1]));
      else
        ans[id] = min(X, a + d2[dic[id] - 1] + (t - r[dic[id] - 1]));
    }
  }
  for (int i = 0; i < q; i++) {
    printf("%d\n", ans[i]);
  }
  return 0;
}
