#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;

const int INF = 0x3f3f3f3f;

class SegmentTree {
public:
    SegmentTree(const vector<int>& a):
        treeMin(vector<int>(4 * SZ(a) + 5)),
        treeMax(vector<int>(4 * SZ(a) + 5)),
        lazyAdd(vector<int>(4 * SZ(a) + 5)),
        lazySet(vector<int>(4 * SZ(a) + 5)),
        n(SZ(a)) {
            build(0, 0, n - 1, a);
        }

    void put(int lq, int rq, int val) {
        update(0, 0, n - 1, lq, rq, 0, val);
    }

    void add(int lq, int rq, int val) {
        update(0, 0, n - 1, lq, rq, val, -1);
    }

    int getFirstSmaller(int val) {
        return getFirstSmaller(0, 0, n - 1, val);
    }
    int getFirstBigger(int val) {
        return getFirstBigger(0, 0, n - 1, val);
    }
    int get(int pos) {
        return get(0, 0, n - 1, pos);
    }
private:
    vector<int> treeMin, treeMax, lazyAdd, lazySet;
    int n;

    void updateNode(int node) {
        treeMin[node] = min(treeMin[2 * node + 1], treeMin[2 * node + 2]);
        treeMax[node] = max(treeMax[2 * node + 1], treeMax[2 * node + 2]);
    }

    void build(int node, int left, int right, const vector<int>& a) {
        lazyAdd[node] = 0;
        lazySet[node] = -1;
        if (left == right) {
            treeMin[node] = treeMax[node] = a[left];
        } else {
            int mid = (left + right) / 2;
            build(2 * node + 1, left, mid, a);
            build(2 * node + 2, mid + 1, right, a);
            updateNode(node);
        }
    }

    void split(int node, int left, int right) {
        if (lazySet[node] != -1) {
            treeMin[node] = treeMax[node] = lazySet[node];
            if (left < right) {
                lazyAdd[2 * node + 1] = lazyAdd[2 * node + 2] = 0;
                lazySet[2 * node + 1] = lazySet[2 * node + 2] = lazySet[node];
            }
            lazySet[node] = -1;
        }
        if (lazyAdd[node] != 0) {
            treeMin[node] += lazyAdd[node];
            treeMax[node] += lazyAdd[node];
            if (left < right) {
                lazyAdd[2 * node + 1] += lazyAdd[node];
                lazyAdd[2 * node + 2] += lazyAdd[node];
            }
            lazyAdd[node] = 0;
        }
    }

    void update(int node, int left, int right, int lq, int rq, int add, int vset) {
        split(node, left, right);
        if (lq <= left && right <= rq) {
            lazySet[node] = vset;
            lazyAdd[node] += add;
        } else {
            int mid = (left + right) / 2;
            if (lq <= mid) {
                update(2 * node + 1, left, mid, lq, rq, add, vset);
            }
            if (rq > mid) {
                update(2 * node + 2, mid + 1, right, lq, rq, add, vset);
            }
            split(2 * node + 1, left, mid);
            split(2 * node + 2, mid + 1, right);
            updateNode(node);
        }
    }
    int getFirstSmaller(int node, int left, int right, int val) {
        split(node, left, right);
        if (treeMin[node] > val) {
            return -1;
        }
        if (left == right) {
            return left;
        } else {
            int mid = (left + right) / 2;
            int ret = getFirstSmaller(2 * node + 2, mid + 1, right, val);
            if (ret == -1) {
                ret = getFirstSmaller(2 * node + 1, left, mid, val);
            }
            return ret;
        }
    }
    int getFirstBigger(int node, int left, int right, int val) {
        split(node, left, right);
        if (treeMax[node] < val) {
            return n;
        }
        if (left == right) {
            return left;
        } else {
            int mid = (left + right) / 2;
            int ret = getFirstBigger(2 * node + 1, left, mid, val);
            if (ret == n) {
                ret = getFirstBigger(2 * node + 2, mid + 1, right, val);
            }
            return ret;
        }
    }
    int get(int node, int left, int right, int pos) {
        split(node, left, right);
        if (left == right) {
            return treeMin[node];
        } else {
            int mid = (left + right) / 2;
            if (pos <= mid) {
                return get(2 * node + 1, left, mid, pos);
            } else {
                return get(2 * node + 2, mid + 1, right, pos);
            }
        }
    }
};

int main() {
    #ifdef LOCAL_RUN
    freopen("task.in", "r", stdin);
    freopen("task.out", "w", stdout);
    //freopen("task.err", "w", stderr);
    #endif // ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);

    int X;
    cin >> X;
    int k;
    cin >> k;
    vector<int> r(k + 2);
    r[0] = 0;
    for (int i = 1; i <= k; ++i) {
        cin >> r[i];
    }
    r[k + 1] = INF;
    k += 2;

    int q;
    cin >> q;
    vector<int> t(q), a(q);
    vector<pair<int, int>> sq(q);
    for (int i = 0; i < q; ++i) {
        cin >> t[i] >> a[i];
        sq[i] = make_pair(a[i], i);
    }
    sort(sq.begin(), sq.end());
    vector<int> v(q), qpos(q), fans(q);
    for (int i = 0; i < q; ++i) {
        v[i] = sq[i].first;
        qpos[sq[i].second] = i;
    }
    SegmentTree tree(v);
    for (int i = 0, pos = 0, sign = -1; i + 1 < k; ++i) {
        while (pos < q && t[pos] < r[i + 1]) {
            int val = tree.get(qpos[pos]);
            val += sign * (t[pos] - r[i]);
            if (val < 0) {
                val = 0;
            }
            if (val > X) {
                val = X;
            }
            fans[pos++] = val;
        }
        int diff = r[i + 1] - r[i];
        if (sign == -1) {
            int pos = tree.getFirstSmaller(diff);
            if (pos >= 0) {
                tree.put(0, pos, 0);
            }
            if (pos + 1 < q) {
                tree.add(pos + 1, q - 1, -diff);
            }
        } else {
            int pos = tree.getFirstBigger(X - diff);
            if (pos < q) {
                tree.put(pos, q - 1, X);
            }
            if (pos - 1 >= 0) {
                tree.add(0, pos - 1, diff);
            }
        }
        sign *= -1;
    }
    for (int i = 0; i < q; ++i) {
        cout << fans[i] << '\n';
    }
}


Measured memory_bytes: 10624