#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define nl '\n'
typedef long long ll;
typedef long double ld;
//////////////////////////////////////////////////////////////////////

const int R = (int)1e9 + 100;
const int K = 1e5+5;
ll X,k,r[K],Q;
pair<ll,int> t[K] , a[K];
int revMap[K] , ans[K];
const int ST_ADD = 0 , ST_SET = 1;

struct Segment_Tree{// add / set updates + range max queries
  struct Node{
    bool pA , pS;
    ll toAdd , toSet , mx;
    Node(){pA=pS=false;toAdd = toSet = mx = 0ll;}
  } st[K<<2];
  
  void merge(int &x,int &lx,int &rx){
    if(lx==rx)return;
    st[x].mx = max(st[x+x].mx,st[x+1+x].mx);// for general case
  }
  
  void push(const int&x,const int &lx,const int &rx){
    if(st[x].pS){// pending set operation
      st[x].mx = st[x].toSet;

      if(lx < rx){
	if(st[x+x].pA){
	  st[x+x].pA = 0;
	  st[x+x].pS = 1;
	  st[x+x].toSet = st[x].toSet;
	}else if(st[x+x].pS){
	  st[x+x].toSet = st[x].toSet;
	}else{
	  st[x+x].pS = 1;
	  st[x+x].toSet = st[x].toSet;
	}

	if(st[x+1+x].pA){
	  st[x+1+x].pA = false;
	  st[x+1+x].pS = true;
	  st[x+1+x].toSet = st[x].toSet;
	}else if(st[x+1+x].pS){
	  st[x+1+x].toSet = st[x].toSet;
	}else{
	  st[x+1+x].pS = true;
	  st[x+1+x].toSet = st[x].toSet;
	}
      }
      
      st[x].pS = false;
    }else if(st[x].pA){// pending add operation
      st[x].mx += st[x].toAdd;

      if(lx < rx){
	if(st[x+x].pS){
	  st[x+x].toSet += st[x].toAdd;
	}else if(st[x+x].pA){
	  st[x+x].toAdd += st[x].toAdd;
	}else{
	  st[x+x].pA = true;
	  st[x+x].toAdd = st[x].toAdd;
	}

	if(st[x+1+x].pS){
	  st[x+1+x].toSet += st[x].toAdd;
	}else if(st[x+1+x].pA){
	  st[x+1+x].toAdd += st[x].toAdd;
	}else{
	  st[x+1+x].pA = true;
	  st[x+1+x].toAdd = st[x].toAdd;
	}
      }
      
      st[x].pA = false;
    }
  }
  
  int type,u,v;
  ll val;
  void upd(int x=1,int lx=1,int rx=Q){
    push(x,lx,rx);
    if(rx<u or lx>v)return;
    if(u<=lx and rx<=v){
      if(type == ST_ADD){// add
	st[x].pA = true;
	st[x].toAdd = val;
      }else if(type == ST_SET){
	st[x].pS = true;
	st[x].toSet = val;	
      }
      push(x,lx,rx);
      return;
    }
    int mid = (lx+rx)/2;
    upd(x+x,lx,mid);upd(x+1+x,mid+1,rx);
    merge(x,lx,rx);
  }
  void update(int utype,int uu,int uv,ll uval){
    type = utype;u = uu;v = uv;val = uval;
    upd();
  }

  ll qry(int x=1,int lx=1,int rx=Q){
    push(x,lx,rx);
    if(lx==rx){
      return st[x].mx;
    }
    int mid = (lx+rx)/2;
    if(u<=mid)return qry(x+x,lx,mid);
    return qry(x+1+x,mid+1,rx);
  }
  ll query(int qu){
    u = qu;
    return qry();
  }

  int lbd(int x=1,int lx=1,int rx=Q){
    push(x,lx,rx);
    if(lx==rx)return st[x].mx <= val ? 1 : 0;
    int mid = (lx+rx)/2;
    push(x+x,lx,mid);push(x+1+x,mid+1,rx);
    if( st[x+x].mx <= val )return (mid-lx+1) + lbd(x+1+x,mid+1,rx);
    return lbd(x+x,lx,mid);
  }
  int lower_bound(ll cut){// returns no of indices with value <= cut
    val = cut;
    return lbd();
  }

  int ubd(int x=1,int lx=1,int rx=Q){
    push(x,lx,rx);
    if(lx==rx)return st[x].mx >= val ? 1 : 0;
    int mid = (lx+rx)/2;
    push(x+x,lx,mid);push(x+1+x,mid+1,rx);
    if(st[x+x].mx < val) return ubd(x+1+x,mid+1,rx);
    return (rx-mid) + ubd(x+x,lx,mid);
  }
  int upper_bound(ll cut){// returns no of indices with value >= cut
    val = cut;
    return ubd();
  }
  
} T;

inline void dbg(ll timer,ll flipTime){
  cerr << "#" << timer << ',' << flipTime << endl;
  for(int j=1;j<=Q;j++)cerr << T.query(j) << ' ';
  cerr << endl;
}

int main(){
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

  cin>>X>>k;
  for(int i=1;i<=k;i++)cin>>r[i];
  cin>>Q;
  for(int i=1;i<=Q;i++){
    cin>>t[i].ff>>a[i].ff;
    a[i].ss = t[i].ss = i;
  }
  sort(t+1,t+1+Q);sort(a+1,a+1+Q);
  for(int i=1;i<=Q;i++)
    revMap[a[i].ss] = i;

  for(int i=1;i<=Q;i++)// initialize
    T.update(ST_SET,i,i,a[i].ff);

  //dbg(0,0);
  
  ll timer = 0;
  bool dec = 1;
  for(int i=1 , qi = 1;i<=k+1;i++){
    
    for(;qi <= Q and (i > k or t[qi].ff < r[i]);qi++){
      int ansIndex = t[qi].ss;
      int treeIndex = revMap[ansIndex];
      
      ll fx = T.query(treeIndex);
      ll dt = t[qi].ff - timer;
      ll answer = dec ? fx - dt : fx + dt;
      if(answer < 0)answer = 0;
      if(answer > X)answer = X;
      ans[ansIndex] = answer;
    }

    if(i > k)break;// last iteration
    
    ll delta = r[i] - timer;
    //
    if(dec){
      int cutoff = T.lower_bound(delta);
      if(cutoff > 0)
	T.update(ST_SET,1,cutoff,0);
      if(cutoff < Q)
	T.update(ST_ADD,cutoff+1,Q,-delta);
    }else{
      int cutoff = T.upper_bound(X-delta);
      if(cutoff > 0)
	T.update(ST_SET,Q+1-cutoff,Q,X);
      if(cutoff < Q)
	T.update(ST_ADD,1,Q-cutoff,delta);
    }

    //dbg(timer , r[i]);
    
    timer = r[i];
    dec ^= 1;
  }

  for(int i=1;i<=Q;i++)cout<<ans[i]<<nl;

  return 0;
};


Measured memory_bytes: 18432