#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100 * 1000 + 10;
const int INF = 1000 * 1000 * 1000 + 10;
const int MAXQ = 100 * 1000 + 10;

typedef pair<int, int> pii;

int sum[MAXN], mx[MAXN], r[MAXN], d[MAXN], res[MAXQ], t[MAXQ];

pii seg[4 * MAXN];
int laz[4 * MAXN];
vector<pii> v;
vector<int> zeroes;

void build(int v, int f, int e)
{
	if (e - f == 1)
	{
		seg[v] = pii(d[f], f);
		return;
	}
	int mid = (f + e) / 2;
	build(2 * v, f, mid);
	build(2 * v + 1, mid, e);
	if (seg[2 * v].first >= seg[2 * v + 1].first)
		seg[v] = seg[2 * v];
	else
		seg[v] = seg[2 * v + 1];
	
}

void shift(int v)
{
	seg[2 * v].first += laz[v];
	laz[2 * v] += laz[v];
	seg[2 * v + 1].first += laz[v];
	laz[2 * v + 1] += laz[v];
	laz[v] = 0;
}

void add(int v, int f, int e, int l, int r, int val)
{
	if (f >= r || l >= e)
		return ;
	if (f >= l && e <= r)
	{
		seg[v].first += val;
		laz[v] += val;
		return;
	}
	shift(v);
	int mid = (f + e) / 2;
	add(2 * v, f, mid, l, r, val);
	add(2 * v + 1, mid, e, l, r, val);
	if (seg[2 * v].first >= seg[2 * v + 1].first)
		seg[v] = seg[2 * v];
	else
		seg[v] = seg[2 * v + 1];
}

pii get(int v, int f, int e, int l, int r)
{
	if (f >= r || l >= e)
		return pii(-INF, -1);
	if (f >= l && e <= r)
		return seg[v];
	shift(v);
	int mid = (f + e)/ 2;
	pii a = get(2 * v, f, mid, l, r);
	pii b = get(2 * v + 1, mid, e, l, r);
	if (a.first >= b.first)
		return a;
	else
		return b;
}


int main()
{
	int x, k;
	cin >> x >> k;
	for (int i = 0; i < k; i++)
		cin >> r[i + 1];
	int q;
	cin >> q;
	for (int i = 0; i < q; i++)
	{
		int a;
		cin >> t[i] >> a;
		v.push_back(pii(a, i));
	}
	sort(v.begin(), v.end());
	int cur = 0;
	for (int i = 0; i < k; i++)
	{
		if (i % 2 == 0)
			d[i + 1] = cur - (r[i + 1] - r[i]);
		else
			d[i + 1] = min(x, cur + (r[i + 1] - r[i]));
		if (d[i + 1] < 0)
		{
			zeroes.push_back(i + 1);
			cur = 0;
		}
		else 
			cur = d[i + 1];
	}
	build(1, 0, k + 1);
	int ptr = 0;
	int zptr = 0;
	int last = 0;
	while (ptr < v.size())
	{	
		while (zptr < zeroes.size() && get(1, 0, k + 1, zeroes[zptr], zeroes[zptr] + 1).first >= 0)
			zptr++;
		int dist = v[ptr].first - last;
		pii ret;
		int ls;
		if (zptr < zeroes.size())
		{
			int rem = -get(1, 0, k + 1, zeroes[zptr], zeroes[zptr] + 1).first;
			ret = get(1, 0, k + 1, 0, zeroes[zptr] + 1);
			ls = zeroes[zptr] + 1;
			if (rem < dist && ret.first != x)
			{
				rem = min(rem, x - ret.first);
				add(1, 0, k + 1, 0, zeroes[zptr] + 1, rem);
				last += rem;
				continue;
			}

		}
		else
		{	
			ls = k + 1;
			ret = get(1, 0, k + 1, 0, k + 1);
		}
		//cerr << get(1, 0, k + 1, 2, 3).first << " " << dist << " " << ret.first << " " << ret.second << endl;
		if (ret.first == x)
		{
			dist = min(dist, x - get(1, 0, k + 1, 0, ret.second).first);
			add(1, 0, k + 1, 0, ret.second, dist);
		}
		else
		{
			dist = min(dist, x - ret.first);
			add(1, 0, k + 1, 0, ls, dist);
		}
		last += dist;
		while (ptr < v.size() && last == v[ptr].first)
		{
			int idx = upper_bound(r, r + k + 1, t[v[ptr].second]) - r;
			idx--;
			int val = max(0, get(1, 0, k + 1, idx, idx + 1).first);
			//cerr << v[ptr].second << " " << val << endl;
			if (idx % 2 == 0)
				val -= t[v[ptr].second] - r[idx];
			else
				val += t[v[ptr].second] - r[idx];
			val = min(x, max(0, val));
			res[v[ptr].second] = val;
			ptr++;
		}	

	}
	for (int i = 0; i < q; i++)
		cout << res[i] << "\n";

}

Measured memory_bytes: 7796