#include <bits/stdc++.h>
using namespace std;
int X, n, m, h, r, pos;
int a[110000], a1[110000], q[110000], ans[110000], v[110000], mx[110000];
long long sum[110000];
struct node {
  int t, a, pos;
  friend bool operator<(const node &r1, const node &r2) { return r1.a < r2.a; }
} b[110000];
void change(int x) {
  v[x - 1] = X;
  for (int i = x, now = X; i < pos; i++) {
    if (i & 1)
      now = max(0, now - a[i]);
    else
      now = min(X, now + a[i]);
    v[i] = now;
  }
  pos = x;
}
int calc(int x) { return min(max(x, 0), X); }
int query(int x, int y) {
  int v2 = 0, ret;
  if (x > a1[n]) {
    v2 = x - a1[n];
    if (~n & 1) v2 = -v2;
    x = a1[n];
  }
  int t = lower_bound(a1 + 1, a1 + 1 + n, x) - a1;
  int v1 = x - a1[t - 1];
  if (t & 1) v1 = -v1;
  if (t >= pos)
    ret = v[t - 1];
  else if (h > r || t <= q[h])
    ret = sum[t - 1] + y;
  else {
    int t1 = upper_bound(q + h, q + r + 1, t - 1) - q - 1;
    ret = sum[t - 1] - sum[q[t1]];
  }
  return calc(calc(ret + v1) + v2);
}
int main() {
  scanf("%d%d", &X, &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a1[i]);
    a[i] = a1[i] - a1[i - 1];
    if (i & 1)
      sum[i] = sum[i - 1] - a[i];
    else
      sum[i] = sum[i - 1] + a[i];
    mx[i] = i == 1 ? 1 : (sum[mx[i - 1]] > sum[i] ? mx[i - 1] : i);
  }
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    b[i].pos = i;
    scanf("%d%d", &b[i].t, &b[i].a);
  }
  sort(b + 1, b + 1 + m);
  h = 1;
  r = 0;
  pos = n + 1;
  for (int i = 1, now = b[1].a; i <= n; i++) {
    if (i & 1) {
      now -= a[i];
      if (now < 0) now = 0, q[++r] = i;
    } else {
      now += a[i];
      if (now > X) {
        change(i + 1);
        break;
      }
    }
  }
  ans[b[1].pos] = query(b[1].t, b[1].a);
  for (int i = 2; i <= m; i++) {
    while (h <= r && q[h] < pos) {
      if (sum[mx[q[h]]] + b[i].a > X) {
        change(mx[q[h]] + 1);
        break;
      }
      if (sum[q[h]] + b[i].a < 0) break;
      h++;
    }
    ans[b[i].pos] = query(b[i].t, b[i].a);
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}
