#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;
const int MAXN = 100010;
int nowarn;

int x, k, r[MAXN], q, t[MAXN], a[MAXN];
int rkt[MAXN], rka[MAXN], id[MAXN], ans[MAXN];

bool cmp_t( int i, int j ) {
	return t[i] < t[j];
}
bool cmp_a( int i, int j ) {
	return a[i] < a[j];
}

void input() {
	nowarn = scanf( "%d%d", &x, &k );
	for( int i = 0; i < k; ++i )
		nowarn = scanf( "%d", r+i );
	nowarn = scanf( "%d", &q );
	for( int i = 1; i <= q; ++i ) {
		nowarn = scanf( "%d%d", t+i, a+i );
		rkt[i] = rka[i] = i;
	}
	sort( rkt+1, rkt+q+1, cmp_t );
	sort( rka+1, rka+q+1, cmp_a );
	for( int i = 1; i <= q; ++i ) id[rka[i]] = i;
}

namespace SGT {
	int val[MAXN], maxv[MAXN<<2], minv[MAXN<<2], setv[MAXN<<2], addv[MAXN<<2];
	int left, right, value;
	void maintain( int o, int L, int R ) {
		int lc = o<<1, rc = lc|1;
		if( setv[o] != -1 ) {
			maxv[o] = minv[o] = setv[o];
		} else if( L != R ) {
			maxv[o] = max( maxv[lc], maxv[rc] );
			minv[o] = min( minv[lc], minv[rc] );
		} else {
			maxv[o] = minv[o] = val[L];
		}
		maxv[o] += addv[o], minv[o] += addv[o];
	}
	void pushdown( int o, int L, int R ) {
		int M = (L+R)/2, lc = o<<1, rc = lc|1;
		if( setv[o] != -1 ) {
			if( L != R ) {
				setv[lc] = setv[rc] = setv[o];
				addv[lc] = addv[rc] = 0;
			} else {
				val[L] = setv[o];
			}
			setv[o] = -1;
		}
		if( addv[o] ) {
			if( L != R )
				addv[lc] += addv[o], addv[rc] += addv[o];
			else
				val[L] += addv[o];
			addv[o] = 0;
		}
		if( L != R )
			maintain(lc, L, M), maintain(rc, M+1, R);
	}
	void _build( int o, int L, int R ) {
		setv[o] = -1, addv[o] = 0;
		if( L == R ) {
			int i = rka[L];
			maxv[o] = minv[o] = val[L] = a[i];
			return;
		}
		int M = (L+R)/2, lc = o<<1, rc = lc|1;
		_build(lc, L, M), _build(rc, M+1, R);
		maintain(o, L, R);
	}
	void build() {
		_build(1, 1, q);
	}
	void _add( int o, int L, int R ) {
		pushdown(o, L, R);
		if( L >= left && R <= right ) {
			addv[o] += value;
			maintain(o, L, R);
			return;
		}
		int M = (L+R)/2, lc = o<<1, rc = lc|1;
		if( left <= M ) _add(lc, L, M);
		if( right > M ) _add(rc, M+1, R);
		maintain(o, L, R);
	}
	void addval( int l, int r, int v ) {
		left = l, right = r, value = v;
		_add(1, 1, q);
	}
	void _set( int o, int L, int R ) {
		pushdown(o, L, R);
		if( L >= left && R <= right ) {
			setv[o] = value, addv[o] = 0;
			maintain(o, L, R);
			return;
		}
		int M = (L+R)/2, lc = o<<1, rc = lc|1;
		if( left <= M ) _set(lc, L, M);
		if( right > M ) _set(rc, M+1, R);
		maintain(o, L, R);
	}
	void setval( int l, int r, int v ) {
		left = l, right = r, value = v;
		_set(1, 1, q);
	}
	int upper_bound( int v ) {
		if( maxv[1] <= v ) return q+1;
		int o = 1, L = 1, R = q;
		while( L != R ) {
			pushdown(o, L, R);
			int M = (L+R)/2, lc = o<<1, rc = lc|1;
			if( maxv[lc] > v ) o = lc, R = M;
			else o = rc, L = M+1;
		}
		return L;
	}
	int query( int p ) {
		int o = 1, L = 1, R = q;
		while( L != R ) {
			pushdown(o, L, R);
			int M = (L+R)/2, lc = o<<1, rc = lc|1;
			if( p <= M ) o = lc, R = M;
			else o = rc, L = M+1;
		}
		return maxv[o];
	}
}

void solve() {
	SGT::build();
	int tp = 1, tm = 0, dir = -1;
	for( int i = 0; i < k; tm = r[i], ++i, dir = -dir ) {
		while( tp <= q && t[rkt[tp]] < r[i] ) {
			int idx = rkt[tp], passt = t[idx] - tm;
			int now = SGT::query( id[idx] );
			now += dir * passt;
			now = max(now, 0), now = min(now, x);
			ans[idx] = now;
			++tp;
		}
		if( dir == -1 ) {
			int passt = r[i] - tm;
			int R = SGT::upper_bound(passt) - 1;
			if( R ) SGT::setval(1, R, 0);
			if( R != q ) SGT::addval(R+1, q, -passt);
		} else {
			int passt = r[i] - tm;
			int L = SGT::upper_bound(x-passt);
			if( L != q+1 ) SGT::setval(L, q, x);
			if( L != 1 ) SGT::addval(1, L-1, passt);
		}
	}
	while( tp <= q ) {
		int idx = rkt[tp], passt = t[idx] - tm;
		int now = SGT::query( id[idx] );
		now += dir * passt;
		now = max(now, 0), now = min(now, x);
		ans[idx] = now;
		++tp;
	}
	for( int i = 1; i <= q; ++i )
		printf( "%d\n", ans[i] );
}

int main() {
	input(), solve();
	return 0;
}


Measured memory_bytes: 9984