#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, long long> pill;
typedef pair<double, int> pdi;
typedef pair<double, double> pdd;
const int MOD = 1000000007;
const ll oo = 1e18;
const int N = 200011;
const int MX = 19;
#define f first
#define s second
#define pb push_back
#define mp make_pair

int x , k , r[N], q;
map<int, int> org,sign;
vector<int> ac;
pii qu[N];
map<pii,ll>ans;

vector<int> da;
ll seg[4*N];

vector< pill> lzy[4*N];

void ps(pill cur , int n) {
	if (lzy[n].size() && lzy[n].back().f > 1) {
		cur.s += lzy[n].back().s;
		lzy[n].pop_back();
	}
	lzy[n].pb(cur);
}

void push(int n , int s , int e) {
	if (!lzy[n].size())
		return;
	for (int i = 0; i < lzy[n].size(); ++i) {
		int type = lzy[n][i].f;
		if (type == 0 || type == 1) {
			seg[n] = type * ((1ll) * e - s + 1) * x;
			if (s != e) {
				lzy[2 * n].clear();
				lzy[2 * n + 1].clear();
				lzy[2 * n].pb(lzy[n][i]);
				lzy[2 * n + 1].pb(lzy[n][i]);
			}
		} else {
			seg[n] += ((1ll) * e - s + 1) * lzy[n][i].s;
			if (s != e) {
				ps(lzy[n][i],2*n);
				ps(lzy[n][i],2*n+1);	
			}
		}
	}
	lzy[n].clear();
}
void update(int type , int n , int s , int e, int l , int r,ll val) {
	if(l>r)return;
	push(n,s,e);
	if (s > r || e < l)
		return;
	if (s >= l && e <= r) {
		lzy[n].pb(mp(type,1ll*val));
		push(n,s,e);
		return;
	}
	update(type, 2 * n, s, (s + e) / 2, l, r,val);
	update(type, 2 * n + 1, (s + e) / 2 + 1, e, l, r,val);
	seg[n] = seg[2 * n] + seg[2 * n + 1];
}
int idx(int ti){
	return lower_bound(da.begin(),da.end(),ti)-da.begin()+1;
}
ll get(int n , int s , int e , int at){
	push(n,s,e);
	if(s > at || e < at)
		return 0;
	if(s==e){
		return seg[n];
	}
	return get(2*n,s,(s+e)/2,at)+get(2*n+1,(s+e)/2+1,e,at);
}
int lb(int x){
	int lo = 1 , hi = da.size();
	int best = da.size()+1;
	while(lo <= hi){
		int mid = (lo +hi)/2;
		if(get(1,1,da.size(),mid) >= x){
			best = mid;
			hi = mid - 1;
		}else{
			lo = mid + 1;
		}
	}
	return best;
}
int main() {
//	freopen("input.txt", "r", stdin);
	scanf("%d%d", &x, &k);
	for (int i = 0 ; i < k ; i++) {
		scanf("%d", &r[i]);
		org[r[i]] = 1;
		ac.pb(r[i]);
	}
	scanf("%d", &q);
	for (int i = 0; i < q; ++i) {
		scanf("%d%d", &qu[i].f, &qu[i].s);
		ac.pb(qu[i].f);
		da.pb(qu[i].s);
	}
	sort(ac.begin(), ac.end());
	ac.resize(unique(ac.begin(), ac.end()) - ac.begin());
	sort(da.begin(),da.end());
	da.resize(unique(da.begin(), da.end()) - da.begin());
	for (int i = 0; i < da.size(); ++i){
		update(3,1,1,da.size(),idx(da[i]),idx(da[i]),da[i]);
	}
	bool add = 0;
	for (int i = 0; i < ac.size(); ++i){
		sign[ac[i]]= add;		
		if(org[ac[i]])add=!add;
	}

	int id = 0;
	for (int i = 0; i < ac.size(); ++i){
		int amount = ac[i] - (i?ac[i-1]:0);
		if(!sign[ac[i]]){
			int mf = lb(amount);
			update(3,1,1,da.size(),mf,da.size(),-amount);
			update(0,1,1,da.size(),1,mf-1,0ll);
		}else{
			int mf = lb(x-amount);
			update(3,1,1,da.size(),1,mf-1,amount);
			update(1,1,1,da.size(),mf,da.size(),0ll);
		}
		while(id < q && qu[id].f == ac[i]){
			ans[qu[id]] = get(1,1,da.size(),idx(qu[id].s));
			id++;
		}
	
	}
	for (int i = 0; i < q; ++i) {
		printf("%d\n",(int)ans[qu[i]]);
	}
	return 0;
}

Measured memory_bytes: 61300