/*
 ***
 Question Name:
 ***
 Question Description:
 ***
 Input:
 ***
 Output:
 
 ***
 Idea: count subsets
 */

#include <memory.h>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>

#define REP(i,s,n) for(int (i)=s; (i)<(int)(n);(i)++)
#define RIT(it,c) for(__typeof(c.begin()) it = c.begin();it!=c.end();it++)
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define MSET(m,v) memset(m,v,sizeof(m))

using namespace std;

typedef long long LL;
typedef long double LD;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<LL> vL;
typedef vector<bool> vb;
typedef unordered_set<int> ui;
typedef pair<LL,LL> pLL;

int X,K,Q;
vi R,T,A;

int comp(int a,int b,int c, int x){
    if(x>=a) return a+c;
    else if(x>=b) return x+c;
    else return b+c;
}

int main(){
    /*Write your code here*/
    cin>>X>>K;
    R.resize(K+2);
    R[0] = 0;
    R[K+1] = 1E9;
    for(int i=1;i<=K;++i) cin>>R[i];
    cin>>Q;
    T.resize(Q);
    A.resize(Q);
    for(int q=0;q<Q;++q) cin>>T[q]>>A[q];
    int a = X, b = 0, c = 0, i = 1, j = 0;
    vi ans(Q,0);
    bool merge = false;
    while(j<Q){
        if(1&i){
            while(j<Q && T[j]<=R[i]){
                int dt = T[j] - R[i-1];
                if(!merge){
                    int tmpa = a, tmpb = max(b,dt-c), tmpc = c-dt;
                    if(tmpb>=tmpa){
                        tmpb = tmpa = tmpc = 0;
                    }
                    ans[j] = comp(tmpa,tmpb,tmpc,A[j]);
                }
                else{
                    ans[j] = max(0,c-dt);
                }
                ++j;
            }
            int dt = R[i]-R[i-1];
            if(!merge){
                b = max(b,dt-c);
                c = c-dt;
                if(b>=a){
                    a = b = c = 0;
                    merge = true;
                }
            }
            else{
                a = b = 0;
                c = max(0,c - dt);
            }
            
        }
        else{
            while(j<Q && T[j]<=R[i]){
                int dt = T[j] - R[i-1];
                if(!merge){
                    int tmpa = min(a, X-c-dt), tmpb = b, tmpc = c+dt;
                    if(tmpb>=tmpa){
                        tmpa = tmpb = 0;
                        tmpc = X;
                    }
                    ans[j] = comp(tmpa,tmpb,tmpc,A[j]);
                    
                }
                else{
                    ans[j] = min(c+dt, X);
                }
                ++j;
            }
            int dt = R[i] - R[i-1];
            if(!merge){
                a = min(a,X-c-dt);
                c = c+dt;
                if(b>=a) {
                    a = b = 0;
                    c = X;
                    merge = true;
                }
            }
            else{
                a = b = 0;
                c = min(X,c + dt);
            }
        }
        ++i;
    }
    for(auto k:ans) cout<<k<<endl;
    return 0;
}

Measured memory_bytes: 2816