/*
СТРОИМ СТЕНУ РАБОТЯГИ!
█▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█
█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█
█═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═█
█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█
█═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═█
█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█
█═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═█
█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█
█═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═█
█▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄█
*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
    
     
     
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
/** Interface */
     
inline int readChar();
template <class T = int> inline T readInt(); 
template <class T> inline void writeInt( T x, char end = 0 );
inline void writeChar( int x ); 
inline void writeWord( const char *s );
     
/** Read */
     
static const int buf_size = 4096;
     
inline int getChar() {
    static char buf[buf_size];
    static int len = 0, pos = 0;
    if (pos == len) {
        pos = 0, len = fread(buf, 1, buf_size, stdin);
    }
    if (pos == len) {
        return -1;
    }
    return buf[pos++];
}
     
inline int readChar() {
    int c = getChar();
    while (c <= 32) {
        c = getChar();
    }
    return c;
}
     
template <class T>
inline T readInt() {
    int s = 1, c = readChar();
    T x = 0;
    if (c == '-')
        s = -1, c = getChar();
    while ('0' <= c && c <= '9')
        x = x * 10 + c - '0', c = getChar();
    return s == 1 ? x : -x;
}
     
/** Write */
     
static int write_pos = 0;
static char write_buf[buf_size];
     
inline void writeChar( int x ) {
    if (write_pos == buf_size)
        fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
    write_buf[write_pos++] = x;
}
     
template <class T> 
inline void writeInt( T x, char end ) {
    if (x < 0)
        writeChar('-'), x = -x;
     
    char s[24];
    int n = 0;
    while (x || !n)
        s[n++] = '0' + x % 10, x /= 10;
    while (n--)
        writeChar(s[n]);
    if (end)
        writeChar(end);
}
     
inline void writeWord( const char *s ) {     while (*s)
writeChar(*s++); }
     
struct Flusher {
    ~Flusher() {
        if (write_pos)
            fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
    }
} flusher;   
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define next next228
#define rank rank228
#define prev prev228
#define get get228
#define y1 y1228                                                         
const int MAXN = 100000;


int x;


struct funcia
{
    int h;
    int len;
    int y;
    //y - у стенки где попадает
    //h - как начинается
    //сколько времени высота h
    int len1;
    funcia(){}
    int getval(int posx) {
        if (posx <= len) {
            return h;
        }
        if (y == h) {
            return y;
        }
        if (posx <= len1) {
            if (y > h) {
                return h + posx - len;
            } else {
                return h - (posx - len);
            }
        } else {
            return y;
        }
    }
};


funcia operator +(funcia a, funcia b) {
    int s = b.getval(a.getval(0));
    int l = 0;
    int r = x;
   // cout << "opa" << endl;
    while (l != r) {
        int mid = (l + r + 1) >> 1;
        if (b.getval(a.getval(mid)) == s) {
            l = mid; 
        } else {
            r = mid - 1;
        }
    }
    //cout << "hope" << endl;
    funcia c;
    c.h = s;
    c.len = l;
    c.y = b.getval(a.getval(x));
    l = 0;
    r = x;
    while (l != r) {
        int mid = (l + r) >> 1;
        if (b.getval(a.getval(mid)) == c.y) {
            r = mid; 
        } else {
            l = mid + 1;
        }
    }
    c.len1 = l;
    //cout << "hope" << endl;
    return c;
}


int k;
vector<int> rs, t;
funcia d[3 * MAXN];


void change(int i, funcia z) {
    d[i] = z;
    while (i >> 1 > 0) {
        i >>= 1;
        d[i] = d[i << 1] + d[(i << 1) + 1];
    }
}


funcia cur;


void rmq(int v, int vl, int vr, int l, int r) {
    if (l > vr || r < vl) {
        return;
    }
    if (l <= vl && vr <= r) {
        //cout << "opass" << endl;
        //cout << v << endl;
        funcia kek = cur + d[v];
        //cout << "soso" << endl;
        cur = kek;
        //cout << "soso" << endl;
        return;
    }
    rmq(v * 2, vl, (vl + vr) / 2, l, r);
    rmq(v * 2 + 1, (vl + vr) / 2 + 1, vr, l, r);
}


int main() {    
    x = readInt();
    k = readInt();
    rs.resize(k);
    for (int i = 0; i < k; i++) {
        rs[i] = readInt();
    }
    t.resize(k);
    t[0] = rs[0];
    for (int i = 1; i < k; i++) {
        t[i] = rs[i] - rs[i - 1];
    }
    int ss = 1;
    while (ss < k) {
        ss <<= 1;
    }
    for (int i = 1; i < 2 * ss; i++) {
        d[i].h = 0;
        d[i].len = 0;
        d[i].y = x;
        d[i].len1 = x;
    }
    for (int i = 0; i < k; i++) {
        funcia kek;
        if (t[i] >= x) {
            kek.h = x;
            kek.len = x;
            kek.y = x;
            kek.len1 = x;
        } else {
            kek.h = x;
            kek.len = t[i];
            kek.y = t[i];
            kek.len1 = x;
        }
        //assert(kek.y <= x);
        change(ss + i, kek);
    }
    int q = readInt();
    for (int its = 0; its < q; its++) {
        int ts = readInt();
        int a = readInt();
        auto it = upper_bound(all(rs), ts);
        if (it == rs.begin()) {
            a = max(0, a - ts);
            writeInt(a, '\n');
            continue;
        }
        int f = it - rs.begin();
        it--;
        int ost = ts - *it;
        cur.h = 0;
        cur.len = 0;
        cur.y = x;
        cur.len1 = x;
        rmq(1, 1, ss, 1, f);
       // return 0;
        //cout << cur.h << ' ' << cur.len << ' ' << cur.y << ' ' << cur.len1 << ' ' << endl;
        int na = cur.getval(a);
      //  cout << na << ' ' << x-  na << endl;
        na = max(0, na - ost);
        int nb = x - na;
        if (f % 2 == 1) {
            swap(na, nb);
        }
        writeInt(na, '\n');
    }
    return 0;
}



Measured memory_bytes: 6144