#include <bits/stdc++.h>
using namespace std;
template <typename T>
void chmax(T &x, const T &y) {
  if (x < y) x = y;
}
template <typename T>
void chmin(T &x, const T &y) {
  if (x > y) x = y;
}
const int N = 1e5 + 5, T = N * 2;
int X, qq[T], *q = qq + N;
long long qk[T], *k = qk + N, qb[T], *b = qb + N;
int head = 0, tail = 0;
long long adb = 0;
int r[N];
int t[N], a[N], ans[N];
vector<int> lk[N];
inline int F(int i, int x) { return k[i] * x + b[i] + adb; }
int qiu(int x) {
  int i = lower_bound(q + head, q + tail + 1, x) - q;
  return F(i, x);
}
void decrease(int x) {
  adb -= x;
  int nt = -1;
  while (head <= tail && F(head, q[head]) <= 0) {
    nt = q[head];
    ++head;
  }
  if (head <= tail && k[head]) chmax(nt, int(-(b[head] + adb) / k[head]));
  if (nt != -1) {
    --head;
    q[head] = nt;
    k[head] = 0;
    b[head] = -adb;
  }
}
void increase(int x) {
  adb += x;
  q[head - 1] = -1;
  while (head <= tail && F(tail, q[tail - 1] + 1) >= X) --tail;
  if (head <= tail && k[tail])
    chmin(q[tail], int((X - (b[tail] + adb)) / k[tail]));
  if (head <= tail && q[tail] != X) {
    ++tail;
    q[tail] = X;
    k[tail] = 0;
    b[tail] = X - adb;
  }
}
int main() {
  cin >> X;
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) scanf("%d", r + i);
  int m;
  cin >> m;
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", t + i, a + i);
    lk[lower_bound(r + 1, r + n + 1, t[i] + 1) - r - 1].push_back(i);
  }
  q[0] = X;
  k[0] = 1;
  b[0] = 0;
  for (int x = 0; x <= n; ++x) {
    for (auto i : lk[x]) {
      ans[i] = qiu(a[i]);
      if (x % 2 == 0)
        ans[i] = max(0, ans[i] - (t[i] - r[x]));
      else
        ans[i] = min(X, ans[i] + (t[i] - r[x]));
    }
    if (x < n) {
      if (x % 2 == 0)
        decrease(r[x + 1] - r[x]);
      else
        increase(r[x + 1] - r[x]);
    }
  }
  for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
}
