#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define MP make_pair
typedef pair < int , int > pii;
typedef long long LL;
typedef pair < LL , int > pli;
const LL inf=(LL)1e17;
class LeftHeap{
public:
    pli key;
	int dis;
    LeftHeap *son[2];
};
LL res[100005],x,p[100005],spT[2][200005][30],fp[200005],dlt[200005],s[200005],e[200005];
pii qs[100005];
int n,q;
LeftHeap *cur[100005][2];
template < typename T > T MAX(T a,T b){
	return a>b?a:b;
}
template < typename T > T MIN(T a,T b){
	return a<b?a:b;
}
template < typename T > T ABS(T a){
	return a>0?a:-a;
}
template < typename T > void Swap(T &a,T &b){
    T p=a;
    a=b;
    b=p;
}
LeftHeap* create(pli val){
    LeftHeap *P=new LeftHeap;
    P->key=val;
    P->dis=1;
    P->son[0]=P->son[1]=NULL;
    return P;
}
inline int cal(LeftHeap *t){
    return t?(t->dis):0;
}
inline void restore(LeftHeap *t){
    if(cal(t->son[0])<cal(t->son[1]))
        Swap(t->son[0],t->son[1]);
    t->dis=cal(t->son[1])+1;
}
LeftHeap* merge(LeftHeap *a,LeftHeap *b){
    if(!a||!b)return a?a:b;
    if(b->key<a->key) Swap(a,b);
    a->son[1]=merge(a->son[1],b);
    restore(a);
    return a;
}
inline void popmin(LeftHeap *&P){
    LeftHeap *T=P?merge(P->son[0],P->son[1]):NULL;
    if(P) delete P;
    P=T;
}
inline void insert(LeftHeap *&P,pli val){
    P=merge(P,create(val));
}
void initalize(LL *arr,int len,int id){
	int xb,x2;
	for(xb=0;xb<200005;xb++) fill(spT[id][xb],spT[id][xb]+30,(id?(-inf):inf));
	for(xb=0;xb<len;xb++){
		spT[id][xb][0]=(LL)arr[xb];
	}
	for(x2=1;(1<<x2)<=len;x2++){
		for(xb=0;xb+(1<<x2)<=len;xb++){
			if(id==1)
				spT[id][xb][x2]=MAX(spT[id][xb][x2-1],spT[id][xb+(1<<(x2-1))][x2-1]);
			else
				spT[id][xb][x2]=MIN(spT[id][xb][x2-1],spT[id][xb+(1<<(x2-1))][x2-1]);
		}
	}
	fp[1]=0;
	for(xb=2;xb<=len;xb++){
		fp[xb]=fp[xb-1];
		while((1<<fp[xb])<=xb) fp[xb]++;
		fp[xb]--;
	}
}
inline LL Query(int F,int T,int id){
	if(id==1)
		return MAX(spT[id][F][fp[T-F+1]],spT[id][T-(1<<fp[T-F+1])+1][fp[T-F+1]]);
	else
		return MIN(spT[id][F][fp[T-F+1]],spT[id][T-(1<<fp[T-F+1])+1][fp[T-F+1]]);
}
inline int getn(int pos,LL val){
	int low=pos,hig=n-1,mid;
	if(pos>0) val-=dlt[pos-1];
	if((LL)val+(LL)Query(pos,n-1,1)<(LL)x) return n;
	while(low<hig){
		mid=((low+hig)>>1);
		if((LL)val+(LL)Query(pos,mid,1)>=(LL)x) hig=mid; else low=mid+1;
	}
	return low;
}
inline int getz(int pos,LL val){
	int low=pos,hig=n-1,mid;
	if(pos>0) val-=dlt[pos-1];
	if((LL)val+(LL)Query(pos,n-1,0)>0LL) return n;
	while(low<hig){
		mid=((low+hig)>>1);
		if((LL)val+(LL)Query(pos,mid,0)>0LL) low=mid+1; else hig=mid;
	}
	return low;
}
inline int fndp(LL val){
	int low=0,hig=n-1,mid;
	if(val<p[0]) return -1;
	while(low<hig){
		mid=(low+hig+1)>>1;
		if(p[mid]<=val) low=mid; else hig=mid-1;
	}
	//printf("Query %I64d res %d\n",val,low);
	return low;
}
int main(){
	scanf("%I64d %d",&x,&n);
	int xb,x2;
	for(xb=0;xb<n;xb++) scanf("%I64d",p+xb);
	p[n++]=2000000007;
	scanf("%d",&q);
	for(xb=0;xb<q;xb++){
		scanf("%d%d",&qs[xb].first,&qs[xb].second);
	}
	for(xb=0;xb<n;xb++){
		dlt[xb]=p[xb]-(xb>0?p[xb-1]:0);
		if(!(xb&1)) dlt[xb]=-dlt[xb];
		s[xb]=(xb==0?0:p[xb-1]);
		e[xb]=p[xb]-1;
	}
	for(xb=1;xb<n;xb++) dlt[xb]+=dlt[xb-1];
	/*printf("DLT:");
	for(xb=0;xb<n;xb++) printf("%I64d ",dlt[xb]);
	printf("\n");*/
	memset(cur,NULL,sizeof(cur));
	initalize(dlt,n,0);
	initalize(dlt,n,1);
	for(xb=0;xb<q;xb++){
		LL t=qs[xb].first,v=qs[xb].second;
		int vn=getn(0,v),vz=getz(0,v);
	//	printf("Go n->%d 0->%d\n",vn,vz);
		if(p[MIN(vn,vz)]>t) {
			int ps=fndp(t);
	//		printf("Done %d ps %d\n",xb,ps);
			if(ps==-1) res[xb]=(LL)v-(LL)t;
			else res[xb]=(LL)v+(LL)dlt[ps]+(LL)((ps&1LL)?(-1LL):1LL)*(LL)(t-p[ps]);
		}
		else if(vn<vz){
			insert(cur[vn][1],MP(t,xb));
		}
		else{
			insert(cur[vz][0],MP(t,xb));
		}
	}
	for(xb=0;xb<n;xb++){
		for(x2=0;x2<2;x2++){
			if(cur[xb][x2]){
				int vn=getn(xb+1,(x2?(x):0)),vz=getz(xb+1,(x2?(x):0)),nx=MIN(vn,vz),ny=(vn<vz)?1:0;
				while(cur[xb][x2]){
					if(cur[xb][x2]->key.first<p[nx]){
						int ps=fndp(cur[xb][x2]->key.first);
	//					printf("Exit Moving %d from %d to %d ps %d\n",cur[xb][x2]->key.second,xb,nx,ps);
						res[cur[xb][x2]->key.second]=(LL)(x2?(x):0)+dlt[ps]+(LL)((ps&1LL)?(-1LL):1LL)*(LL)((LL)cur[xb][x2]->key.first-(LL)p[ps])-dlt[xb];
						popmin(cur[xb][x2]);
					}
					else break;
				}
				cur[nx][ny]=merge(cur[nx][ny],cur[xb][x2]);
			}
		}
	}
	for(xb=0;xb<q;xb++){
		res[xb]=MIN(x,MAX(0LL,res[xb]));
		printf("%I64d\n",res[xb]);
	}
	return 0;
}


Measured memory_bytes: 115200