#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int p[100500];
vector<pair<int, int> > v;
vector<pair<int, int> > arr;
int rev[100500];
int ans[100500];
int X;
struct treap {
  int x, y, sz;
  bool is0, isn;
  int add;
  treap *l, *r;
  treap(int x, int y, treap *l, treap *r)
      : x(x), y(y), l(l), r(r), is0(0), isn(0), add(0), sz(1) {}
};
int treaps[100500];
void push(treap *v) {
  if ((!(v->is0 && v->isn) && !(v->is0 && v->add) && !(v->isn && v->add)) == 0)
    exit(-1);
  if (v->is0)
    v->x = 0;
  else if (v->isn)
    v->x = X;
  else if (v->add != 0)
    v->x += v->add;
  if (v->l) {
    if (v->is0) {
      v->l->is0 = 1;
      v->l->add = v->l->isn = 0;
    } else if (v->isn) {
      v->l->isn = 1;
      v->l->add = v->l->is0 = 0;
    } else {
      if (v->l->is0) {
        v->l->x = 0;
        v->l->is0 = 0;
        v->l->add = 0;
      }
      if (v->l->isn) {
        v->l->x = X;
        v->l->isn = 0;
        v->l->add = 0;
      }
      v->l->add += v->add;
    }
  }
  if (v->r) {
    if (v->is0) {
      v->r->is0 = 1;
      v->r->add = v->r->isn = 0;
    } else if (v->isn) {
      v->r->isn = 1;
      v->r->add = v->r->is0 = 0;
    } else {
      if (v->r->is0) {
        v->r->x = 0;
        v->r->is0 = 0;
        v->r->add = 0;
      }
      if (v->r->isn) {
        v->r->x = X;
        v->r->isn = 0;
        v->r->add = 0;
      }
      v->r->add += v->add;
    }
  }
  v->is0 = 0;
  v->isn = 0;
  v->add = 0;
}
void recalc(treap *v) {
  int sz = 1;
  if (v->l) sz += v->l->sz;
  if (v->r) sz += v->r->sz;
  v->sz = sz;
}
treap *merge_treap(treap *L, treap *R) {
  if (!L) return R;
  if (!R) return L;
  push(L);
  push(R);
  if (L->y > R->y) {
    L->r = merge_treap(L->r, R);
    recalc(L);
    return L;
  } else {
    R->l = merge_treap(L, R->l);
    recalc(R);
    return R;
  }
}
void split(treap *T, treap *&L, treap *&R, int x) {
  if (!T) {
    L = R = NULL;
    return;
  }
  push(T);
  if (T->x <= x) {
    L = T;
    split(L->r, L->r, R, x);
  } else {
    R = T;
    split(R->l, L, R->l, x);
  }
  recalc(T);
}
int get(treap *v, int num) {
  push(v);
  int sz = 0;
  if (v->l) sz += v->l->sz;
  if (num < sz) return get(v->l, num);
  if (num == sz) {
    return v->x;
  }
  return get(v->r, num - sz - 1);
}
treap *head = NULL;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int k, r, t, a;
  cin >> X >> k;
  for (int i = 0; i < k; i++) {
    cin >> r;
    v.push_back(make_pair(r, 1e9 + 5));
  }
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    cin >> t >> a;
    v.push_back({t, i});
    arr.push_back(make_pair(a, i));
  }
  sort(arr.begin(), arr.end());
  sort(v.begin(), v.end());
  int last = 0;
  int sign = -1;
  for (int i = 0; i < q; i++) {
    treap *v = new treap(arr[i].first, rand(), NULL, NULL);
    treaps[arr[i].second] = i;
    head = merge_treap(head, v);
  }
  for (pair<int, int> &x : v) {
    treap *L, *R;
    int len = x.first - last;
    if (len) {
      if (sign == 1) {
        split(head, L, R, X - len);
        if (R) {
          push(R);
          R->isn = true;
        }
        if (L) {
          push(L);
          L->add += len;
        }
      } else {
        split(head, L, R, len);
        if (L) {
          push(L);
          L->is0 = true;
        }
        if (R) {
          push(R);
          R->add -= len;
        }
      }
      head = merge_treap(L, R);
    }
    if (x.second == 1e9 + 5) {
      sign = (sign == 1 ? -1 : 1);
    } else {
      ans[x.second] = get(head, treaps[x.second]);
    }
    last = x.first;
  }
  for (int i = 0; i < q; i++) cout << ans[i] << "\n";
  return 0;
}
