#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;

template<typename Type> class StarrySkyTree {
public:
	unsigned size_; std::vector<Type> dat1, dat2, dat;
	inline void update_(unsigned a, unsigned b, Type x, unsigned k, unsigned l, unsigned r) {
		if (r <= a || b <= l) return;
		if (a <= l && r <= b) {
			dat2[k] += x; return;
		}
		update_(a, b, x, (k << 1), l, (l + r) >> 1);
		update_(a, b, x, (k << 1) + 1, (l + r) >> 1, r);
		dat1[k] = std::min(dat1[k << 1] + dat2[k << 1], dat1[(k << 1) + 1] + dat2[(k << 1) + 1]);
	}
	inline Type query_(unsigned a, unsigned b, unsigned k, unsigned l, unsigned r) {
		if (r <= a || b <= l) return std::numeric_limits<Type>::max();
		if (a <= l && r <= b) return dat1[k] + dat2[k];
		Type lc = query_(a, b, (k << 1), l, (l + r) >> 1);
		Type rc = query_(a, b, (k << 1) + 1, (l + r) >> 1, r);
		return std::min(lc, rc) + dat2[k];
	}
	//StarrySkyTree() : size_(0), dat(std::vector<Type>()) {};
	StarrySkyTree(int size__) {
		for (size_ = 1; size_ < size__; ) size_ <<= 1;
		dat1.resize(size_ << 1, 0);
		dat2.resize(size_ << 1, 0);
		dat.resize(size_ << 1, 0);
	}
	template<class T>
	StarrySkyTree(T begin_, T end_) {
		unsigned n = (end_ - begin_);
		for (size_ = 1; size_ < n; size_ <<= 1); dat.resize(size_ << 1, std::numeric_limits<Type>::max());
		for (unsigned i = 0; i < n; i++) dat[i + size_] = *(begin_ + i);
		for (unsigned i = size_ - 1; i > 0; i--) dat[i] = std::min(dat[i << 1], dat[(i << 1) + 1]);
	}
	inline unsigned size() { return size_; }
	inline void add(unsigned i, Type x) {
		update_(i, i + 1, x, 1, 0, size_);
	}
	inline void add(unsigned l, unsigned r, Type x) {
		update_(l, r, x, 1, 0, size_);
	}
	inline Type query(unsigned l, unsigned r) {
		return query_(l, r, 1, 0, size_);
	}
};

long long X, N, Q, R[100009], T[100009], A[100009], ans[100009]; vector<tuple<long long, long long, int>>F;
StarrySkyTree<long long> A1(1), A2(1);

pair<long long, long long>calc(long long l, long long r) {
	// [l, r)
	return make_pair(A1.query(l, r), -A2.query(l, r));
}
void adds(long long l, long long r, long long x) {
	A1.add(l, r, x);
	A2.add(l, r, -x);
}
void solve(long long U) {
	if (U == 0) return;

	long long LL = 1, RR = N + 1, MM, maxn = 1;
	for (int i = 0; i < 23; i++) {
		MM = (LL + RR) / 2;
		pair<long long, long long>G = calc(0, MM);
		if (G.first == 0 || G.second == X) RR = MM;
		else { LL = MM; maxn = MM; }
	}
	pair<long long, long long>G2 = calc(0, maxn); long long E = min(U, X - G2.second);
	adds(0, maxn, E);
	//for (int i = 0; i <= N; i++) cout << A1.query(i, i + 1) << " "; cout << endl;
	
	int cx = maxn;
	while (true) {
		long long J = A1.query(cx, cx + 1);
		long long K = A1.query(cx - 1, cx); if ((cx - 1) % 2 == 0) K -= (R[cx] - R[cx - 1]); else K += (R[cx] - R[cx - 1]);
		K = min(K, X);
		if (K <= 0 || J >= X || K - J == 0) break;
		adds(cx, cx + 1, K - J);
		if (cx == N) break;
		cx++;
	}
	solve(U - E);
}

int main() {
	cin >> X >> N;
	for (int i = 1; i <= N; i++) cin >> R[i];
	A1 = StarrySkyTree<long long>(N + 3);
	A2 = StarrySkyTree<long long>(N + 3);
	long long S = 0;
	for (int i = 0; i <= N; i++) {
		adds(i, i + 1, S);
		if (i % 2 == 0) S -= (R[i + 1] - R[i]);
		else S += (R[i + 1] - R[i]);
		S = min(X, max(0LL, S));
	}
	cin >> Q;
	for (int i = 1; i <= Q; i++) {
		cin >> T[i] >> A[i];
		F.push_back(make_tuple(A[i], T[i], i));
	}
	sort(F.begin(), F.end());
	
	long long ti = 0;

	for (int i = 0; i < F.size(); i++) {
		long long nex = get<0>(F[i]), V = get<1>(F[i]);
		solve(nex - ti); ti = nex;

		int pos1 = upper_bound(R, R + N + 1, V) - R; pos1--;
		ans[get<2>(F[i])] = A1.query(pos1, pos1 + 1);
		if (pos1 % 2 == 0) ans[get<2>(F[i])] -= (V - R[pos1]);
		else ans[get<2>(F[i])] += (V - R[pos1]);

		//cout << ti << ": "; for (int j = 0; j <= N; j++) cout << A1.query(j, j + 1) << " "; cout << endl;
	}

	for (int i = 1; i <= Q; i++) {
		cout << min(X, max(0LL, ans[i])) << endl;
	}
	return 0;
}

Measured memory_bytes: 20336