#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <complex>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << #x << " = " << (x) << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100010


int main(){
  int X;
  int n,q;
  int r[SIZE], d[SIZE], d2[SIZE];
  int max_d2[SIZE];
  int t,a,dic[SIZE];
  pair<pair<int,int>,int> query[SIZE];
  
  scanf("%d%d",&X,&n);
  
  for(int i=0;i<n;i++){
    scanf("%d",r+i);
  }
  r[n] = INF;
  r[n] = INF + 10;

  scanf("%d",&q);

  int p = 0;
  
  for(int i=0;i<q;i++){
    scanf("%d%d",&t,&a);
    query[i] = {{a,t},i};

    while(p < n && t > r[p]) p++;
    dic[i] = p;
  }

  sort(query, query+q);

  int now_a = 0;
  int last_r = 0;
  int left = 0;

  int now_d2 = 0;
  
  for(int i=0;i<=n;i++){

    if(i%2 == 0){
      now_a = max(0, now_a - (r[i] - last_r));
      now_d2 -= r[i] - last_r;
    }else{
      now_a = min(X, now_a + (r[i] - last_r));
      now_d2 += r[i] - last_r;
    }

    last_r = r[i];
    d[i] = now_a;
    d2[i] = now_d2;
    //debug(d[i]);
    //debug(d2[i]);
  }

  max_d2[0] = d2[0];
  for(int i=0;i<=n;i++){
    max_d2[i] = max(max_d2[i-1], d2[i]);
  }

  int ans[SIZE];

  int left_ri = 0;
  int last_a = 0;

  set<int> ss;
  priority_queue<pair<int,int> > pq;
  int min_ff = n;

  int l_ans[SIZE];
  
  for(int i=0;i<q;i++){
    a = query[i].first.first;
    int da = (a - last_a);
    t = query[i].first.second;
    int id = query[i].second;
    
    if(left + da < r[left_ri]){
      left += da;
    }else{
      while(left_ri < n && d2[left_ri] + a >= 0){
        pq.push({d2[left_ri],left_ri});
        left_ri++;
        left = r[left_ri] + (d2[left_ri] + a);
      }
    }

    while(pq.size() && pq.top().second > min_ff) pq.pop();
    while(pq.size() && pq.top().first + a >= X){
      int pl = pq.top().second;
      int pr = min_ff;
      ss.insert(r[pq.top().second]);
      min_ff = pq.top().second;
      pq.pop();

      now_a = X;
      l_ans[pl] = X;
      for(int j=pl+1;j<=pr;j++){
        if(j%2 == 0){
          now_a = max(0, now_a - (r[j] - r[j-1]));
        }else{
          now_a = min(X, now_a + (r[j] - r[j-1]));
        }

        l_ans[j] = now_a;
      }

      while(pq.size() && pq.top().second > min_ff) pq.pop();
    }

    //debug(dic[id]);
    //debug(min_ff);
    //debug(l_ans[dic[id]-1]);
    
    if(min_ff <= dic[id]-1){
      //debug('a');
      if(dic[id]%2 == 0){
        ans[id] = max(0, l_ans[dic[id]-1] - (t - r[dic[id]-1]));
      }else{
        ans[id] = min(X, l_ans[dic[id]-1] + (t - r[dic[id]-1]));
      }
      
    }else if(left_ri < dic[id]){
      //debug('b');

      if(dic[id]-1 == -1){
        ans[id] = max(0,a - t);
      }else{
        if(dic[id]%2 == 0){
          ans[id] = max(0, d[dic[id]-1] - (t - r[dic[id]-1]));
        }else{
          ans[id] = min(X, d[dic[id]-1] + (t - r[dic[id]-1]));
        }
      }
    }else{
      //debug('c');

      if(dic[id]%2 == 0)
        ans[id] = max(0,a + d2[dic[id]-1] - (t - r[dic[id]-1]));
      else
        ans[id] = min(X,a + d2[dic[id]-1] + (t - r[dic[id]-1]));   
    }
  }
  

  for(int i=0;i<q;i++){
    printf("%d\n",ans[i]);
  }
  
  
  return 0;
}


Measured memory_bytes: 5620