#include <bits/stdc++.h>
using namespace std;
struct data {
  int t, a, no;
  bool operator<(const data& b) const { return a < b.a; }
} a[100010];
int n, m, q, p[100010], t[100010], r[100010], tag[100010 << 2],
    tag2[100010 << 2], ans[100010];
long long s[100010];
inline void push(int x, int l, int r) {
  if (l == r) return;
  int mid = l + r >> 1;
  if (tag[x] >= 0) {
    s[x << 1] = 1ll * (mid - l + 1) * tag[x],
           s[x << 1 | 1] = 1ll * (r - mid) * tag[x];
    tag[x << 1] = tag[x << 1 | 1] = tag[x];
    tag2[x << 1] = tag2[x << 1 | 1] = 0;
    tag[x] = -1;
  }
  if (tag2[x]) {
    s[x << 1] += 1ll * (mid - l + 1) * tag2[x],
        s[x << 1 | 1] += 1ll * (r - mid) * tag2[x];
    tag2[x << 1] += tag2[x], tag2[x << 1 | 1] += tag2[x];
    tag2[x] = 0;
  }
}
inline void build(int x, int l, int r) {
  if (l == r) {
    s[x] = a[l].a;
    return;
  }
  int mid = l + r >> 1;
  build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
  s[x] = s[x << 1] + s[x << 1 | 1];
}
inline void modify_set(int x, int l, int r, int L, int R, int v) {
  push(x, L, R);
  if (l == L && r == R) {
    s[x] = 1ll * (r - l + 1) * v, tag[x] = v, tag2[x] = 0;
    return;
  }
  int mid = L + R >> 1;
  if (r <= mid)
    modify_set(x << 1, l, r, L, mid, v);
  else if (l > mid)
    modify_set(x << 1 | 1, l, r, mid + 1, R, v);
  else
    modify_set(x << 1, l, mid, L, mid, v),
        modify_set(x << 1 | 1, mid + 1, r, mid + 1, R, v);
  s[x] = s[x << 1] + s[x << 1 | 1];
}
inline void modify_add(int x, int l, int r, int L, int R, int v) {
  push(x, L, R);
  if (l == L && r == R) {
    s[x] += 1ll * (r - l + 1) * v, tag2[x] += v;
    return;
  }
  int mid = L + R >> 1;
  if (r <= mid)
    modify_add(x << 1, l, r, L, mid, v);
  else if (l > mid)
    modify_add(x << 1 | 1, l, r, mid + 1, R, v);
  else
    modify_add(x << 1, l, mid, L, mid, v),
        modify_add(x << 1 | 1, mid + 1, r, mid + 1, R, v);
  s[x] = s[x << 1] + s[x << 1 | 1];
}
inline int query(int x, int p, int l, int r) {
  push(x, l, r);
  if (l == r) return s[x];
  int mid = l + r >> 1;
  if (p <= mid) return query(x << 1, p, l, mid);
  return query(x << 1 | 1, p, mid + 1, r);
}
inline void inc(int x) {
  if (query(1, q, 1, q) + x <= m) {
    modify_add(1, 1, q, 1, q, x);
    return;
  }
  int l = 1, r = q;
  while (l < r) {
    int mid = l + r >> 1;
    if (query(1, mid, 1, q) + x <= m)
      l = mid + 1;
    else
      r = mid;
  }
  if (l > 1) modify_add(1, 1, l - 1, 1, q, x);
  modify_set(1, l, q, 1, q, m);
}
inline void dec(int x) {
  if (query(1, 1, 1, q) >= x) {
    modify_add(1, 1, q, 1, q, -x);
    return;
  }
  int l = 1, r = q;
  while (l < r) {
    int mid = l + r >> 1;
    if (query(1, mid, 1, q) >= x)
      r = mid;
    else
      l = mid + 1;
  }
  if (query(1, l, 1, q) < x) l++;
  if (l > 1 && query(1, l - 1, 1, q) >= x) l--;
  if (l <= q) modify_add(1, l, q, 1, q, -x);
  modify_set(1, 1, l - 1, 1, q, 0);
}
int main() {
  memset(tag, -1, sizeof tag);
  cin >> m >> n;
  for (int i = 1; i <= n; i++) scanf("%d", &r[i]);
  cin >> q;
  for (int i = 1; i <= q; i++) scanf("%d%d", &a[i].t, &a[i].a), a[i].no = i;
  sort(a + 1, a + 1 + q);
  build(1, 1, q);
  for (int i = 1; i <= q; i++) p[a[i].no] = i;
  int j = 1, last = 0;
  for (int i = 1; i <= n; i++)
    if (i & 1) {
      while (j <= q && a[p[j]].t < r[i]) {
        if (a[p[j]].t - last) dec(a[p[j]].t - last);
        ans[j] = query(1, p[j], 1, q), last = a[p[j]].t;
        j++;
      }
      dec(r[i] - last), last = r[i];
    } else {
      while (j <= q && a[p[j]].t < r[i]) {
        if (a[p[j]].t - last) inc(a[p[j]].t - last);
        ans[j] = query(1, p[j], 1, q), last = a[p[j]].t;
        j++;
      }
      inc(r[i] - last), last = r[i];
    }
  while (j <= q) {
    if (a[p[j]].t - last) {
      if (n & 1)
        inc(a[p[j]].t - last);
      else
        dec(a[p[j]].t - last);
    }
    ans[j] = query(1, p[j], 1, q), last = a[p[j]].t;
    j++;
  }
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
  return 0;
}
