#include <bits/stdc++.h>
const int N = 2e5 + 5;
using namespace std;
int n, m, X, r[N], cnt, t[N], a[N], flag, ans[N], num[N];
struct node {
  int t, id, op;
  node(int a = 0, int b = 0, int c = 0) { t = a, id = b, op = c; }
  bool operator<(const node &p) const { return t == p.t ? op < p.op : t < p.t; }
} p[N];
struct nd {
  int t, a, id;
  nd(int x = 0, int y = 0, int z = 0) { t = x, a = y, id = z; }
  bool operator<(const nd &p) const { return a < p.a; }
} q[N];
struct SegTree {
  struct Node {
    int tag1, tag2, val;
  } t[N << 2];
  void build(int p, int l, int r) {
    t[p].tag1 = 0, t[p].tag2 = -1;
    if (l == r) return (void)(t[p].val = q[l].a);
    int mid = (l + r) >> 1;
    build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
  }
  void pushdown(int p) {
    if (t[p].tag1 || t[p].tag2 != -1) {
      if (t[p].tag2 != -1) {
        t[p << 1].tag2 = t[p << 1 | 1].tag2 = t[p << 1].val =
            t[p << 1 | 1].val = t[p].tag2;
        t[p << 1].tag1 = t[p << 1 | 1].tag1 = 0, t[p].tag2 = -1;
      }
      if (t[p].tag1) {
        t[p << 1].tag1 += t[p].tag1, t[p << 1 | 1].tag1 += t[p].tag1;
        t[p << 1].val += t[p].tag1, t[p << 1 | 1].val += t[p].tag1;
        t[p].tag1 = 0;
      }
    }
  }
  void modify(int p, int l, int r, int ql, int qr, int x) {
    if (ql <= l && r <= qr)
      return (void)(t[p].val = t[p].tag2 = x, t[p].tag1 = 0);
    pushdown(p);
    int mid = (l + r) >> 1;
    if (ql <= mid) modify(p << 1, l, mid, ql, qr, x);
    if (mid < qr) modify(p << 1 | 1, mid + 1, r, ql, qr, x);
  }
  int query(int p, int l, int r, int x) {
    if (x > r && x < l) return 1;
    if (l == r) return t[p].val;
    pushdown(p);
    int mid = (l + r) >> 1;
    if (x <= mid)
      return query(p << 1, l, mid, x);
    else
      return query(p << 1 | 1, mid + 1, r, x);
  }
} T;
template <typename T>
inline T read() {
  T x = 0, w = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') w = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x * w;
}
void solve1() {
  int l = 0, r = m, mid, ans = 0;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (T.query(1, 1, m, mid) < 0)
      ans = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  if (ans) T.modify(1, 1, m, 1, ans, 0);
}
void solve2() {
  int l = 0, r = m, mid, ans = m + 1;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (T.query(1, 1, m, mid) > X)
      ans = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  if (ans <= m) T.modify(1, 1, m, ans, m, X);
}
int main() {
  X = read<int>(), n = read<int>();
  for (int i = 1; i <= n; i++) r[i] = read<int>(), p[++cnt] = node(r[i], i, 1);
  m = read<int>();
  for (int i = 1; i <= m; i++) {
    t[i] = read<int>(), a[i] = read<int>();
    q[i] = nd(t[i], a[i], i), p[++cnt] = node(t[i], i, 0);
  }
  sort(q + 1, q + m + 1), sort(p + 1, p + cnt + 1), T.build(1, 1, m);
  for (int i = 1; i <= m; i++) num[q[i].id] = i;
  for (int id, tmp, pos = 0, i = 1; i <= cnt; i++) {
    while (pos < m && r[pos + 1] < p[i].t) pos++;
    if (p[i].op) {
      id = p[i].id;
      if (!flag)
        T.t[1].tag1 -= r[id] - r[id - 1], T.t[1].val -= r[id] - r[id - 1],
            solve1();
      else
        T.t[1].tag1 += r[id] - r[id - 1], T.t[1].val += r[id] - r[id - 1],
            solve2();
      flag ^= 1;
    } else {
      id = p[i].id, tmp = T.query(1, 1, m, num[id]);
      if (!flag)
        tmp = max(0, tmp - (p[i].t - r[pos]));
      else
        tmp = min(X, tmp + (p[i].t - r[pos]));
      ans[id] = tmp;
    }
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}
