#include <bits/stdc++.h>
using namespace std;
const long long INF = 2000000007;
const long long SZ = 3e5;
long long ar[SZ];
long long res[SZ];
long long x;
struct node {
  bool ok = false;
  long long l, r, add, sval;
  node *left, *right;
};
node *build(long long l, long long r) {
  node *res = new node;
  res->l = l;
  res->r = r;
  res->add = res->sval = 0;
  if (l == r) {
    res->sval = ar[l];
  } else {
    long long mid = (l + r) / 2;
    res->left = build(l, mid);
    res->right = build(mid + 1, r);
  }
  return res;
}
void push(node *root) {
  if (!root) return;
  root->left->add += root->add;
  root->right->add += root->add;
  root->add = 0;
  if (root->ok) {
    root->left->sval = root->right->sval = root->sval;
    root->left->ok = root->right->ok = true;
    root->sval = 0;
    root->ok = false;
  }
}
long long query(node *root, long long i) {
  if (i < root->l || i > root->r) return 0;
  if (root->l == root->r) return root->sval + root->add;
  push(root);
  return query(root->left, i) + query(root->right, i);
}
void add(node *root, long long l, long long r, long long d) {
  if (l > root->r || r < root->l) return;
  if (l <= root->l && r >= root->r) {
    root->add += d;
    return;
  }
  push(root);
  add(root->left, l, r, d);
  add(root->right, l, r, d);
}
void stroot(node *root, long long l, long long r, long long d) {
  if (l > root->r || r < root->l) return;
  if (l <= root->l && r >= root->r) {
    root->ok = true;
    root->sval = d;
    root->add = 0;
    return;
  }
  push(root);
  stroot(root->left, l, r, d);
  stroot(root->right, l, r, d);
}
void ans(node *root, long long t1, long long i1, long long i2, long long st) {
  long long cr = query(root, i2);
  if (st % 2 == 0)
    cr -= min(t1, cr);
  else
    cr += min(t1, x - cr);
  res[i1] = cr;
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long k, q1, t, a;
  cin >> x >> k;
  vector<long long> r(k + 2);
  vector<vector<tuple<long long, long long, long long>>> re(k + 1);
  r[0] = 0;
  for (long long i = 0; i < k; i++) cin >> r[i + 1];
  r[k + 1] = INF;
  sort(r.begin(), r.end());
  cin >> q1;
  vector<tuple<long long, long long, long long>> q(q1);
  for (long long i = 0; i < q1; i++) {
    cin >> t >> a;
    q[i] = make_tuple(a, t, i);
  }
  sort(q.begin(), q.end());
  for (long long i = 0; i < q1; i++) {
    long long i1 = upper_bound(r.begin(), r.end(), get<1>(q[i])) - r.begin();
    i1--;
    re[i1].push_back(make_tuple(get<1>(q[i]), get<2>(q[i]), i));
    ar[i] = get<0>(q[i]);
  }
  node *root = build(0, q1 - 1);
  for (long long i = 0; i < k + 1; i++) {
    for (auto tu : re[i])
      ans(root, get<0>(tu) - r[i], get<1>(tu), get<2>(tu), i);
    long long l1 = 0, r1 = q1;
    long long step = r[i + 1] - r[i];
    while (l1 < r1) {
      long long cr = (l1 + r1) / 2;
      long long vl = query(root, cr);
      if (i % 2 == 0) {
        if (vl < step)
          l1 = cr + 1;
        else
          r1 = cr;
      } else {
        if (vl + step <= x)
          l1 = cr + 1;
        else
          r1 = cr;
      }
    }
    if (i % 2 == 0) {
      if (l1) stroot(root, 0, l1 - 1, 0);
      if (l1 < q1) add(root, l1, q1 - 1, 0 - step);
    } else {
      if (l1) add(root, 0, l1 - 1, step);
      if (l1 < q1) stroot(root, l1, q1 - 1, x);
    }
  }
  for (long long i = 0; i < q1; i++) cout << res[i] << endl;
  return 0;
}
