#include<bits/stdc++.h>
#define pub push_back
#define x first
#define all(a) a.begin(), a.end()
#define y second
#define mp make_pair
#define ll long long
#define db double   
using namespace std;

const int magic = 1000;

int x;
int n, m;
int a[100007];
int type[100007];
int blockCnt;
int blockMi[100007 / magic + 7][magic + 7];
int blockMa[100007 / magic + 7][magic + 7];
int blockDp1[100007 / magic + 7][magic + 7];
int blockDp2[100007 / magic + 7][magic + 7];
int blockBal[100007 / magic + 7][magic + 7];
int blockSum[100007 / magic + 7];
int blockSz[100007 / magic + 7];

void buildBlock(int v){
	int l = v * magic, r = min(n, (v + 1) * magic) - 1;
	blockSz[v] = r - l + 1;
	int bal = 0;
	for (int i = l, j = 0; i <= r; i++, j++){
		//cout << a[i] << ' ' << type[i] << endl;
		blockSum[v] += a[i];
		int val = a[i] * type[i];
		bal += val;
		if (bal > x) bal = x;
		if (bal < -x) bal = -x;
		blockMi[v][j] = bal;
		blockMa[v][j] = bal; 
		if (j){
			blockMi[v][j] = min(blockMi[v][j], blockMi[v][j - 1]);
			blockMa[v][j] = max(blockMa[v][j], blockMa[v][j - 1]);
		}
		blockBal[v][j] = bal;
	}

	for (int i = l, j = 0; i <= r; i++, j++){
		int bal1 = 0, bal2 = x;
		for (int s = j; s < blockSz[v]; s++){
			int val = a[l + s] * type[l + s];
			bal1 += val;
			bal2 += val;
			if (bal1 > x) bal1 = x;
			if (bal1 < 0) bal1 = 0;
			if (bal2 > x) bal2 = x;
			if (bal2 < 0) bal2 = 0;
		}
		//cout << v << ' ' << j << ' ' << bal1 << ' ' << bal2 << endl;
		blockDp1[v][j] = bal1;
		blockDp2[v][j] = bal2;
	}
}

int getBlockVal(int v, int st){	
	int vl = -1, vr = blockSz[v];
	while(vl + 1 < vr){
		int vm = (vl + vr) >> 1;
		if (st + blockMa[v][vm] >= x || st + blockMi[v][vm] <= 0)
			vr = vm;
		else
			vl = vm;
	}
	//cout << "---" << v << ' ' << vr << ' ' << blockMa[v][1] + st << endl;
	if (vr == blockSz[v]) return st + blockBal[v][blockSz[v] - 1];
	if (st + blockBal[v][vr] <= 0){
		return blockDp1[v][vr];
	} else {
		return blockDp2[v][vr];
	}
}

int getAns(int st, int tt){
	for (int i = 0; i < blockCnt; i++){
		//cout << "===" << st << ' ' << tt << ' ' << blockSum[i] << endl;
		if (blockSum[i] >= tt){
			for (int j = i * magic; ; j++){
				int val = a[j] * type[j];
				if (a[j] < tt){
					tt -= a[j];
					st += val;
					if (st < 0) st = 0;
					if (st > x) st = x;
				} else {
					val = type[j] * tt;
					st += val;
					if (st < 0) st = 0;
					if (st > x) st = x;
					break;
				}
			}
			return st;
		} else {
			st = getBlockVal(i, st);
			tt -= blockSum[i];
		}
	}
}

int main() {
    srand(time(NULL) + 'D' + 'E' + 'N' + 'I' + 'S' + 'S' + 'O' + 'N');
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);  
    //freopen("expr.in", "r", stdin);
    //freopen("expr.out", "w", stdout);
    //ios_base::sync_with_stdio(0);
    scanf("%d %d", &x, &n);

    int last = 0;
    int ww = -1;

    for (int i = 0; i < n; i++){
    	int val;
    	scanf("%d", &val);
    	a[i] = val - last;
    	type[i] = ww;
    	last = val;
    	ww = -ww;
    }
    a[n] = (int)1e9 + 7;
    type[n] = ww;
    n++;

    blockCnt = (n + magic - 1) / magic;

	for (int i = 0; i < blockCnt; i++) buildBlock(i);

   	scanf("%d", &m);
	while(m--){
		int w1, w2;
		scanf("%d %d", &w1, &w2);
		printf("%d\n", getAns(w2, w1));
	}
}

Measured memory_bytes: 3968