#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
const i64 MOD = 1e9 + 7;
const i64 INF = 1e18 + 7;
signed main() {
  int s, n;
  cin >> s >> n;
  vector<int> t(n);
  for (auto& x : t) cin >> x;
  int q;
  cin >> q;
  vector<int> p(q), a(q);
  for (int i = 0; i < q; ++i) cin >> p[i] >> a[i];
  vector<int> diff(n, t[0]);
  for (int i = 1; i < n; ++i) diff[i + 1] = t[i + 1] - t[i];
  auto f = [&](int x) {
    int ta = x, tb = s - x;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
      if (i & 1) {
        int d = min(tb, diff[i]);
        ta += d;
        tb -= d;
      } else {
        int d = min(ta, diff[i]);
        ta -= d;
        tb += d;
      }
      v[i] = ta;
    }
    return v;
  };
  vector<int> st_val = f(0);
  auto g = [&](int x) {
    auto v = f(x);
    for (int i = 0; i < n; ++i) v[i] -= st_val[i];
    return v;
  };
  vector<int> diff_b = g(s);
  int bound = 0;
  while (bound < n && diff_b[bound]) bound++;
  vector<int> c(bound, -1);
  auto h = [&](int x) {
    auto v = g(x);
    for (int i = 0; i < bound; ++i)
      if (v[i] && v[i] != diff_b[i]) c[i] = x - v[i];
    return v;
  };
  for (int i = 0; i < bound; ++i) {
    int st = i ? c[i - 1] : 0;
    int en = (i == bound - 1 || c[i + 1] == -1) ? s : min(c[i + 1] + 1, s);
    while (en - st > 1 && c[i] == -1) {
      auto v = h((st + en) / 2);
      (v[i] ? en : st) = (st + en) / 2;
    }
    if (c[i] == -1) c[i] = st;
  }
  for (auto& x : c) cout << x << " ";
  cout << endl;
  for (int i = 0; i < q; ++i) {
    int time_ind =
        distance(t.begin(), upper_bound(t.begin(), t.end(), p[i])) - 1;
    int time_diff = p[i] - (time_ind == -1 ? 0 : t[time_ind]);
    if (time_ind == -1) {
      cout << max(0, a[i] - p[i]) << endl;
      continue;
    }
    int ans =
        st_val[time_ind] + max(0, min(a[i] - c[time_ind], diff_b[time_ind]));
    cout << "kari : " << ans << " => ";
    ans = max(0, min(ans + (time_ind & 1 ? -time_diff : time_diff), s));
    cout << ans << endl;
    cout << "hoge : " << time_diff << endl;
  }
}
