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

#define MAX_LOG 22

template<typename ty>
class MIN_SP{
	vector<ty> lcc[MAX_LOG];
	vector<ty> emp;
	vector<int> l2;
public:

	ty MAX_VAL = INT_MAX;  //need change
	int SIZE;

	void init(int size_){
		SIZE = size_;
		emp.assign(size_, MAX_VAL);
		for (int i = 0; i < MAX_LOG; i++){
			lcc[i] = emp;
		}
		l2.assign(SIZE + 1, 0);
		for (int i = 0; i <= SIZE; i++){
			l2[i] = log2(i);
		}
		emp.clear();
	}

	void set_array(ty *AA){
		for (int i = 0; i < SIZE; i++){
			lcc[0][i] = AA[i];
		}
		for (int i = 0; i + 1 < MAX_LOG; i++){
			for (int j = 0; j + (1 << i) < SIZE; j++){
				lcc[i + 1][j] = min(lcc[i][j], lcc[i][j + (1 << i)]);
			}
		}
	}
	void set_array(int size_, ty *AA){
		init(size_);
		for (int i = 0; i < SIZE; i++){
			lcc[0][i] = AA[i];
		}
		for (int i = 0; i + 1 < MAX_LOG; i++){
			for (int j = 0; j + (1 << i) < SIZE; j++){
				lcc[i + 1][j] = min(lcc[i][j], lcc[i][j + (1 << i)]);
			}
		}
	}
	void set_array(vector<ty> AA){
		if (SIZE < AA.size()){
			SIZE = AA.size();
			init(SIZE);
		}
		for (int i = 0; i < SIZE; i++){
			lcc[0][i] = AA[i];
		}
		for (int i = 0; i + 1 < MAX_LOG; i++){
			for (int j = 0; j + (1 << i) < SIZE; j++){
				lcc[i + 1][j] = min(lcc[i][j], lcc[i][j + (1 << i)]);
			}
		}
	}
	ty get_min(int a, int b){
		int rng = b - a + 1;
		int L = l2[rng];
		return min(lcc[L][a], lcc[L][b - (1 << L) + 1]);
	}
};
template<typename ty>
class MAX_SP{
	vector<ty> lcc[MAX_LOG];
	vector<ty> emp;
	vector<int> l2;
public:

	ty MIN_VAL = INT_MIN;  //need change
	int SIZE;

	void init(int size_){
		SIZE = size_;
		emp.assign(size_, MIN_VAL);
		for (int i = 0; i < MAX_LOG; i++){
			lcc[i] = emp;
		}
		l2.assign(SIZE + 1, 0);
		for (int i = 0; i <= SIZE; i++){
			l2[i] = log2(i);
		}
		emp.clear();
	}

	void set_array(ty *AA){
		for (int i = 0; i < SIZE; i++){
			lcc[0][i] = AA[i];
		}
		for (int i = 0; i + 1 < MAX_LOG; i++){
			for (int j = 0; j + (1 << i) < SIZE; j++){
				lcc[i + 1][j] = max(lcc[i][j], lcc[i][j + (1 << i)]);
			}
		}
	}
	void set_array(int size_, ty *AA){
		init(size_);
		for (int i = 0; i < SIZE; i++){
			lcc[0][i] = AA[i];
		}
		for (int i = 0; i + 1 < MAX_LOG; i++){
			for (int j = 0; j + (1 << i) < SIZE; j++){
				lcc[i + 1][j] = max(lcc[i][j], lcc[i][j + (1 << i)]);
			}
		}
	}
	void set_array(vector<ty> AA){
		if (SIZE < AA.size()){
			SIZE = AA.size();
			init(SIZE);
		}
		for (int i = 0; i < SIZE; i++){
			lcc[0][i] = AA[i];
		}
		for (int i = 0; i + 1 < MAX_LOG; i++){
			for (int j = 0; j + (1 << i) < SIZE; j++){
				lcc[i + 1][j] = max(lcc[i][j], lcc[i][j + (1 << i)]);
			}
		}
	}
	ty get_max(int a, int b){
		int rng = b - a + 1;
		int L = l2[rng];
		return max(lcc[L][a], lcc[L][b - (1 << L) + 1]);
	}
}; 

long long int x;
int k;

vector<int> r;

vector<long long int> dif;

MIN_SP<long long int> mi;
MAX_SP<long long int> mx;

int ALL;

#define MAX 500002
long long int up2[MAX];
long long int dw2[MAX];
int lcc[MAX_LOG][MAX];

long long int nex(int ich, long long int up,long long int dw,bool once=true){
	if (once){
		up2[ich] = up;
		dw2[ich] = dw;
	}
	int ne;
	{
		int mint = ich;
		int maxt = dif.size() - 1;
		while (mint + 1 < maxt){
			int mid = (mint + maxt) >> 1;
			if (mi.get_min(ich, mid) < dw){
				maxt = mid-1;
				continue;
			}
			if (mx.get_max(ich, mid) > up){
				maxt = mid-1;
				continue;
			}
			mint = mid;
		}
		if (mint != maxt){
			if (mi.get_min(ich, maxt) < dw || mx.get_max(ich, maxt) > up){
				maxt--;
			}
			else{
				mint++;
			}
		}
		ne = mint;
	}
	if (once){
		lcc[0][ich] = ne + 1;
		return 0;
	}
	if (ne + 1 >=ALL){
		return dif[ALL-1] - dw;
	}
	return -(ne + 1);
	if (!(ne& 1)){
		return nex(ne + 1,dif[ne+1]+x , dif[ne + 1]);
	}
	else{
		return nex(ne + 1, dif[ne + 1], dif[ne + 1] - x);
	}
}
void init(){
	for (int i = 0; i+1 < MAX_LOG; i++){
		for (int j = 0; j < MAX; j++){
			if (lcc[i][j] == -1)continue;
			if (lcc[i][j] == dif.size()){
				lcc[i + 1][j] = dif.size();
				continue;
			}
			lcc[i + 1][j] = lcc[i][lcc[i][j]];
		}
	}
}
long long int up(int cur){
	for (int i = MAX_LOG - 1; i >= 0; i--){
		if (lcc[i][cur] >= ALL){
			continue;
		}
		cur = lcc[i][cur];
	}
	return dif[ALL - 1] - dw2[cur];
}
vector<pair<int, int> > query;
int main(){
	memset(lcc, -1, sizeof(lcc));
	cin >> x >> k;
	for (int i = 0; i < k; i++){
		int a;
		scanf("%d", &a);
		r.push_back(a);
	}
	int q;
	scanf("%d", &q);
	for (int i = 0; i < q; i++){
		int a, t;
		scanf("%d%d", &t, &a);
		query.push_back(make_pair(t, a));
		r.push_back(t);
		r.push_back(t);
	}
	sort(r.begin(), r.end());
	int mul = -1;
	dif.push_back(0);
	long long int cur = 0;
	for (int i = 0; i < r.size(); i++){
		dif.push_back(dif.back() + mul*(r[i] - cur));
		cur = r[i];
		mul *= -1;
	}
	ALL = dif.size();
	mi.set_array(dif);
	mx.set_array(dif);
	for (int i = dif.size() - 1; i >= 0; i--){
		if (i & 1){
			nex(i, dif[i] + x, dif[i]);
		}
		else{
			nex(i, dif[i], dif[i] - x);
		}
	}
	init();

	for(int i=0;i<q;i++){
		int t=query[i].first;
		int a = query[i].second;
		ALL = upper_bound(r.begin(), r.end(), t) - r.begin();
		//x-a ~ -a
		long long int ans = nex(0, x - a, -a,false);
		if (ans < 0){
			ans = up(-ans);
		}
		printf("%lld\n", ans);
	}

	return 0;
}

Measured memory_bytes: 168644