#include <vector> 
#include <list> 
#include <map> 
#include <set> 
#include <deque> 
#include <queue> 
#include <stack> 
#include <bitset> 
#include <algorithm> 
#include <functional> 
#include <numeric> 
#include <utility> 
#include <sstream> 
#include <iostream> 
#include <iomanip> 
#include <cstdio> 
#include <cmath> 
#include <cstdlib> 
#include <cctype> 
#include <string> 
#include <cstring> 
#include <ctime> 

using namespace std;

#define _int64 long long

_int64 rmq[20][110000][2];
_int64 rmaq[20][110000][2];
_int64 r[110000];
int p[110000][20];
_int64 v[110000];

int main()
{
  _int64 initv,tmp,tmpr,gap1,gap2,mi,ma,x,now,delta;
  int i,j,o,k,left,right,mid,q,a,t;
  scanf("%lld",&x);
  scanf("%d",&k);
  for (i=0;i<k;i++)
  {
    scanf("%lld",&r[i]);
  }
  
  for (i=k-1;i>=0;i--)
  {
    if (i==k-1) v[i]=0;
    else
    {
      v[i]=v[i+1];
      if (i%2==0)
        v[i]-=r[i+1]-r[i];
      else v[i]+=r[i+1]-r[i];
    }
  }
  //cout<<"v:"<<endl;
  //for (i=0;i<k;i++)
  //  cout<<v[i]<<" "<<endl;

  r[k]=(1LL<<60);
  //v[k]=(1LL<<60);

  for (i=0;i<k;i++)
  {
    rmq[0][i][0]=v[i];
    rmq[0][i][1]=v[i];
  }
  for (i=1;i<20;i++)
    for (j=0;j<k;j++)
    {
      rmq[i][j][0]=rmq[i-1][j][0];
      if ((j+(1<<(i-1))<k)&&(rmq[i-1][j+(1<<(i-1))][0]<rmq[i][j][0]))
        rmq[i][j][0]=rmq[i-1][j+(1<<(i-1))][0];

      rmq[i][j][1]=rmq[i-1][j][1];
      if ((j-(1<<(i-1))>=0)&&(rmq[i-1][j-(1<<(i-1))][1]<rmq[i][j][1]))
        rmq[i][j][1]=rmq[i-1][j-(1<<(i-1))][1];
    }


  for (i=0;i<k;i++)
  {
    rmaq[0][i][0]=v[i];
    rmaq[0][i][1]=v[i];
  }
  for (i=1;i<20;i++)
    for (j=0;j<k;j++)
    {
      rmaq[i][j][0]=rmaq[i-1][j][0];
      if ((j+(1<<(i-1))<k)&&(rmaq[i-1][j+(1<<(i-1))][0]>rmaq[i][j][0]))
        rmaq[i][j][0]=rmaq[i-1][j+(1<<(i-1))][0];

      rmaq[i][j][1]=rmaq[i-1][j][1];
      if ((j-(1<<(i-1))>=0)&&(rmaq[i-1][j-(1<<(i-1))][1]>rmaq[i][j][1]))
        rmaq[i][j][1]=rmaq[i-1][j-(1<<(i-1))][1];
    }
//cout<<"a"<<endl;
  p[k-1][0]=k;
  for (i=k-2;i>=0;i--)
  {
    if (i%2==0)
    {
      gap1=v[i];gap2=v[i]+x;
    }
    else
    {
      gap1=v[i]-x;gap2=v[i];
    }
    //cout<<i<<endl;
    left=i;right=k;
    while (right-left>1)
    {
      mid=(left+right)/2;
      //cout<<mid<<endl;
      tmp=0;
      while ((1<<tmp)<=(mid-(i+1)+1)) tmp++;
      tmp--;
      //cout<<tmp<<endl;
      mi=rmq[tmp][i+1][0];
      if (rmq[tmp][mid][1]<mi) mi=rmq[tmp][mid][1];

      ma=rmaq[tmp][i+1][0];
      if (rmaq[tmp][mid][1]>ma) ma=rmaq[tmp][mid][1];

      if ((gap1<=mi)&&(ma<=gap2)) left=mid;
      else right=mid;
    }
    p[i][0]=right;
    //cout<<"p[i]: "<<i<<" "<<p[i][0]<<endl;
  }
//cout<<"b"<<endl;
  p[k][0]=-1;
  for (i=1;i<20;i++)
    for (j=0;j<=k;j++)
    {
      p[j][i]=p[j][i-1];
      if (p[j][i]!=-1) p[j][i]=p[p[j][i]][i-1];
    }
  initv=v[0]+r[0];
  //cout<<"initv: "<<initv<<endl;
  scanf("%d",&q);
  for (i=0;i<q;i++)
  {
    scanf("%d%d",&t,&a);
    gap1=initv-a;gap2=initv-a+x;
    //cout<<"gap: "<<gap1<<" "<<gap2<<endl;
    left=-1;right=k;
    while (right-left>1)
    {
      mid=(left+right)/2;
      tmp=0;
      //cout<<"mid: "<<mid<<endl;
      while ((1<<tmp)<=(mid+1)) tmp++;
      tmp--;
      //cout<<"tmp :"<<tmp<<endl;
      mi=rmq[tmp][0][0];
      if (rmq[tmp][mid][1]<mi) mi=rmq[tmp][mid][1];

      ma=rmaq[tmp][0][0];
      if (rmaq[tmp][mid][1]>ma) ma=rmaq[tmp][mid][1];

      //cout<<"mi ma: "<<mi<<" "<<ma<<endl;
      if ((gap1<=mi)&&(ma<=gap2)) left=mid;
      else right=mid;
    }
    now=right;
    //cout<<"now: "<<i<<" "<<t<<" "<<a<<" "<<now<<endl;
    if (r[now]>=t)
    {
      delta=initv-a;
    }
    else
    {
      for (j=19;j>=0;j--)
      {
        if (p[now][j]==-1) continue;
        if (r[p[now][j]]<t) now=p[now][j];
      }
      if (now%2==0)
        delta=v[now];
      else delta=v[now]-x;
    }
    //cout<<"delta: "<<delta<<endl;
    left=-1;right=k;
    while (right-left>1)
    {
      mid=(left+right)/2;
      if (r[mid]>=t) right=mid;
      else left=mid;
    }
    //cout<<"left: "<<left<<endl;
    if (left==-1) tmp=initv;
    else tmp=v[left];
    if (left==-1) tmpr=0;
    else tmpr=r[left];
    if (left%2==0) tmp+=(t-tmpr);
    else tmp-=(t-tmpr);
    tmp-=delta;
    if (tmp<0) tmp=0;
    if (tmp>x) tmp=x;
    printf("%lld\n",tmp);
  }
  return 0;
}

Measured memory_bytes: 80000