#include <bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof a)
#define mcpy(a,b) memcpy(a,b,sizeof b)
#define lb(x) ((x)&(-(x)))
#define xx first
#define yy second
#define pb push_back
#define mp make_pair
#define pii pair<int,int> 
#define inf 0x3f3f3f3f
#define N 100010
using namespace std;
typedef long long ll;
struct data{int t,a,no;bool operator <(const data& b)const{return a<b.a;}}a[N];
int n,m,q,p[N],t[N],r[N],ans[N],tag[N<<2],tag2[N<<2];
ll s[N<<2];
inline void push(int x,int l,int r){
	if(l==r)return;
	int mid=l+r>>1;
	if(tag[x]>=0){
		s[x<<1]=1ll*(mid-l+1)*tag[x],s[x<<1|1]=1ll*(r-mid)*tag[x];
		tag[x<<1]=tag[x<<1|1]=tag[x];
		tag2[x<<1]=tag2[x<<1|1]=0;
		tag[x]=-1;
	}
	if(tag2[x]){
		s[x<<1]+=1ll*(mid-l+1)*tag2[x],s[x<<1|1]+=1ll*(r-mid)*tag2[x];
		tag2[x<<1]+=tag2[x],tag2[x<<1|1]+=tag2[x];
		tag2[x]=0;
	}
}
inline void build(int x,int l,int r){
	if(l==r){s[x]=a[l].a;return;}
	int mid=l+r>>1;
	build(x<<1,l,mid),build(x<<1|1,mid+1,r);
	s[x]=s[x<<1]+s[x<<1|1];
}
inline void modify_set(int x,int l,int r,int L,int R,int v){
	push(x,L,R);
	if(l==L&&r==R){s[x]=1ll*(r-l+1)*v,tag[x]=v,tag2[x]=0;return;}
	int mid=L+R>>1;
	if(r<=mid)modify_set(x<<1,l,r,L,mid,v);
	else if(l>mid)modify_set(x<<1|1,l,r,mid+1,R,v);
	else modify_set(x<<1,l,mid,L,mid,v),modify_set(x<<1|1,mid+1,r,mid+1,R,v);
	s[x]=s[x<<1]+s[x<<1|1];
}
inline void modify_add(int x,int l,int r,int L,int R,int v){
	push(x,L,R);
	if(l==L&&r==R){s[x]+=1ll*(r-l+1)*v,tag2[x]+=v;return;}
	int mid=L+R>>1;
	if(r<=mid)modify_add(x<<1,l,r,L,mid,v);
	else if(l>mid)modify_add(x<<1|1,l,r,mid+1,R,v);
	else modify_add(x<<1,l,mid,L,mid,v),modify_add(x<<1|1,mid+1,r,mid+1,R,v);
	s[x]=s[x<<1]+s[x<<1|1];
}
inline ll query(int x,int p,int l,int r){
	push(x,l,r);
	if(l==r)return s[x];
	int mid=l+r>>1;
	if(p<=mid)return query(x<<1,p,l,mid);
	return query(x<<1|1,p,mid+1,r);
}
inline void inc(int x){
//	printf("inc %d:\n",x);for(int i=1;i<=q;i++)cout<<query(1,i,1,q)<<" ";puts("");
	if(query(1,q,1,q)+x<=m){
//		puts("no pos.");
		modify_add(1,1,q,1,q,x);
//		for(int i=1;i<=q;i++)cout<<query(1,i,1,q)<<" ";puts("\n");
		return;
	}
	int l=1,r=q;
	while(l<r){
		int mid=l+r>>1;
		if(query(1,mid,1,q)+x<=m)l=mid+1;
		else r=mid;
	}
//	printf("pos: %d\n",l);
	if(l>1)modify_add(1,1,l-1,1,q,x);
	modify_set(1,l,q,1,q,m);
//	for(int i=1;i<=q;i++)cout<<query(1,i,1,q)<<" ";puts("\n");
}
inline void dec(int x){
//	printf("dec %d:\n",x);for(int i=1;i<=q;i++)cout<<query(1,i,1,q)<<" ";puts("");
	if(query(1,1,1,q)>=x){
//		puts("no pos.");
		modify_add(1,1,q,1,q,-x);
//		for(int i=1;i<=q;i++)cout<<query(1,i,1,q)<<" ";puts("\n");
		return;
	}
	int l=1,r=q;
	while(l<r){
		int mid=l+r>>1;
		if(query(1,mid,1,q)>=x)r=mid;
		else l=mid+1;
	}
	if(query(1,l,1,q)<x)l++;
	if(l>1&&query(1,l-1,1,q)>=x)l--;
//	printf("pos: %d\n",l);
	if(l<=q)modify_add(1,l,q,1,q,-x);
	modify_set(1,1,l-1,1,q,0);
//	for(int i=1;i<=q;i++)cout<<query(1,i,1,q)<<" ";puts("\n");
}
int main(){
	mset(tag,-1);
	cin>>m>>n;
	for(int i=1;i<=n;i++)scanf("%d",&r[i]);
	cin>>q;
	for(int i=1;i<=q;i++)scanf("%d%d",&a[i].t,&a[i].a),a[i].no=i;
	sort(a+1,a+1+q);
	build(1,1,q);
//	for(int i=1;i<=q;i++)cout<<query(1,i,1,q)<<" ";puts("");
	for(int i=1;i<=q;i++)p[a[i].no]=i;
	int j=1;
	ll last=0;
	for(int i=1;i<=n;i++)if(i&1){
		while(j<=q&&a[p[j]].t<r[i]){
			if(a[p[j]].t-last)dec(a[p[j]].t-last);
			ans[j]=query(1,p[j],1,q),last=a[p[j]].t;
			j++;
		}
		dec(r[i]-last),last=r[i];
//		for(int i=1;i<=q;i++)cout<<query(1,i,1,q)<<" ";puts("");
	}else{
		while(j<=q&&a[p[j]].t<r[i]){
			if(a[p[j]].t-last)inc(a[p[j]].t-last);
			ans[j]=query(1,p[j],1,q),last=a[p[j]].t;
			j++;
		}
		inc(r[i]-last),last=r[i];
	}
	while(j<=q){
		if(a[p[j]].t-last){
			if(n&1)inc(a[p[j]].t-last);
			else dec(a[p[j]].t-last);
		}
		ans[j]=query(1,p[j],1,q),last=a[p[j]].t;
		j++;
	}
	for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
	return 0;
}
/*
100
2
2 3
2
4 50
100 50
*/

Measured memory_bytes: 10240