#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define db long double
#define ii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define FN(i, n) for (int i = 0; i < (int)(n); ++i)
#define FEN(i,n) for (int i = 1;i <= (int)(n); ++i)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repv(i,a,b) for(int i=b-1;i>=a;i--)
#define SET(A, val) memset(A, val, sizeof(A))
typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const int N=100005;
int seg[4*N],r[N],t[N],a[N],ind[N],ans[N],lazy[4*N],lazy2[4*N],t1[4*N],t2[4*N];
map<int,int> rev;
#define lc pos+pos
#define rc lc|1
void build(int low,int high,int pos)
{
  if(low==high)
    {
      seg[pos]=a[ind[low]];
      return;
    }
  int mid=(low+high)>>1;
  build(low,mid,lc); build(mid+1,high,rc);
}
void split2(int pos)
{
  if(lazy2[pos]==-1) return;
  seg[lc]=seg[rc]=lazy2[pos];
  lazy2[lc]=lazy2[rc]=lazy2[pos];
  t2[lc]=t2[rc]=t2[pos];
  lazy2[pos]=-1;
}
void split(int pos)
{
  if(!lazy[pos]) return;
  seg[lc]+=lazy[pos]; seg[rc]+=lazy[pos];
  lazy[lc]+=lazy[pos]; lazy[rc]+=lazy[pos];
  t1[lc]=t1[rc]=t1[pos];
  lazy[pos]=0;
}
void update2(int low,int high,int pos,int l,int r,int val,int timer)
{
  if(low>r || high<l || l>r) return;
  if(low>=l && high<=r)
    {
      seg[pos]=val;
      lazy2[pos]=val;
      t2[pos]=timer;
      return;
    }
  if(t1[pos]>=t2[pos]) split(pos);
  else split2(pos);
  int mid=(low+high)>>1;
  update2(low,mid,lc,l,r,val,timer); update2(mid+1,high,rc,l,r,val,timer);
}
void update(int low,int high,int pos,int l,int r,int val,int timer)
{
  if(low>r || high<l || l>r) return;
  if(low>=l && high<=r)
    {
      seg[pos]+=val;
      if(t1[pos]>t2[pos]) lazy[pos]+=val;
      else lazy[pos]=val;
      t1[pos]=timer;
      return;
    }
  if(t1[pos]>=t2[pos]) split(pos);
  else split2(pos);
  int mid=(low+high)>>1;
  update(low,mid,lc,l,r,val,timer); update(mid+1,high,rc,l,r,val,timer);
}
int query(int low,int high,int pos,int ind)
{
  if(low==high && low==ind) return seg[pos];
  if(t1[pos]>=t2[pos]) split(pos);
  else split2(pos);
  int mid=(low+high)>>1;
  if(ind<=mid) return query(low,mid,lc,ind);
  else return query(mid+1,high,rc,ind);
}
int main()
{
  std::ios::sync_with_stdio(false);
  cin.tie(NULL) ; cout.tie(NULL) ;
  int X,k,q;
  cin>>X>>k;
  rep(i,1,k+1) cin>>r[i];
  r[++k]=1e9+4;
  cin>>q;
  rep(i,1,q+1)
    {
      cin>>t[i]>>a[i];
      ind[i]=i;
    }
  memset(lazy2,-1,sizeof(lazy2));
  sort(ind+1,ind+q+1,[](int i,int j){return a[i]<a[j];});
  rep(i,1,q+1)
    rev[a[ind[i]]]=i;
  build(1,q,1);
  int curr=1;
  rep(i,1,k+1)
    {
      while(curr<=q && t[curr]<=r[i])
	{
	  int tmp=rev[a[curr]];
	  int x=query(1,q,1,tmp);
	  if(i&1) ans[curr]=x-min(x,t[curr]-r[i-1]);
	  else ans[curr]=x+min(X-x,t[curr]-r[i-1]);
	  curr++;
	}
      if(i&1)
	{
	  int diff=r[i]-r[i-1];
	  int low=1,high=q;
	  while(low<high)
	    {
	      int mid=(low+high+1)>>1;
	      if(query(1,q,1,mid)>diff) high=mid-1;
	      else low=mid;
	    }
	  if(query(1,q,1,high)>diff) high--;
	  update2(1,q,1,1,high,0,i);
	  update(1,q,1,high+1,q,-diff,i);
	}
      else
	{
	  int diff=r[i]-r[i-1];
	  int low=1,high=q;
	  while(low<high)
	    {
	      int mid=(low+high+1)>>1;
	      if(diff+query(1,q,1,mid)>X) high=mid-1;
	      else low=mid;
	    }
	  if(diff+query(1,q,1,high)>X) high--;
	  update(1,q,1,1,high,diff,i);
	  update2(1,q,1,high+1,q,X,i);
	}
    }
  rep(i,1,q+1) cout<<ans[i]<<endl;
  return 0 ;
}
