Problem Statement

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₁,r₂,..,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⁹
• 1≤K≤10⁵
• 1≤r₁<r₂<..<r_K≤10⁹
• 1≤Q≤10⁵
• 0≤t₁<t₂<..<t_Q≤10⁹
• 0≤a_i≤X(1≤i≤Q)
• All input values are integers.

---

Input

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

XKr1 r2 .. rKQt1 a1t2 a2:tQ aQ

Output

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

---

Sample Input 1

Copy

180360 120 180330 9061 1180 180

Sample Output 1

Copy

601120

In the first query, 30 out of the initial 90 grams of sand will drop from bulb A, resulting in 60 grams. In the second query, the initial 1 gram of sand will drop from bulb A, and nothing will happen for the next 59 seconds. Then, we will turn over the sandglass, and 1 second after this, bulb A contains 1 gram of sand at the time in question.

---

Sample Input 2

Copy

100110000040 10090 100100 100101 100

Sample Output 2

Copy

1001000

In every query, the upper bulb initially contains 100 grams, and the question in time comes before we turn over the sandglass.

---

Sample Input 3

Copy

100548 141 231 314 42570 1950 98143 30231 55342 0365 100600 10

Sample Output 3

Copy

195291105842100 ——————————————————————————————— 题目大意就是就是有一个排序好的数列，每次全部数+或-一个数，然后把<0的变成0，>X的变成X 这样我们可以算出每个询问在最后一次翻转后的状态 维护一个mn（初值为0）和一个mx（初值为沙子总数） 这样每次修改的时候我们算一下mn和mx的变换之后就可以得到所有的值在最后都是在mn'和mx之间 得到最后一次旋转后的值之后就可以直接算了 其实就是类似线段树的限制值的范围的那种操作以及区间+ - 只是这里不需要而已

#include
        
         #include
         
          #include
          
           #define LL long longusing namespace std;const int M=1e5+7;int read(){    int ans=0,f=1,c=getchar();    while(c<'0'||c>'9'){
      if(c=='-') f=-1; c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}    return ans*f;}int ans[M],T[M];struct pos{
      int T,s;}e[M];int x,k=1,n,m,sgn=-1;void calc(LL &k){
      if(k<0) k=0; if(k>x) k=x;}int main(){    x=read();    n=read(); for(int i=1;i<=n;i++) T[i]=read();    m=read(); for(int i=1;i<=m;i++) e[i].T=read(),e[i].s=read();    LL h=0,mx=x,mn=0;    for(int i=1;i<=m;i++){        while(k<=n&&T[k]<=e[i].T){            LL v=(T[k]-T[k-1])*sgn;            mx+=v; mn+=v; h+=v;            calc(mx); calc(mn);            k++;sgn*=-1;         }        LL now=e[i].s+h,nowh=(e[i].T-T[k-1])*sgn;        if(now
           
            mx) now=mx;        now+=nowh; calc(now);        printf("%lld\n",now);    }    return 0;}