#include<bits/stdc++.h>
#define X first
#define Y second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
template<class T> using vv=vector<vector<T>>;
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
const ll MOD=1e9+7;

LL X;
int K;
int Q;
LL rs[114514];
LL ts[114514];
LL as[114514];
LL ans[114514];

struct LazySeg {
  int size;
  vector<char> has_lazy;
  vector<LL> seg;
  vector<LL> lazy;
  vector<LL> width;
  vector<LL> assi;
  const LL INF = 0x3fffffffff;

  LazySeg(vector<LL> A) {
    int n = A.size();
    size = 1;
    while (size < n) size *= 2;

    seg.resize(size);
    seg.insert(seg.end(), A.begin(), A.end());
    seg.resize(size*2);
    lazy.resize(size*2);
    has_lazy.resize(size*2);
    width.resize(size*2);
    assi.resize(size*2);
    rrep(i, size) {
      seg[i] = max(seg[i*2], seg[i*2+1]);
      width[i] = width[i*2] + width[i*2+1]; 
    }
  }

  void LazyPropagate(int k) {
    if (has_lazy[k]) {
      seg[k] = assi[k];
      if (k < size) {
        has_lazy[k*2] = true;
        has_lazy[k*2+1] = true;
        assi[k*2] = assi[k]; 
        assi[k*2+1] = assi[k];
        lazy[k*2] = 0;
        lazy[k*2+1] = 0;
      }
      has_lazy[k] = false;
    }

    seg[k] += lazy[k];
    if (k < size) {
      lazy[k*2] += lazy[k];
      lazy[k*2+1] += lazy[k];
    }
    lazy[k] = 0;
  }

  void Add(int wishl, int wishr, int k, int watchl, int watchr, LL x) {
    if (wishr <= watchl || watchr <= wishl) {
      LazyPropagate(k);
      return;
    }

    if (wishl <= watchl && watchr <= wishr) {
      lazy[k] += x;
      LazyPropagate(k);
      return;
    }

    LazyPropagate(k);
    int mid = (watchl+watchr)/2;
    Add(wishl, wishr, k*2, watchl, mid, x);
    Add(wishl, wishr, k*2+1, mid, watchr, x);
    seg[k] = max(seg[k*2], seg[k*2+1]);
  }

  void Move(int wishl, int wishr, int k, int watchl, int watchr, LL x) {
    if (wishr <= watchl || watchr <= wishl) {
      LazyPropagate(k);
      return;
    }

    if (wishl <= watchl && watchr <= wishr) {
      has_lazy[k] = true;
      lazy[k] = 0;
      assi[k] = x;
      LazyPropagate(k);
      return;
    }

    LazyPropagate(k);
    int mid = (watchl+watchr)/2;
    Move(wishl, wishr, k*2, watchl, mid, x);
    Move(wishl, wishr, k*2+1, mid, watchr, x);
    seg[k] = max(seg[k*2], seg[k*2+1]);
  }

  void Add(int wishl, int wishr, LL x) {
    return Add(wishl, wishr, 1, 0, size, x);
  }

  void Move(int wishl, int wishr, LL x) {
    return Move(wishl, wishr, 1, 0, size, x);
  }

  LL Get(int wishl, int wishr, int k, int watchl, int watchr) {
    LL lval, rval;

    if (wishr <= watchl || watchr <= wishl) return -INF;

    if (wishl <= watchl && watchr <= wishr) {
      LazyPropagate(k);
      return seg[k];
    }

    LazyPropagate(k);
    int mid = (watchl+watchr)/2;
    lval = Get(wishl, wishr, k*2, watchl, mid);
    rval = Get(wishl, wishr, k*2+1, mid, watchr);
    return max(lval, rval);
  }

  LL Get(int wishl, int wishr) {
    return Get(wishl, wishr, 1, 0, size);
  }
};

int main() {
  scanf("%lld", &X);
  scanf("%d", &K);

  priority_queue<LL, vector<LL>, greater<LL>> R;
  priority_queue<pll, vector<pll>, greater<pll>> W;
  vector<LL> T, A;
  rep(i, K) {
    scanf("%lld", &rs[i]);
    R.push(rs[i]);
    T.eb(rs[i]);
  }

  scanf("%d", &Q);
  rep(i, Q) {
    scanf("%lld%lld", &ts[i], &as[i]);
    A.eb(as[i]);
    T.eb(ts[i]);
    W.push(pll(ts[i], i));
  }
  sort(all(A));
  A.erase(unique(all(A)), A.end());

  LazySeg seg(A);
  sort(all(T));

  LL sgn = -1;
  LL prevt = 0;
  for (LL t : T) {
    seg.Add(0, A.size(), sgn*(t-prevt));
    
    if (sgn == -1) {
      int low = -1;
      int high = A.size();
      while (high - low > 1) {
        int mid = (high+low)/2;
        LL val = seg.Get(mid, mid+1);
        if (val <= 0) low = mid;
        else high = mid;
      }

      seg.Move(0, low+1, 0);
    } else {
      int low = -1;
      int high = A.size();
      while (high - low > 1) {
        int mid = (high+low)/2;
        LL val = seg.Get(mid, mid+1);
        if (val >= X) high = mid;
        else low = mid;
      }

      seg.Move(high, A.size(), X);
    }

    while (!W.empty() && W.top().first == t) {
      int idx = W.top().second; W.pop();
      int k = lower_bound(all(A), as[idx]) - A.begin();
      ans[idx] = seg.Get(k, k+1);
    }

    while (!R.empty() && R.top() == t) {
      sgn = -sgn;
      R.pop();
    }

    prevt = t;
  }

  rep(i, Q) {
    printf("%lld\n", ans[i]);
  }
}



Measured memory_bytes: 19688