#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <cassert>

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 -> x = 0;
    else
    if (v -> isn)
        v -> x = X;

    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;
        }

        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;
        }
        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());
    /*for (int i = 0; i < q; i++)
        rev[arr[i].second] = i*/
    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){
            //cout << get(head, 5) << " " << len * sign << endl;
            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);

            //cout << get(head, 5) << " " << len * sign << endl;
        }

        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;
}


Measured memory_bytes: 9072