#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define pb push_back
#define mp make_pair

int x, k, q;

ll t[400010], tset[400010], tadd[400010];
int a[100010], r[100010];
struct query{
    int t, a, it;
    query(int t, int a, int it): t(t), a(a), it(it) {}
};
vector<query> in;

void build(int v, int vl, int vr){
    if(vl == vr){
        t[v] = a[vl];
        return;
    }
    int vm = (vl + vr) >> 1;
    build(2 * v, vl, vm);
    build(2 * v + 1, vm + 1, vr);
}

void push(int v, int vl, int vr){
    if(tset[v] != -1){
        if(vl != vr){
            tset[2 * v] = tset[v];
            tset[2 * v + 1] = tset[v];
            tadd[2 * v] = 0;
            tadd[2 * v + 1] = 0;
        }
        else t[v] = tset[v];
        tset[v] = -1;
    }
    if(tadd[v] != 0){
        if(vl != vr){
            tadd[2 * v] += tadd[v];
            tadd[2 * v + 1] += tadd[v];
        }
        else t[v] += tadd[v];
        tadd[v] = 0;
    }
}

void update(int v, int vl, int vr, int l, int r, int set, int add){
    push(v, vl, vr);
    if(l > vr || r < vl) return;
    if(l <= vl && vr <= r){
        tset[v] = set;
        tadd[v] = add;
        push(v, vl, vr);
        return;
    }
    int vm = (vl + vr) >> 1;
    update(2 * v, vl, vm, l, r, set, add);
    update(2 * v + 1, vm + 1, vr, l, r, set, add);
}

int get(int v, int vl, int vr, int l, int r){
    push(v, vl, vr);
    if(l > vr || r < vl) return 0;
    if(l <= vl && vr <= r) return t[v];
    int vm = (vl + vr) >> 1;
    int q1 = get(2 * v, vl, vm, l, r);
    int q2 = get(2 * v + 1, vm + 1, vr, l, r);
    return q1 + q2;
}

bool cmp(const query &lhs, const query &rhs){
    if(lhs.a != rhs.a) return lhs.a < rhs.a;
    return lhs.t < rhs.t;
}

bool cmp2(const pair<pii, int> &lhs, const pair<pii, int> &rhs){
    if(lhs.first.first != rhs.first.first) return lhs.first.first < rhs.first.first;
    return lhs.second > rhs.second;
}

vector< pair<pii, int> > moments;
int ans[100010];
int change[100010];

int main()
{
    ios_base::sync_with_stdio(0);
    for(int i = 0; i < 400000; i++) tset[i] = -1;
    cin >> x >> k;
    for(int i = 0; i < k; i++){
        cin >> r[i];
    }
    cin >> q;
    for(int i = 0; i < q; i++){
        int tq, ta;
        cin >> tq >> ta;
        in.pb(query(tq, ta, i));
    }
    sort(in.begin(), in.end(), cmp);
    for(int i = 0; i < q; i++){
        change[in[i].it] = i;
    }
    for(int i = 0; i < q; i++){
        a[i] = in[i].a;
    }
    build(1, 0, q - 1);
    for(int i = 0; i < k; i++){
        moments.pb(mp(mp(r[i], -1), 1));
    }
    for(int i = 0; i < q; i++){
        moments.pb(mp(mp(in[i].t, in[i].it), 0));
    }
    sort(moments.begin(), moments.end(), cmp2);
    int last = 0;
    int turn = 0;
    for(int i = 0; i < moments.size(); i++){
        int len = moments[i].first.first - last;
        if(turn == 0){
            int lo = -1, hi = q;
            while(lo != hi){
                int mi = (lo + hi + 1) >> 1;
                if(get(1, 0, q - 1, mi, mi) - len > 0) hi = mi - 1;
                else lo = mi;
            }
            if(lo >= 0) update(1, 0, q - 1, 0, lo, 0, 0);
            if(lo + 1 < q) update(1, 0, q - 1, lo + 1, q - 1, -1, -len);
        }
        else{
            int lo = -1, hi = q;
            while(lo != hi){
                int mi = (lo + hi + 1) >> 1;
                if(get(1, 0, q - 1, mi, mi) + len > x) hi = mi - 1;
                else lo = mi;
            }
            if(lo >= 0) update(1, 0, q - 1, 0, lo, -1, len);
            if(lo + 1 < q) update(1, 0, q - 1, lo + 1, q - 1, x, 0);
        }
        if(moments[i].second == 0){
            int it = change[moments[i].first.second];
            ans[moments[i].first.second] = get(1, 0, q - 1, it, it);
        }
        if(moments[i].second == 1){
            turn ^= 1;
        }
        last = moments[i].first.first;
    }
    for(int i = 0; i < q; i++){
        cout << ans[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 15600