#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())

ll X,t[100005],rui[100005];
P nxt[20][100005][2];
int n,q;
struct RMQ{
	#define s (1<<18)
	ll seg[s];
	void init(){ fill(seg,seg+s,-1e18); }
	void update(int k,ll a){
		k+=s/2-1; seg[k]=a;
		while(k>0){
			k=(k-1)/2;
			seg[k]=max(seg[k*2+1],seg[k*2+2]);
		}
	}
	ll query(int a,int b,int k,int l,int r){
		if(r<a || b<l) return -1e18;
		if(a<=l && r<=b) return seg[k];
		else{
			ll vl=query(a,b,k*2+1,l,(l+r)/2);
			ll vr=query(a,b,k*2+2,(l+r)/2+1,r);
			return max(vl,vr);
		}
	}
}mx,mn;

int find_min(int p,ll v){
	//(lb,ub]
	int lb = p-1, ub = n+1;
	
	while(ub - lb > 1){
		int mid = (lb+ub)/2;
		if(-mn.query(p,mid,0,0,s/2-1) <= v){
			ub = mid;
		}
		else lb = mid;
	}
	if(ub == n+1) return INF;
	else return ub;
}
int find_max(int p,ll v){
	//(lb,ub]
	int lb = p-1, ub = n+1;
	
	while(ub - lb > 1){
		int mid = (lb+ub)/2;
		if(mx.query(p,mid,0,0,s/2-1) >= v){
			ub = mid;
		}
		else lb = mid;
	}
	if(ub == n+1) return INF;
	else return ub;
}

int main(){
	scanf("%lld",&X);
	scanf("%d",&n);
	repn(i,n) scanf("%lld",&t[i]);
	scanf("%d",&q);
	rui[0] = 0;
	mx.init(); mn.init();
	repn(i,n){
		if(i%2 == 1) rui[i] = rui[i-1] - (t[i]-t[i-1]);
		else rui[i] = rui[i-1] + (t[i]-t[i-1]);
		mx.update(i,rui[i]);
		mn.update(i,-rui[i]);
	}
	//時刻t_i時点で0 / X -> 次は？
	
	repn(i,n){
		//nxt[0][i]
		//rui[i]以下 or rui[i]+X以上
		int pos = find_min(i+1,rui[i]);
		pos = min(find_max(i+1,rui[i]+X),pos);
		if(pos == INF){
			nxt[0][i][0] = mp(INF,INF);
		}
		else if(rui[pos] <= rui[i]){
			nxt[0][i][0] = mp(pos,0);
		}
		else{
			nxt[0][i][0] = mp(pos,1);
		}
		
		//nxt[1][i]
		//rui[i]以上 or rui[i]-X以下
		pos = find_max(i+1,rui[i]);
		pos = min(find_min(i+1,rui[i]-X),pos);
		//cout << i << " " << pos << endl;
		if(pos == INF){
			nxt[0][i][1] = mp(INF,INF);
		}
		else if(rui[pos] >= rui[i]){
			nxt[0][i][1] = mp(pos,1);
		}
		else{
			nxt[0][i][1] = mp(pos,0);
		}
	}
	rep(j,18){
		repn(i,n){
			rep(x,2){
				if(nxt[j][i][x].fi > n) nxt[j+1][i][x] = mp(INF,INF);
				else{
					int k = nxt[j][i][x].fi;
					int l = nxt[j][i][x].sc;
					
					nxt[j+1][i][x] = nxt[j][k][l];
				}
			}
		}
	}
	rep(i,q){
		int tt,a; scanf("%d%d",&tt,&a);
		int id = lower_bound(t+1,t+n+1,tt) - t;
		//-a以下 or X-a以上
		int pos = find_min(1,-a);
		pos = min(find_max(1,X-a),pos);
		//cout << pos << " " << id << endl;
		if(pos > id-1){
			//easy do
			ll ans = a + rui[id-1];
			if(id%2 == 1) ans -= (tt-t[id-1]);
			else ans += (tt-t[id-1]);
			
			ans = max(ans,0ll); ans = min(ans,X);
			printf("%lld\n",ans);
		}
		else{
			//pos -> go while pos <= tt
			int p = pos,q ;
			if(rui[pos] <= -a) q = 0; else q = 1;

			for(int j=18;j>=0;j--){
				if(nxt[j][p][q].fi <= id-1){
					int pp = nxt[j][p][q].fi;
					int qq = nxt[j][p][q].sc;
					p = pp; q = qq;
				}
			}
			ll ans = (q==0?0:X) + rui[id-1] - rui[p];
			
			if(id%2 == 1) ans -= (tt-t[id-1]);
			else ans += (tt-t[id-1]);
			
			ans = max(ans,0ll); ans = min(ans,X);
			printf("%lld\n",ans);
		}
	}
}

Measured memory_bytes: 38144