#include <bits/stdc++.h>
using namespace std;
template <class htpe, class cmp>
using heap = priority_queue<htpe, vector<htpe>, cmp>;
template <class htpe>
using min_heap = heap<htpe, greater<htpe> >;
template <class htpe>
using max_heap = heap<htpe, less<htpe> >;
const int INF = 1791791791;
const long long INFLL = 1791791791791791791ll;
template <int input_buf_size, int output_buf_size>
class FastIO {
  char cbuf[input_buf_size + 1];
  int icur = 0;
  inline bool go_to_next_token() {
    while (cbuf[icur] == ' ' || cbuf[icur] == '\n') icur++;
    while (cbuf[icur] == 0) {
      icur = 0;
      if (fgets(cbuf, sizeof(cbuf), stdin) != cbuf) return false;
      while (cbuf[icur] == ' ' || cbuf[icur] == '\n') icur++;
    }
    return true;
  }

 public:
  string readString() {
    assert(go_to_next_token());
    string ans;
    while (cbuf[icur] != ' ' && cbuf[icur] != '\n' && cbuf[icur] != 0)
      ans.push_back(cbuf[icur++]);
    ans.shrink_to_fit();
    return ans;
  }
  template <class int_type>
  int_type readInt() {
    assert(go_to_next_token());
    int_type x = 0;
    bool m = cbuf[icur] == '-';
    if (m) icur++;
    while ('0' <= cbuf[icur] && cbuf[icur] <= '9') {
      x *= 10;
      x += (cbuf[icur] - '0');
      icur++;
    }
    if (m) x = -x;
    return x;
  }
  bool seekEof() { return !go_to_next_token(); }

 private:
  char obuf[output_buf_size + 1];
  int ocur = 0;
  inline void write_string(const char* str, size_t sz = 0) {
    if (sz == 0) sz = strlen(str);
    if (ocur + sz > output_buf_size) {
      fputs(obuf, stdout);
      fputs(str, stdout);
      ocur = 0;
      obuf[0] = 0;
      return;
    }
    strcpy(obuf + ocur, str);
    ocur += sz;
    obuf[ocur] = 0;
  }

 public:
  template <class int_type>
  void writeInt(int_type x, bool sp = true) {
    char buf[21];
    int c = 0;
    if (x < 0) {
      buf[c++] = '-';
      x = -x;
    }
    int s = c;
    if (x == 0) {
      buf[c++] = '0';
    }
    while (x > 0) {
      buf[c++] = (x % 10) + '0';
      x /= 10;
    }
    for (int i = 0; 2 * i < c - s; i++) {
      swap(buf[s + i], buf[c - 1 - i]);
    }
    buf[c] = 0;
    write_string(buf, c);
    if (sp) write_string(" ", 1);
  }
  void writeString(string s, bool space = true) {
    write_string(s.c_str(), s.size());
    if (space) write_string(" ", 1);
  }
  void writeEndl() { write_string("\n", 1); }
  void flush() {
    fputs(obuf, stdout);
    ocur = 0;
    obuf[0] = 0;
  }

 private:
  bool lflush;

 public:
  FastIO(bool local_flush) {
    obuf[0] = 0;
    lflush = local_flush;
  }
  ~FastIO() { fputs(obuf, stdout); }
};
FastIO<10000000, 10000000> IO(true);
class segment_tree {
  int n;
  vector<long long> mn, mx;
  vector<long long> mod;
  void build(int v, int L, int R, const vector<int>& a) {
    if (L == R - 1)
      mn[v] = mx[v] = a[L];
    else {
      int mid = (L + R) / 2;
      build(2 * v + 1, L, mid, a);
      build(2 * v + 2, mid, R, a);
      mn[v] = min(mn[2 * v + 1], mn[2 * v + 2]);
      mx[v] = max(mx[2 * v + 1], mx[2 * v + 2]);
    }
  }
  void push(int v) {
    mn[v] += mod[v];
    mx[v] += mod[v];
    mod[2 * v + 1] += mod[v];
    mod[2 * v + 2] += mod[v];
    mod[v] = 0;
  }
  void add(int v, int L, int R, int l, int r, int val) {
    if (r <= L || R <= l)
      return;
    else if (l <= L && R <= r) {
      mod[v] += val;
    } else {
      push(v);
      add(2 * v + 1, L, (L + R) >> 1, l, r, val);
      add(2 * v + 2, (L + R) >> 1, R, l, r, val);
      mn[v] =
          min(mn[2 * v + 1] + mod[2 * v + 1], mn[2 * v + 2] + mod[2 * v + 2]);
      mx[v] =
          max(mx[2 * v + 1] + mod[2 * v + 1], mx[2 * v + 2] + mod[2 * v + 2]);
    }
  }
  int first_geq(int v, int L, int R, int l, int r, long long x) {
    if (R <= l || r <= L) return R;
    if (mx[v] + mod[v] < x) return R;
    if (L == R - 1) return L;
    push(v);
    int mid = (L + R) >> 1;
    int a = first_geq(2 * v + 1, L, mid, l, r, x);
    if (a < mid) return a;
    return first_geq(2 * v + 2, mid, R, l, r, x);
  }
  int last_leq(int v, int L, int R, int l, int r, long long x) {
    if (R <= l || r <= L) return L - 1;
    if (mn[v] + mod[v] > x) return L - 1;
    if (L == R - 1) return L;
    push(v);
    int mid = (L + R) >> 1;
    int a = last_leq(2 * v + 1, L, mid, l, r, x);
    if (a >= L) return a;
    a = last_leq(2 * v + 2, mid, R, l, r, x);
    if (a >= mid) return a;
    return L - 1;
  }
  long long get_val(int v, int L, int R, int i) {
    if (i < L || R <= i)
      return -INFLL;
    else if (L == R - 1)
      return mn[v] + mod[v];
    else {
      push(v);
      int mid = (L + R) >> 1;
      if (i < mid)
        return get_val(2 * v + 1, L, mid, i);
      else
        return get_val(2 * v + 2, mid, R, i);
    }
  }

 public:
  segment_tree(vector<int>& b) {
    n = b.size();
    mn.resize(4 * n);
    mx.resize(4 * n);
    mod.resize(4 * n, 0);
    assert(is_sorted((b).begin(), (b).end()));
    build(0, 0, n, b);
  }
  void add(int l, int r, int x) { add(0, 0, n, l, r, x); }
  long long get_val(int i) { return get_val(0, 0, n, i); }
  int first_geq(int l, int r, long long x) {
    return first_geq(0, 0, n, l, r, x);
  }
  int last_leq(int l, int r, long long x) { return last_leq(0, 0, n, l, r, x); }
};
struct query {
  int a, t;
  int ans;
  query(int _a, int _t, int _ans) : a(_a), t(_t), ans(_ans) {}
};
int main() {
  int x = IO.readInt<int>();
  int k = IO.readInt<int>();
  vector<int> r(k + 2);
  for (int i = 0; i < ((int)(k)); ++i) r[i + 1] = IO.readInt<int>();
  r.back() = INF;
  k += 2;
  int q = IO.readInt<int>();
  vector<int> answers(q);
  vector<query> qs;
  for (int i = 0; i < ((int)(q)); ++i) {
    int t = IO.readInt<int>();
    int a = IO.readInt<int>();
    qs.push_back(query(a, t, i));
  }
  vector<int> a_ap;
  for (int i = 0; i < ((int)(q)); ++i) a_ap.push_back(qs[i].a);
  sort((a_ap).begin(), (a_ap).end());
  a_ap.resize(unique((a_ap).begin(), (a_ap).end()) - a_ap.begin());
  segment_tree st(a_ap);
  int cl = 0, cr = a_ap.size();
  int la = 0, ra = x - 1;
  sort((qs).begin(), (qs).end(),
       [](const query& a, const query& b) { return a.t < b.t; });
  int qi = 0;
  int d = -1;
  for (int i = (int)(1); i < ((int)(k)); ++i) {
    while (qi < q && qs[qi].t <= r[i]) {
      long long vb;
      int ai =
          lower_bound((a_ap).begin(), (a_ap).end(), qs[qi].a) - a_ap.begin();
      if (ai < cl)
        vb = la;
      else if (ai >= cr)
        vb = ra;
      else
        vb = st.get_val(ai);
      vb += d * (qs[qi].t - r[i - 1]);
      vb = min<long long>(vb, x);
      vb = max<long long>(vb, 0);
      answers[qs[qi].ans] = vb;
      qi++;
    }
    if (d < 0) {
      if (la < r[i] - r[i - 1]) {
        int nli = st.first_geq(cl, cr, r[i] - r[i - 1] + 1);
        cl = nli;
        la = 0;
      } else
        la -= r[i] - r[i - 1];
      ra -= r[i] - r[i + 1];
      st.add(cl, cr, -(r[i] - r[i - 1]));
    } else {
      if (x - ra < r[i] - r[i - 1]) {
        int nri = st.first_geq(cl, cr, x - (r[i] - r[i - 1]));
        cr = nri;
        ra = x;
      } else
        ra += r[i] - r[i - 1];
      la += r[i] - r[i - 1];
      st.add(cl, cr, r[i] - r[i - 1]);
    }
    d = -d;
  }
  for (int i = 0; i < ((int)(q)); ++i) {
    IO.writeInt(answers[i], 0);
    IO.writeEndl();
  }
  return 0;
}
