#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000000000000000000000001
#define LONG_INF 10000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)
long long value_bottom[200000] = {};
long long value_top[200000] = {};
int value_normal[200000] = {};
long long border_bottom[200000] = {};
long long border_top[200000] = {};
vector<long long> vertex;
int main() {
	long long x, k;
	cin >> x >> k;
	vertex.push_back(0);
	REP(i, k) {
		long long r;
		cin >> r;
		vertex.push_back(r);
	}
	k++;
	value_top[0] = x;
	for (int i = 1;i < k;++i) {
		if (i % 2 == 1) {
			//downing
			value_top[i] = value_top[i-1] - (vertex[i] - vertex[i - 1]);
			value_top[i] = max(value_top[i],(long long)0);
			value_bottom[i] = value_bottom[i-1] - (vertex[i] - vertex[i - 1]);
			value_bottom[i] = max(value_bottom[i], (long long)0);
		}else{
			//uping
			value_bottom[i] = value_bottom[i-1] + (vertex[i] - vertex[i - 1]);
			value_bottom[i] = min(value_bottom[i], x);
			value_top[i] = value_top[i-1] + (vertex[i] - vertex[i - 1]);
			value_top[i] = min(value_top[i], x);
		}
	}
	long long now = 0;
	border_top[0] = x;
	for (int i = 1;i < k;++i) {
		if (i % 2 == 1) {
			now += vertex[i] - vertex[i - 1];
			value_normal[i] = now;
			border_bottom[i] = max(border_bottom[i-1], now);
			border_top[i] = min(border_top[i - 1], x + now);
		}else{
			now -= vertex[i] - vertex[i - 1];
			value_normal[i] = now;
			border_top[i] = min(border_top[i - 1], x + now);
			border_bottom[i] = max(border_bottom[i - 1], now);
		}
	}
	int query;
	cin >> query;
	vector<long long> answers;
	for (int i = 0;i < query;++i) {
		long long a, b;
		cin >> a >> b;
		/*300
		2
			50 200
			10
			*/
		int point = lower_bound(vertex.begin(), vertex.end(),a) - vertex.begin();
		if (point == vertex.size() || vertex[point] != a) point--;
		if (point % 2 == 0) {
			//downing
			if (border_top[point] <= b) {
				answers.push_back(max(value_top[point] - (a - vertex[point]), (long long)0));
			}
			else if (border_bottom[point] >= b) {
				answers.push_back(max(value_bottom[point] - (a - vertex[point]), (long long)0));
			}
			else {
				//ok
				answers.push_back(max(b - value_normal[point] - (a - vertex[point]), (long long)0));
			}
		}
		else {
			//up
			if (border_top[point] <= b) {
				answers.push_back(min(value_top[point] + (a - vertex[point]), (long long)x));
			}
			else if (border_bottom[point] >= b) {
				answers.push_back(min(value_bottom[point] + (a - vertex[point]), (long long)x));
			}
			else {
				//ok
				answers.push_back(min(b - value_normal[point] + (a - vertex[point]), (long long)x));
			}
		}
	}
	REP(i, query) {
		cout << answers[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 8436