#include <bits/stdc++.h>
using namespace std;
inline void read(int &x) {
  char ch;
  bool flag = false;
  for (ch = getchar(); !isdigit(ch); ch = getchar())
    if (ch == '-') flag = true;
  for (x = 0; isdigit(ch); x = x * 10 + ch - '0', ch = getchar())
    ;
  x = flag ? -x : x;
}
inline void read(long long &x) {
  char ch;
  bool flag = false;
  for (ch = getchar(); !isdigit(ch); ch = getchar())
    if (ch == '-') flag = true;
  for (x = 0; isdigit(ch); x = x * 10 + ch - '0', ch = getchar())
    ;
  x = flag ? -x : x;
}
int const maxn = 150000;
int const inf = 10000000000;
int n, lim, m;
int fa[maxn];
int r[maxn];
struct zy {
  int a, t, id;
  zy(int a, int t, int id) : a(a), t(t), id(id) {}
};
map<int, int> M;
bool operator<(zy A, zy B) { return A.t > B.t; }
priority_queue<zy> Q;
int ans[maxn];
int get_fa(int x) {
  if (fa[x] == x) return x;
  return fa[x] = get_fa(fa[x]);
}
vector<int> CCtmp;
int main() {
  read(lim);
  read(n);
  for (int i = 1; i <= n; i++) read(r[i]);
  read(m);
  for (int i = 1; i <= m; i++) {
    int a, t;
    read(t);
    read(a);
    Q.push(zy(a, t, i));
    M.insert(make_pair(i, a));
    fa[i] = i;
  }
  r[n + 1] = inf;
  for (int i = 0; i <= n; i++) {
    zy tmp = Q.top();
    while (tmp.t <= r[i + 1]) {
      if (i % 2 == 0)
        ans[tmp.id] = min(lim, max(M[get_fa(tmp.id)] - (tmp.t - r[i]), 0));
      else
        ans[tmp.id] = min(lim, max(M[get_fa(tmp.id)] + (tmp.t - r[i]), 0));
      Q.pop();
      if (Q.empty()) break;
      tmp = Q.top();
    }
    if (Q.empty()) break;
    int maxi = -1, mini = -1;
    CCtmp.clear();
    for (auto s : M) {
      int x = s.first;
      if (i % 2 == 0)
        M[x] = min(lim, max(M[get_fa(x)] - (r[i + 1] - r[i]), 0));
      else
        M[x] = min(lim, max(M[get_fa(x)] + (r[i + 1] - r[i]), 0));
      if (M[x] == 0)
        if (mini == -1) {
          mini = x;
          continue;
        } else {
          fa[x] = mini;
          CCtmp.push_back(x);
          continue;
        }
      if (M[x] == lim)
        if (maxi == -1) {
          maxi = x;
          continue;
        } else {
          fa[x] = maxi;
          CCtmp.push_back(x);
          continue;
        }
    }
    for (auto s : CCtmp) M.erase(s);
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}
