#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#define rep(i, a, b) for (int i = (a), _ = (b); i <= _; ++ i)
#define per(i, a, b) for (int i = (a), _ = (b); i >= _; -- i)
#define For(i, a, b) for (int i = (a), _ = (b); i < _; ++ i)
#define ri rd<int>
using namespace std;
const int maxN = 1e5 + 7;

template<class T> inline T rd() {
	bool f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = 0;
	T x = 0; for (; isdigit(c); c = getchar()) x = x * 10 + c - 48; return f ? x : -x;
}

inline void Min(int &x, int y) { y < x ? x = y : 0; }
inline void Max(int &x, int y) { y > x ? x = y : 0; }

int X, n, m;
int rev[maxN];
int t[maxN], id[maxN];

struct rec {
	int d, i;
	inline bool operator < (const rec &v) const { return d < v.d; }
}val[maxN];

namespace dsu {
	int fa[maxN];
	inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
	inline int merge(int x, int y) { return fa[find(x)] = find(y); }
}

namespace Treap {
	struct node;
	typedef node* Node;
	struct node {
		int mn, mx, d, i;
		int sz, tag, fix;
		Node lc, rc, fa;
	}*rt, a[maxN], *pool[maxN]; int cur = 0;
	Node ps[maxN];

	struct DR {
		Node lc, rc;
		DR() { lc = rc = NULL; }
	};

	inline Node newnode(int d, int i) { 
		Node x = pool[cur++];
		x->tag = 0; x->fix = rand();
		x->lc = x->rc = x->fa = 0; x->sz = 1;
		x->mn = x->mx = x->d = d, x->i = i;
		return x;
	}
	inline void delnode(Node x) { pool[--cur] = x; }
	inline void init() { For (i, 0, maxN) pool[i] = a+i; }
	inline void setlc(Node x, Node y) { y ? y->fa = x : 0; x->lc = y; }
	inline void setrc(Node x, Node y) { y ? y->fa = x : 0; x->rc = y; }

	inline void pushup(Node x) {
		x->mn = x->mx = x->d; x->sz = 1;
		if (x->lc) Min(x->mn, x->lc->mn), Max(x->mx, x->lc->mx), x->sz += x->lc->sz;
		if (x->rc) Min(x->mn, x->rc->mn), Max(x->mx, x->rc->mx), x->sz += x->rc->sz;
	}

	inline void totag(Node x, int d) {
		x->d += d, x->mn += d, x->mx += d, x->tag += d;
	}

	inline void pushdown(Node x) {
		if (x->tag) {
			if (x->lc) totag(x->lc, x->tag);
			if (x->rc) totag(x->rc, x->tag);
			x->tag = 0;
		}
	}

	inline void clear(Node x) {
		static Node stack[maxN]; int Top = 0;
		for (; x; x = x->fa) stack[++Top] = x;
		for (; Top; -- Top) pushdown(stack[Top]);
	}

	DR split_kth(Node x, int kth) {
		DR res; if (!x) return res;
		int cnt = 1 + (x->lc ? x->lc->sz : 0);
		pushdown(x);
		if (kth < cnt) {
			res = split_kth(x->lc, kth);
			if (res.lc) res.lc->fa = NULL; setlc(x, res.rc), res.rc = x;
		}
		else {
			res = split_kth(x->rc, kth - cnt);
			if (res.rc) res.rc->fa = NULL; setrc(x, res.lc), res.lc = x;
		}
		pushup(x); return res;
	}

	Node merge(Node x, Node y) {
		if (!x) return y; if (!y) return x;
		if (x->fix < y->fix) {
			pushdown(x);
			setrc(x, merge(x->rc, y));
			pushup(x); return x;
		}
		else {
			pushdown(y);
			setlc(y, merge(x, y->lc));
			pushup(y); return y;
		}
	}

	void mdf(int d) {
		totag(rt, d);
		if (rt && rt->mn < 0) {
			int x = 0; Node nw;
			while (rt && rt->mn < 0) {
				DR t = split_kth(rt, 1);
				rt = t.rc;
				x = x ? dsu::merge(x, t.lc->i) : t.lc->i;
				delnode(t.lc);
			}
			ps[x] = nw = newnode(0, x);
			rt = merge(nw, rt);
		}
		if (rt && rt->mx > X) {
			int x = 0; Node nw;
			while (rt && rt->mx > X) {
				DR t = split_kth(rt, rt->sz-1);
				rt = t.lc;
				x = x ? dsu::merge(x, t.rc->i) : t.rc->i;
				delnode(t.rc);
			}
			ps[x] = nw = newnode(X, x);
			rt = merge(rt, nw);
		}
	}

	inline int eval(int x) {
		Node p = ps[x];
		clear(p);
		return p->d;
	}

	void build() {
		static Node stack[maxN]; int Top = 0; Node nw;
		rep (i, 1, m) {
			ps[i] = nw = newnode(val[i].d, i); 

			for (; Top && stack[Top]->fix > nw->fix; -- Top) {
				setrc(stack[Top], nw->lc); pushup(stack[Top]);
				setlc(nw, stack[Top]); pushup(nw);
			}
			if (Top == 0) rt = nw;
			stack[++Top] = nw;
		}
		for (; Top > 1; -- Top)
			setrc(stack[Top-1], stack[Top]), pushup(stack[Top-1]);
	}
}

int main() {

	X = ri(), n = ri();
	rep (i, 1, n) rev[i] = ri();
	m = ri();
	rep (i, 1, m) t[i] = ri(), val[i] = (rec){ri(), i};
	sort(val+1, val+m+1);
	rep (i, 1, m) id[val[i].i] = i, dsu::fa[i] = i;

	Treap::init();
	Treap::build();

	int sgn = -1;
	for (int i = 1, j = 1, las = 0; i <= m; ++ i) {
		for (; j <= n && rev[j] <= t[i]; las = rev[j], sgn *= -1, ++ j)
			Treap::mdf(sgn * (rev[j] - las));
		printf("%d\n", max(0, min(X, Treap::eval(dsu::find(id[i])) + sgn * (t[i] - las))));
	}

	return 0;
}


Measured memory_bytes: 11776