#include <cstdio>
#include <memory.h>
#include <cstring>
#include <vector>
#include <deque>
#include <cstdlib>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <functional>
#include <set>
#include <list>
#include <map>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;

typedef unsigned long long llu;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
const ll MOD = 1e9 + 7;
const long double PI = 3.141592653589793238462643383279502884197;

int szz = 1;
int x, n;
int ttime[100002];
int psum[100002];
int spa[100002][18];
int dp[100001];

int min_tree[262144];
int max_tree[262144];

int min_find(int i, int l, int r, int le, int ri) {
	if (r < le || l > ri) return 1e9 + 7;
	if (le >= l && ri <= r) return min_tree[i];
	
	return min(min_find(i * 2, l, r, le, (le + ri) / 2), min_find(i * 2 + 1, l, r, (le + ri) / 2 + 1, ri));
}

int max_find(int i, int l, int r, int le, int ri) {
	if (r < le || l > ri) return -1e9 - 7;
	if (le >= l && ri <= r) return max_tree[i];

	return max(max_find(i * 2, l, r, le, (le + ri) / 2), max_find(i * 2 + 1, l, r, (le + ri) / 2 + 1, ri));
}

void min_init(int i) {
	if (i >= szz) return;
	min_init(i * 2); min_init(i * 2 + 1);
	min_tree[i] = min(min_tree[i * 2], min_tree[i * 2 + 1]);
}

void max_init(int i) {
	if (i >= szz) return;
	max_init(i * 2); max_init(i * 2 + 1);
	max_tree[i] = max(max_tree[i * 2], max_tree[i * 2 + 1]);
}

int cal(int o, int base) {
	int miv = 1e9 + 7;
	int l = o + 1, r = n, mid;

	while (l <= r) {
		mid = (l + r) / 2;
		if (min_find(1, o + 1, mid, 0, szz - 1) <= base) r = mid - 1;
		else l = mid + 1;
	}
	miv = min(miv, l);

	l = o + 1, r = n, mid;
	while (l <= r) {
		mid = (l + r) / 2;
		if (max_find(1, o + 1, mid, 0, szz - 1) >= base + x) r = mid - 1;
		else l = mid + 1;
	}
	miv = min(miv, l);

	return miv;
}

int go(int o) {
	if (dp[o]) return dp[o];

	int base, miv = 1e9;

	if (o % 2) base = psum[o];
	else base = psum[o] - x;

	return dp[o] = cal(o, base);
}

int fidx(int ob) {
	int now = 0;
	for (int i = 17; i >= 0; i--)
		if (ttime[spa[now][i]] <= ob) now = spa[now][i];

	return now;
}

int main() {
	int a, b, q;
	int le, ri;

	scanf("%d %d", &x, &n);
	while (szz <= n) szz *= 2;

	for (int i = 0; i < 18; i++)
		spa[n + 1][i] = n + 1;
	for (int i = 0; i < szz; i++) {
		min_tree[i + szz] = 1e9 + 7;
		max_tree[i + szz] = -1e9 - 7;
	}

	for (int i = 1; i <= n; i++) {
		scanf("%d", &ttime[i]);
		max_tree[i + szz] = min_tree[i + szz] = psum[i] = psum[i - 1] + (ttime[i] - ttime[i - 1]) * (i % 2 ? -1 : 1);
	}
	ttime[n + 1] = 1e9 + 7;
	min_init(1);
	max_init(1);

	for (int i = n; i >= 1; i--) {
		spa[i][0] = go(i);
		
		for (int j = 1; j < 18; j++)
			spa[i][j] = spa[spa[i][j - 1]][j - 1];
	}

	scanf("%d", &q);
	while (q--) {
		scanf("%d %d", &a, &b);

		spa[0][0] = cal(0, -b);
		for (int i = 1; i < 18; i++)
			spa[0][i] = spa[spa[0][i - 1]][i - 1];

		le = fidx(a);
		ri = upper_bound(ttime, ttime + n + 1, a) - ttime - 1;
		
		int ans;
		if (le % 2)	ans = psum[ri] - psum[le];
		else if (!le) ans = b + psum[ri];
		else ans = x - (psum[le] - psum[ri]);

		if (ri % 2) ans += (a - ttime[ri]);
		else ans -= (a - ttime[ri]);

		ans = min(ans, x);
		ans = max(ans, 0);

		printf("%d\n", ans);
	}
}

Measured memory_bytes: 11392