#include <bits/stdc++.h>
using namespace std;
long long int t[3][100005];
map<long long int, int> m1;
long long int s[100005];
int main() {
  long long int x, m, q;
  long long int a, b, c, d;
  int i, j, k;
  cin >> x >> m;
  m1[0] = 0;
  m1[(1 << 30)] = 0;
  t[1][0] = x;
  for (i = 0, a = 0; i < m; i++, a = b) {
    cin >> b;
    m1[b] = i + 1;
    if (i % 2 == 1) {
      t[2][i + 1] = t[2][i] + b - a;
      if (t[2][i + 1] > x)
        t[0][i + 1] = x, t[2][i + 1] = x;
      else
        t[0][i + 1] = t[0][i];
      c = t[2][i + 1] + t[1][i] - t[0][i];
      if (c > x)
        t[1][i + 1] = t[1][i] - c + x;
      else
        t[1][i + 1] = t[1][i];
    } else {
      t[2][i + 1] = t[2][i] - b + a;
      if (t[2][i + 1] < 0)
        t[0][i + 1] = t[0][i] - t[2][i + 1], t[2][i + 1] = 0;
      else
        t[0][i + 1] = t[0][i];
      t[1][i + 1] = t[1][i];
    }
  }
  cin >> q;
  for (i = 0; i < q; i++) {
    cin >> a >> b;
    auto itr = m1.upper_bound(a);
    itr--;
    c = itr->second;
    if (b <= t[0][c])
      d = t[2][c];
    else if (b >= t[1][c])
      d = t[2][c] + t[1][c] - t[0][c];
    else
      d = t[2][c] + b - t[0][c];
    if (c % 2 == 0)
      d -= a - (itr->first);
    else
      d += a - (itr->first);
    if (d > x) d = x;
    if (d < 0) d = 0;
    s[i] = d;
  }
  for (i = 0; i < q; i++) {
    cout << s[i] << endl;
  }
  return 0;
}
