#include <bits/stdc++.h>
using namespace std;
int x;
int r[100000];
pair<int, int> a[100000];
int k, q;
int em[100000], fu[100000];
int diff[100000];
int firstEmpty;
int mm[100000], ma[100000];
int main() {
  firstEmpty = 2000000000;
  scanf("%lld\n%lld", &x, &k);
  for (int i = 0; i < k; i++) scanf("%d", r + i);
  scanf("%d", &q);
  for (int i = 0; i < q; i++) scanf("%d %d", &a[i].first, &a[i].second);
  em[0] = 0;
  fu[0] = x;
  for (int i = 1; i < k; i++) {
    if (i % 2 == 1) {
      em[i] = min(x, em[i - 1] + r[i] - r[i - 1]);
      fu[i] = min(x, fu[i - 1] + r[i] - r[i - 1]);
    } else {
      em[i] = max(0, em[i - 1] - r[i] + r[i - 1]);
      fu[i] = max(0, fu[i - 1] - r[i] + r[i - 1]);
    }
  }
  diff[0] = -r[0];
  for (int i = 1; i < k; i++) {
    if (i % 2 == 1) {
      diff[i] = min(x, diff[i - 1] + r[i] - r[i - 1]);
    } else {
      diff[i] = max(-x, diff[i - 1] - r[i] + r[i - 1]);
      if (diff[i] == -x) firstEmpty = min(firstEmpty, r[i]);
    }
  }
  mm[0] = -r[0];
  ma[0] = x - r[0];
  for (int i = 1; i < k; i++) mm[i] = min(mm[i - 1], diff[i]);
  for (int i = 1; i < k; i++) ma[i] = max(ma[i - 1], diff[i]);
  for (int i = 0; i < q; i++) {
    if (a[i].first < r[0]) {
      printf("%d\n", max(0, a[i].second - a[i].first));
      continue;
    }
    int long long = 0, rr = k - 1;
    int ans = 0;
    while (long long <= rr) {
      int mid = (long long + rr) / 2;
      if (r[mid] <= a[i].first) {
        ans = mid;
        long long = mid + 1;
      } else
        rr = mid - 1;
    }
    if (a[i].second + ma[ans] >= x) {
      if (ans % 2 == 0)
        printf("%d\n", min(x, fu[ans] + min(a[i].first - r[ans], x - fu[ans])));
      else
        printf("%d\n", max(0, fu[ans] - (a[i].first - r[ans])));
    } else if (a[i].second + mm[ans] >= 0) {
      if (ans % 2 == 0) {
        int cur = min(x, a[i].second + diff[ans]);
        printf("%d\n", min(x, cur + min(a[i].first - r[ans], x - cur)));
      } else {
        int cur = min(x, a[i].second + diff[ans]);
        printf("%d\n", max(0, cur - (a[i].first - r[ans])));
      }
    } else {
      if (ans % 2 == 0)
        printf("%d\n", min(x, em[ans] + min(a[i].first - r[ans], x - em[ans])));
      else
        printf("%d\n", max(0, em[ans] - (a[i].first - r[ans])));
    }
  }
  return 0;
}
