#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int x, k, q, rt;
pair<int, int> qt[maxn];
int qa[maxn], r[maxn], ans[maxn];
namespace Segtree {
int tot = 0;
class node {
 public:
  int ls, rs, mn, mx, tag, add;
  node(int _mn = 0, int _mx = 0) {
    ls = rs = add = 0;
    tag = -1;
    mn = _mn;
    mx = _mx;
  }
} t[maxn * 4];
void push_down(int v, int l, int r) {
  int mid = (l + r) >> 1;
  int &ls = t[v].ls, &rs = t[v].rs;
  if (!ls) ls = ++tot, t[ls] = node(l, mid);
  if (!rs) rs = ++tot, t[rs] = node(mid + 1, r);
  if (t[v].tag >= 0) {
    t[ls].mn = t[ls].mx = t[ls].tag = t[v].tag;
    t[ls].add = 0;
    t[rs].mn = t[rs].mx = t[rs].tag = t[v].tag;
    t[rs].add = 0;
    t[v].tag = -1;
  }
  if (t[v].add != 0) {
    t[ls].mn += t[v].add;
    t[ls].mx += t[v].add;
    t[ls].add += t[v].add;
    t[rs].mn += t[v].add;
    t[rs].mx += t[v].add;
    t[rs].add += t[v].add;
    t[v].add = 0;
  }
}
void push_up(int v) {
  int ls = t[v].ls, rs = t[v].rs;
  t[v].mx = max(t[ls].mx, t[rs].mx);
  t[v].mn = min(t[ls].mn, t[rs].mn);
}
void increase(int &v, int l, int r, int val) {
  if (!v) v = ++tot, t[v] = node(l, r);
  if (t[v].mn > x - val) {
    t[v].mn = t[v].mx = t[v].tag = x;
    t[v].add = 0;
    return;
  }
  if (t[v].mx <= x - val) {
    t[v].mn += val;
    t[v].mx += val;
    t[v].add += val;
    return;
  }
  push_down(v, l, r);
  int mid = (l + r) >> 1;
  increase(t[v].ls, l, mid, val);
  increase(t[v].rs, mid + 1, r, val);
  push_up(v);
}
void decrease(int &v, int l, int r, int val) {
  if (!v) v = ++tot, t[v] = node(l, r);
  if (t[v].mx < val) {
    t[v].mn = t[v].mx = t[v].tag = 0;
    t[v].add = 0;
    return;
  }
  if (t[v].mn >= val) {
    t[v].mn -= val;
    t[v].mx -= val;
    t[v].add -= val;
    return;
  }
  push_down(v, l, r);
  int mid = (l + r) >> 1;
  decrease(t[v].ls, l, mid, val);
  decrease(t[v].rs, mid + 1, r, val);
  push_up(v);
}
int query(int &v, int l, int r, int k) {
  if (!v) v = ++tot, t[v] = node(l, r);
  if (l == r) return t[v].mn;
  push_down(v, l, r);
  int mid = (l + r) >> 1;
  if (k <= mid)
    return query(t[v].ls, l, mid, k);
  else
    return query(t[v].rs, mid + 1, r, k);
}
}  // namespace Segtree
int main() {
  scanf("%d%d", &x, &k);
  for (int(i) = 1; (i) <= k; i++) scanf("%d", &r[i]);
  scanf("%d", &q);
  for (int(i) = 1; (i) <= q; i++) {
    scanf("%d%d", &qt[i].first, &qa[i]);
    qt[i].second = i;
  }
  sort(qt + 1, qt + 1 + q);
  int ptr = 1;
  for (int(i) = 1; (i) <= q; i++) {
    while (ptr <= k && r[ptr] <= qt[i].first) {
      if (ptr & 1)
        Segtree::decrease(rt, 1, x, r[ptr] - r[ptr - 1]);
      else
        Segtree::increase(rt, 1, x, r[ptr] - r[ptr - 1]);
      ptr++;
    }
    int id = qt[i].second;
    ans[id] = Segtree::query(rt, 1, x, qa[id]);
    if (ptr & 1)
      ans[id] = max(ans[id] - qt[i].first + r[ptr - 1], 0);
    else
      ans[id] = min(ans[id] + qt[i].first - r[ptr - 1], x);
  }
  for (int(i) = 1; (i) <= q; i++) printf("%d\n", ans[i]);
  return 0;
}
