#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cctype>
#include <ctime>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <tuple>
#include <cmath>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

using namespace std;

#ifndef M_PI
    #define M_PI 3.14159265358979323846
#endif

#define mp make_pair
#define mt make_tuple
#define fr first
#define sc second
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef long double ld;
typedef tuple<long long, long long, long long> tlll;
typedef tuple<int, int, int> tiii;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int INF = 2000000007;
const int SZ = 3e5;
int ar[SZ], res[SZ];
int x;

struct node
{
    bool ok = false;
    int l, r, add, sval;
    node *left, *right;
};

node *build(int l, int r)
{
    node *res = new node;
    res->l = l;
    res->r = r;
    res->add = res->sval = 0;
    if (l == r)
    {
        res->sval = ar[l];
        res->ok = true;
    }
    else
    {
        int mid = (l + r) / 2;
        res->left = build(l, mid);
        res->right = build(mid + 1, r);
    }
    return res;
}

void push(node *root)
{
    if (!root->left)
        return;
    if (!root->ok)
    {
        root->left->add += root->add;
        root->right->add += root->add;
        root->add = 0;
    }
    else
    {
        root->left->sval = root->right->sval = root->sval;
        root->left->add = root->right->add = root->add;
        root->left->ok = root->right->ok = true;
        root->sval = root->add = 0;
        root->ok = false;
    }
}

int query(node *root, int i)
{
    if (i < root->l || i > root->r) return 0;
    if (root->l == root->r) return root->sval + root->add;
    push(root);
    return query(root->left, i) + query(root->right, i);
}

void add(node *root, int l, int r, int d)
{
    if (l > root->r || r < root->l) return;
    if (l <= root->l && r >= root->r)
    {
        root->add += d;
        return;
    }
    push(root);
    add(root->left, l, r, d);
    add(root->right, l, r, d);
}

void stroot(node *root, int l, int r, int d)
{
    if (l > root->r || r < root->l) return;
    if (l <= root->l && r >= root->r)
    {
        root->ok = true;
        root->sval = d;
        root->add = 0;
        return;
    }
    push(root);
    stroot(root->left, l, r, d);
    stroot(root->right, l, r, d);
}

void ans(node *root, int t1, int i1, int i2, int st)
{
    int cr = query(root, i2);
    if (st % 2 == 0)
        cr -= min(t1, cr);
    else
        cr += min(t1, x - cr);
    res[i1] = cr;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int k, q1, t, a;
    cin >> x >> k;
    vector<int> r(k + 2);
    vector<vector<tiii>> re(k + 1);
    r[0] = 0;
    for (int i = 0; i < k; i++)
        cin >> r[i + 1];
    r[k + 1] = INF;
    sort(r.begin(), r.end());

    cin >> q1;
    vector<tiii> q(q1);
    for (int i = 0; i < q1; i++)
    {
        cin >> t >> a;
        q[i] = mt(a, t, i);
    }
    sort(q.begin(), q.end());
    for (int i = 0; i < q1; i++)
    {
        int i1 = upper_bound(r.begin(), r.end(), get<1>(q[i])) - r.begin(); i1--;
        re[i1].push_back(mt(get<1>(q[i]), get<2>(q[i]), i));
        ar[i] = get<0>(q[i]);
    }

    node *root = build(0, q1 - 1);

    for (int i = 0; i < k + 1; i++)
    {
        for (auto tu : re[i])
            ans(root, get<0>(tu) - r[i], get<1>(tu), get<2>(tu), i);
        int l1 = 0, r1 = q1, step = r[i + 1] - r[i];
        while (l1 < r1)
        {
            int cr = (l1 + r1) / 2;
            int vl = query(root, cr);
            if (i % 2 == 0)
            {
                if (vl < step)
                    l1 = cr + 1;
                else
                    r1 = cr;
            }
            else
            {
                if (vl + step <= x )
                    l1 = cr + 1;
                else
                    r1 = cr;
            }
        }
        if (i % 2 == 0)
        {
            if (l1)
                stroot(root, 0, l1 - 1, 0);
            if (l1 < q1)
                add(root, l1, q1 - 1, 0 - step);
        }
        else
        {
            if (l1)
                add(root, 0, l1 - 1, step);
            if (l1 < q1)
                stroot(root, l1, q1 - 1, x);
        }
    }

    for (int i = 0; i < q1; i++)
        cout << res[i] << '\n';
    return 0;
}


Measured memory_bytes: 17408