#include<bits/stdc++.h>
using namespace std;

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

int X, K, Q;
vector<int> T, R;
int Yn;
vector<int> Y;
map<int, int> dy;
struct Query {
    int t, a, id;
    bool operator <(const Query &i) const {
        return t < i.t;
    }
};
vector<Query> query;

struct BIT {
    vector<ll> tree;
    vector<pair<ll, int> > lazy;
    void init() {
        tree = vector<ll>(4*Yn, 0);
        lazy = vector<pair<ll, int> >(4*Yn, make_pair(0, 0));
    }
    void prop(int l, int r, int n) {
        if(l != r) {
            if(lazy[n].second == 0) {
                tree[2*n] += lazy[n].first;
                lazy[2*n].first += lazy[n].first;
                tree[2*n + 1] += lazy[n].first;
                lazy[2*n + 1].first += lazy[n].first;
            }
            else {
                tree[2*n] = lazy[n].first;
                lazy[2*n] = lazy[n];
                tree[2*n + 1] = lazy[n].first;
                lazy[2*n + 1] = lazy[n];
            }
            lazy[n] = make_pair(0, 0);
        }
    }
    void upd(int a, int b, int d, int l, int r, int n) {
        if(b < l || r < a) return;
        if(a <= l && r <= b) {
            tree[n] += d;
            lazy[n].first += d;
            return;
        }
        prop(l, r, n);
        int m = (l + r)>>1;
        upd(a, b, d, l, m, 2*n);
        upd(a, b, d, m + 1, r, 2*n + 1);
        tree[n] = min(tree[2*n], tree[2*n + 1]);
    }
    void upd2(int a, int b, int v, int l, int r, int n) {
        if(b < l || r < a) return;
        if(a <= l && r <= b) {
            tree[n] = v;
            lazy[n] = make_pair(v, 1);
            return;
        }
        prop(l, r, n);
        int m = (l + r)>>1;
        upd2(a, b, v, l, m, 2*n);
        upd2(a, b, v, m + 1, r, 2*n + 1);
        tree[n] = min(tree[2*n], tree[2*n + 1]);
    }
    ll quer(int a, int b, int l, int r, int n) {
        if(b < l || r < a) return 1e18;
        if(a <= l && r <= b) return tree[n];
        prop(l, r, n);
        int m = (l + r)>>1;
        ll L = quer(a, b, l, m, 2*n);
        ll R = quer(a, b, m + 1, r, 2*n + 1);
        return min(L, R);
    }
} bit;

vector<ll> psum;
vector<int> ans;

int main() {
    scanf("%d %d", &X, &K);
    R.resize(K);
    for(int i = 0; i < K; i++) {
        scanf("%d", &R[i]);
    }
    T = R;
    for(int i = K - 1; i >= 1; i--) R[i] -= R[i - 1];
    scanf("%d", &Q);
    for(int i = 0; i < Q; i++) {
        int t, a; scanf("%d %d", &t, &a);
        query.push_back({t, a, i});
        Y.push_back(a);
    }
    sort(query.begin(), query.end());
    sort(Y.begin(), Y.end());
    Y.resize(unique(Y.begin(), Y.end()) - Y.begin());
    Yn = Y.size();
    for(int i = 0; i < Yn; i++) dy[Y[i]] = i;
    for(int i = 0; i < Q; i++) query[i].a = dy[ query[i].a ];

    bit.init();
    for(int i = 0; i < Yn; i++) bit.upd(i, i, Y[i], 0, Yn - 1, 1);

    psum.resize(K);
    for(int i = 0; i < K; i++) {
        psum[i] = i%2? R[i] : -R[i];
        if(i) psum[i] += psum[i - 1];
    }

    ans.resize(Q);
    int pos = 0;
    for(int i = 0; i < K; i++) {
        /*
        cout << i << endl;
        for(int j = 0; j < Yn; j++) {
            cout << Y[j] << ' ' << bit.quer(j, j, 0, Yn - 1, 1) << endl;
        }
        //*/
        while(pos < Q && query[pos].t < T[i]) {
            ans[ query[pos].id ] = bit.quer(query[pos].a, query[pos].a, 0, Yn - 1, 1) + (i%2? (query[pos].t - (i == 0? 0 : T[i - 1])) : -(query[pos].t - (i == 0? 0 : T[i - 1])));
            pos++;
        }
        bit.upd(0, Yn - 1, (i%2? R[i] : -R[i]), 0, Yn - 1, 1);
        int s = 0, e = Yn - 1;
        int x = -1;
        while(s <= e) {
            int m = (s + e)>>1;

            if(bit.quer(m, m, 0, Yn - 1, 1) < 0) {
                x = m;
                s = m + 1;
            }
            else e = m - 1;
        }
        if(x != -1) bit.upd2(0, x, 0, 0, Yn - 1, 1);
        s = 0, e = Yn - 1;
        x = -1;
        while(s <= e) {
            int m = (s + e)>>1;

            if(bit.quer(m, m, 0, Yn - 1, 1) > X) {
                x = m;
                e = m - 1;
            }
            else s = m + 1;
        }
        if(x != -1) bit.upd2(x, Yn - 1, X, 0, Yn - 1, 1);
    }
    while(pos < Q) {
        ans[ query[pos].id ] = bit.quer(query[pos].a, query[pos].a, 0, Yn - 1, 1) + (K%2? (query[pos].t - T[K - 1]) : -(query[pos].t - T[K - 1]));
        pos++;
    }
    for(int i = 0; i < Q; i++) {
        ans[i] = max(0, ans[i]);
        ans[i] = min(X, ans[i]);
        printf("%d\n", ans[i]);
    }
}


Measured memory_bytes: 18740