#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int main() {
  ios::sync_with_stdio(false);
  int x, k, b[100005] = {}, q, z[100005] = {}, c = 1;
  pair<pair<int, int>, int> a[100005] = {};
  cin >> x >> k;
  int l = 0, r = x, d = 0, u = x;
  for (int i = 1; i <= k; i++) cin >> b[i];
  b[k + 1] = mod + mod;
  cin >> q;
  for (int i = 1; i <= q; i++)
    cin >> a[i].first.first >> a[i].first.second, a[i].second = i;
  sort(a + 1, a + q + 1);
  for (int i = 1; i <= k + 1; i++) {
    if (i % 2) {
      while (c <= q && a[c].first.first <= b[i]) {
        if (a[c].first.second >= l && a[c].first.second <= r)
          z[a[c].second] =
              max(0, d + a[c].first.second - l - a[c].first.first + b[i - 1]);
        else if (a[c].first.second < l)
          z[a[c].second] = max(0, d - a[c].first.first + b[i - 1]);
        else
          z[a[c].second] = max(0, u - a[c].first.first + b[i - 1]);
        c++;
      }
      if (b[i] - b[i - 1] < d) {
        d -= b[i] - b[i - 1];
        u -= b[i] - b[i - 1];
      } else if (b[i] - b[i - 1] < u) {
        l += b[i] - b[i - 1] - d;
        d = 0;
        u -= b[i] - b[i - 1];
      } else {
        l = r = d = u = 0;
      }
    } else {
      while (c <= q && a[c].first.first <= b[i]) {
        if (a[c].first.second >= l && a[c].first.second <= r)
          z[a[c].second] =
              min(x, d + a[c].first.second - l + a[c].first.first - b[i - 1]);
        else if (a[c].first.second < l)
          z[a[c].second] = min(x, d + a[c].first.first - b[i - 1]);
        else
          z[a[c].second] = min(x, u + a[c].first.first - b[i - 1]);
        c++;
      }
      if (b[i] - b[i - 1] < x - u) {
        d += b[i] - b[i - 1];
        u += b[i] - b[i - 1];
      } else if (b[i] - b[i - 1] < x - d) {
        d += b[i] - b[i - 1];
        r -= b[i] - b[i - 1] - x + u;
        u = x;
      }
    }
  }
  for (int i = 1; i <= q; i++) cout << z[i] << '\n';
}
