// Copyright (C) 2017 Sayutin Dmitry.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.

#include <iostream>
#include <vector>
#include <stdint.h>
#include <algorithm>
#include <set>
#include <map>
#include <array>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <string>
#include <assert.h>
#include <iterator>
#include <cstdint>
#include <cinttypes>
#include <string.h>
#include <random>
#include <numeric>
#include <tuple>


using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::min;
using std::abs;
using std::max;

using std::unique;
using std::sort;
using std::generate;
using std::reverse;
using std::min_element;
using std::max_element;

#ifdef LOCAL
#define LASSERT(X) assert(X)
#else
#define LASSERT(X) {}
#endif

template <typename T>
T input() {
    T res;
    cin >> res;
    LASSERT(cin);
    return res;
}

template <typename IT>
void input_seq(IT b, IT e) {
    std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>);
}

#define SZ(vec)         int((vec).size())
#define ALL(data)       data.begin(),data.end()
#define RALL(data)      data.rbegin(),data.rend()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()

#define pb push_back
#define eb emplace_back

struct node;
void recalc(node*);

std::mt19937 rnd(228410);

struct node {
    node* left;
    node* right;
    int val;
    int sz;
    int mod;
    uint32_t y;
    
    node(int v, node* l, node* r) {
        val = v;
        left = l;
        right = r;
        mod = 0;
        y = rnd();
        
        recalc(this);
    }
};

void push(node* nd) {
    nd->val += nd->mod;

    if (nd->left)
        nd->left->mod += nd->mod;
    
    if (nd->right)
        nd->right->mod += nd->mod;

    nd->mod = 0;
}

void recalc(node* nd) {
    nd->sz = 1;

    if (nd->left)
        nd->sz += nd->left->sz;

    if (nd->right)
        nd->sz += nd->right->sz;
}

node* merge(node* a, node* b) {
    if (a == NULL)
        return b;
    if (b == NULL)
        return a;

    push(a);
    push(b);
    
    if (a->y > b->y) {
        a->right = merge(a->right, b);
        recalc(a);
        return a;
    } else {
        b->left = merge(a, b->left);
        recalc(b);
        return b;
    }
}

pair<node*, node*> split(node* root, int k) {
    if (root == NULL)
        return {NULL, NULL};

    push(root);    
    
    if ((root->left == NULL ? 0 : root->left->sz) >= k) {
        auto spl = split(root->left, k);
        root->left = spl.second;
        recalc(root);
        
        return {spl.first, root};
    } else {
        auto spl = split(root->right, k - 1 - (root->left == NULL ? 0 : root->left->sz));
        root->right = spl.first;
        recalc(root);
        
        return {root, spl.second};
    }
}

node* get_k(node* root, int k) {
    if (root == NULL)
        return NULL;

    push(root);
    
    if ((root->left == NULL ? 0 : root->left->sz) > k)
        return get_k(root->left, k);
    else if ((root->left == NULL ? 0 : root->left->sz) == k)
        return root;
    else
        return get_k(root->right, k - 1 - (root->left == NULL ? 0 : root->left->sz));
}

int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    // code here.
    int x = input<int>();
    int k = input<int>();

    vector<int> rs(k);
    input_seq(ALL(rs));

    using std::tuple;
    using std::get;
    
    int q = input<int>();
    vector<tuple<int, int, int>> queries(q);
    vector<int> q_ans(q, -100);

    // (a_i, t_i, i)
    for (int i = 0; i != q; ++i) {
        get<1>(queries[i]) = input<int>();
        get<0>(queries[i]) = input<int>();
        get<2>(queries[i]) = i;
    }

    std::sort(ALL(queries));

    // (r[i], -1)
    // (t_id, q_id)
    vector<pair<int, int>> events;

    for (int val: rs)
        events.eb(val, -1);

    for (int i = 0; i != SZ(queries); ++i)
        events.eb(get<1>(queries[i]), i);

    std::sort(ALL(events));

    node* root = NULL;
    for (int i = 0; i != SZ(queries); ++i)
        root = merge(root, new node(get<0>(queries[i]), NULL, NULL));

    int del_first = 0;
    int del_last  = 0;

    int prev_t = 0;
    int cur_dir = -1;
    for (auto& ev: events) {
        root->mod += cur_dir * (ev.first - prev_t);
        prev_t = ev.first;
        
        node* last_del = NULL;
        while (root) {
            auto fst = get_k(root, 0);

            if (fst->val < 0) {
                root = split(root, 1).second;
                del_first += 1;
                last_del = fst;
            } else {
                break;
            }
        }
        
        if (last_del) {
            last_del->val = 0;
            del_first -= 1;
            root = merge(last_del, root);
        }

        last_del = NULL;
        while (root) {
            auto lst = get_k(root, root->sz - 1);

            if (lst->val > x) {
                root = split(root, root->sz - 1).first;
                del_last += 1;
                last_del = lst;
            } else {
                break;
            }
        }
        
        if (last_del) {
            last_del->val = x;
            del_last -= 1;
            root = merge(root, last_del);
        }

        if (ev.second == -1)
            cur_dir = -cur_dir;
        else {
            int ind = ev.second;
            ind -= del_first;
            if (ind < 0)
                ind = 0;
            if (ind >= root->sz)
                ind = root->sz - 1;

            q_ans[get<2>(queries[ev.second])] = get_k(root, ind)->val;
        }
    }
    
    
    for (int val: q_ans)
        cout << val << "\n";
    
    return 0;
}


Measured memory_bytes: 9456