#include <bits/stdc++.h>
using namespace std;using ll=long long;using uint=unsigned int;using pii=pair<int,int>;using pll=pair<ll,ll>;using ull = unsigned long long;using ld=long double;template<typename T>void _(const char*s,T h){cerr<<s<<" = "<<h<<"\n";}template<typename T,typename...Ts>void _(const char*s,T h,Ts...t){int b=0;while(((b+=*s=='(')-=*s==')')!=0||*s!=',')cerr<<*s++;cerr<<" = "<<h<<",";_(s+1,t...);}// break continue pop_back 998244353
#define int ll
#define pii pll
#define f first
#define s second
#define pb emplace_back
#define forn(i,n) for(int i=0;i<(n);++i)
#define sz(a)((int)(a).size())
#define sqr(x) ((x)*(x))
struct init{init(){cin.tie(0);iostream::sync_with_stdio(0);cout<<fixed<<setprecision(10);cerr<<fixed<<setprecision(5);}~init(){
#ifdef LOCAL
#define dbg(...) _(#__VA_ARGS__,__VA_ARGS__)
cerr<<"Time elapsed: "<<(double)clock()/CLOCKS_PER_SEC<<"s.\n";
#else
#define dbg(...) 
#endif
}}init;template<typename T,typename U>void upx(T&x,U y){if(x<y)x=y;}template<typename T,typename U>void upn(T&x,U y){if(x>y)x=y;}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());const int D=4,dx[]={+1,0,-1,0},dy[]={0,+1,0,-1};
 
const int N=1e5+5,OO=1e9;
int len,n,q;
int a[N],al[N];
pii qs[N];
struct node{
    int val,tag,mod;
    node(){
        val=0;
        tag=0;
        mod=0;
    }
} t[N*4];
int sh=1;
void applyadd(int v,int x){ 
    // dbg(t[v].val,)
    if(t[v].tag==2){
        t[v].val+=x;
        t[v].mod+=x;
    }else{
        // if(t[v].tag!=1)t[v].mod=0;
        t[v].tag=1;
        t[v].val+=x; //<--
        t[v].mod+=x; //<--
    }   
}
void applykek(int v,int x){ 
    t[v].tag=2;
    t[v].val=x; //<--
    t[v].mod=x; //<--
}
void push(int v){//tl,tr мб не надо
    if(t[v].tag==1){
        applyadd(v+v,t[v].mod);
        applyadd(v+v+1,t[v].mod); 
        t[v].mod=0; //<--
        t[v].tag=0;
    }else if(t[v].tag==2){
        applykek(v+v,t[v].mod);
        applykek(v+v+1,t[v].mod); 
        t[v].mod=0; //<--
        t[v].tag=0;
    }
}
void recalc(int v){
    t[v].val=max(t[v+v].val,t[v+v+1].val); //<--
}
void build(int z){
    while(sh<z)sh*=2;
    forn(i,z)t[i+sh].val=al[i];
    for(int i=sh-1;i>0;--i)recalc(i);
}
int get(int v,int tl,int tr,int i){
    if(tl==tr)return t[v].val;
    push(v);
    int tm=(tl+tr)/2;
    if(tm>=i)return get(v+v,tl,tm,i); //<--
    return get(v+v+1,tm+1,tr,i); //<--
}
void add(int v,int tl,int tr,int l,int r,int val){
    if(l<=tl&&tr<=r){
        applyadd(v,val);
        return;
    }
    push(v);
    int tm=(tl+tr)/2;
    if(tm>=l)add(v+v,tl,tm,l,r,val);
    if(tm+1<=r)add(v+v+1,tm+1,tr,l,r,val);
    recalc(v);
}
void add(int l,int r,int val){
    if(l>r)return;
    add(1,0,sh-1,l,r,val);
}
void kek(int v,int tl,int tr,int l,int r,int val){
    if(l<=tl&&tr<=r){
        applykek(v,val);
        return;
    }
    push(v);
    int tm=(tl+tr)/2;
    if(tm>=l)kek(v+v,tl,tm,l,r,val);
    if(tm+1<=r)kek(v+v+1,tm+1,tr,l,r,val);
    recalc(v);
}
void kek(int l,int r,int val){
    if(l>r)return;
    kek(1,0,sh-1,l,r,val);
}
int gpo(int v,int tl,int tr,int d){
    if(tl==tr)return tl;
    push(v);
    int tm=(tl+tr)/2;
    if(t[v+v].val<=d)return gpo(v+v+1,tm+1,tr,d);
    return gpo(v+v,tl,tm,d); //<--
}
int gpo(int d){
    if(t[1].val<=d)return sh;
    return gpo(1,0,sh-1,d);
}
int dir=-1;
void f(int d,int rev){
    if(dir==-1){
        int pos=gpo(d);
        add(pos,sh-1,-d);
        kek(0,pos-1,0);
    }else{
        int pos=gpo(len-d);
        add(0,pos-1,d);
        kek(pos,sh-1,len);
    }
    if(rev)dir=-dir;
}
int g(int x){
    return get(1,0,sh-1,x);
}
int32_t main(){
    cin>>len>>n;
    forn(i,n)cin>>a[i];
    cin>>q;
    forn(i,q){
        cin>>qs[i].f>>qs[i].s;
        al[i]=qs[i].s;
    }
    sort(al,al+q);
    build(q);
    int pos=-1,last=0;
    forn(i,q){
        int cur=qs[i].f,x=lower_bound(al,al+q,qs[i].s)-al;
        while(pos+1<n&&a[pos+1]<=cur){
            pos++;
            f(a[pos]-last,1);
            last=a[pos];
        }
        f(cur-last,0);
        last=cur;
        cout<<g(x)<<'\n';
    }
    return 0;
}

Measured memory_bytes: 16176