We have a sandglass consisting of two bulbs, bulb A and bulb B. These bulbs contain some amount of sand. When we put the sandglass, either bulb A or B lies on top of the other and becomes the upper bulb. The other bulb becomes the lower bulb.

The sand drops from the upper bulb to the lower bulb at a rate of 1 gram per second. When the upper bulb no longer contains any sand, nothing happens.

Initially at time 0, bulb A is the upper bulb and contains a grams of sand; bulb B contains X-a grams of sand (for a total of X grams).

We will turn over the sandglass at time r_1,r_2,..,r_K. Assume that this is an instantaneous action and takes no time. Here, time t refer to the time t seconds after time 0.

You are given Q queries. Each query is in the form of (t_i,a_i). For each query, assume that a=a_i and find the amount of sand that would be contained in bulb A at time t_i.

Constraints

* 1≤X≤10^9
* 1≤K≤10^5
* 1≤r_1<r_2< .. <r_K≤10^9
* 1≤Q≤10^5
* 0≤t_1<t_2< .. <t_Q≤10^9
* 0≤a_i≤X (1≤i≤Q)
* All input values are integers.

Input

The input is given from Standard Input in the following format:


X
K
r_1 r_2 .. r_K
Q
t_1 a_1
t_2 a_2
:
t_Q a_Q


Output

For each query, print the answer in its own line.

Examples

Input

180
3
60 120 180
3
30 90
61 1
180 180


Output

60
1
120


Input

100
1
100000
4
0 100
90 100
100 100
101 100


Output

100
10
0
0


Input

100
5
48 141 231 314 425
7
0 19
50 98
143 30
231 55
342 0
365 100
600 10


Output

19
52
91
10
58
42
100
#include<bits/stdc++.h>
using namespace std;
inline long long getnum()
{
		long long now=0;long long fh=1;char ch=getchar();
		while(ch<'0' || ch>'9'){if(ch=='-')fh=-1;ch=getchar();}
		while(ch>='0' && ch<='9'){now=(now<<3)+(now<<1)+ch-'0';ch=getchar();}
		return now*fh;
}
int r[100003],mx[100003],mn[100003],ans,n,q,k,x,ans0[100003],ansx[100003],f,t;
int ai,ti;
int qz[100003];
int find(int t)//correct
{
	int bl=0;
	int br=k+1;
	int mid;
	while (br-bl>1)
	{
		mid=(bl+br)>>1;
		if (r[mid]>t)	br=mid;else bl=mid;

	}
	return bl;
}
int main()
{
	x=getnum();
	k=getnum();
	for (int i=1;i<=k;i++)
	{
		r[i]=getnum();
	}
	q=getnum();
	f=-1;
	ansx[0]=x;
	mx[0]=x;
	for (int i=1;i<=k;i++)
	{
		ans0[i]=ans0[i-1]+f*(r[i]-r[i-1]);
		ans0[i]=max(ans0[i],0);
		ans0[i]=min(ans0[i],x);

		ansx[i]=ansx[i-1]+f*(r[i]-r[i-1]);
		ansx[i]=max(ansx[i],0);
		ansx[i]=min(ansx[i],x);

		qz[i]=qz[i-1]+f*(r[i]-r[i-1]);

		f=-f;
	}
	f=-1;
	for (int i=1;i<=k;i++)
	{
		t+=f*(r[i]-r[i-1]);
		mn[i]=max(mn[i-1],-t);
		mx[i]=min(mx[i-1],x-t);
		f=-f;
		//printf("%d  %d %d\n",t,mn[i],mx[i]);
	}
	while(q--)
	{
	  ti=getnum();
	  ai=getnum();
	  int la=find(ti);
	  int ans;
	  if (mn[la]<=ai&&mx[la]>=ai)
	  	ans=ai+qz[la]+((la%2)*2-1)*(ti-r[la]);//la%2==1:+  ==0:-
	  else
	  	if (mn[la]>ai)
	  		ans=ans0[la]+((la%2)*2-1)*(ti-r[la]);
	  	else
	  		ans=ansx[la]+((la%2)*2-1)*(ti-r[la]);
	  ans=max(ans,0);
		ans=min(ans,x);
	  printf("%d\n", ans);
	}

}
