#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define gc getchar
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define x1 uvuvwevwevwe
#define y1 onyetenyevwe
#define x2 ugwemubwem
#define y2 ossas
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
template <typename T> void scan(T &angka){
	angka=0;char input=gc();T kali=1;
	while(!(48<=input&&input<=57)){	if(input=='-')	kali=-1;input=gc();}
	while(48<=input&&input<=57)	angka=(angka<<3)+(angka<<1)+input-48,input=gc();angka*=kali;
}
template <typename T1,typename T2> void scan(T1 &angka1,T2 &angka2){
	scan(angka1);scan(angka2);
}
const int MAXK=100000;
const int MAXQ=100000;
const int treesize=131072;
struct trio{
	int fi,se,th;
	trio(int _fi,int _se,int _th){
		fi=_fi;
		se=_se;
		th=_th;
	}
	trio(){
	}
	bool operator<(const trio &other)const{
		if(fi!=other.fi)
			return (fi<other.fi);
		if(se!=other.se)
			return (se<other.se);
		return (th<other.th);
	}
};
struct segtree{
	int terbesar,pilihan;
	segtree(int _terbesar,int _pilihan){
		terbesar=_terbesar,pilihan=_pilihan;
	}
	segtree(){
	}
	bool operator<(const segtree &other)const{
		if(terbesar!=other.terbesar)
			return (terbesar<other.terbesar);
		return (pilihan>other.pilihan);
	}
};
//kalau batas==-1 batas not found atau lebih besar dari poshenti pertama
//nilai batas itu nyimpannya indeks terakhir yang dapat di update
int totalgram,totalbalik,posbalik[MAXK+5],batas=-1,nilai[MAXK+5];
bool batasfix=false;			//menyatakan apakah sudah depends on batas atau masih butuh pake poshenti
//fist itu posisinya , second itu yang terdekat di sebelah kirinya
set <pii> poshenti;
vector <int> event;
//first itu gram awal, second itu time, trio itu id;

//sambil linesweep sambil menjawab makanya penting idxquery
vector <trio> querylist;
int ans[MAXQ+5],q,idxquery=0;

//variabel segment tree yang terbesar sama yang terkiri terbesar yang manakah itu
int lazy[(treesize<<1)+5]={};
segtree tree[(treesize<<1)+5],dummy(-1,-1);

//segtree
void pullup(int indeks){
	tree[indeks]=max(tree[indeks<<1],tree[(indeks<<1)|1]);
}
void pushdown(int indeks){
	tree[(indeks<<1)].terbesar+=lazy[indeks];
	lazy[(indeks<<1)]+=lazy[indeks];
	tree[(indeks<<1)|1].terbesar+=lazy[indeks];
	lazy[(indeks<<1)|1]+=lazy[indeks];
	lazy[indeks]=0;
}
void buatsegtree(int kiri,int kanan,int indeks){
	lazy[indeks]=0;
	if(kiri==kanan)
	{
		tree[indeks].terbesar=nilai[kiri];
		tree[indeks].pilihan=kiri;
		//assert(tree[indeks].terbesar<=totalgram);
		return;
	}
	int mid=(kiri+kanan)>>1;
	buatsegtree(kiri,mid,indeks<<1);
	buatsegtree(mid+1,kanan,(indeks<<1)|1);
	pullup(indeks);
	//assert(tree[indeks].terbesar<=totalgram);
}
void buatsegtree(){
	buatsegtree(0,totalbalik,1);
}
void update(int kiri,int kanan,int indeks,int l,int r,int tambah){
	if(l<=kiri&&kanan<=r)
	{
		lazy[indeks]+=tambah;
		tree[indeks].terbesar+=tambah;
		//assert(tree[indeks].terbesar-totalgram<=50);
		//assert(tree[indeks].terbesar<=totalgram);
		return;
	}
	if(l>kanan||r<kiri)
		return;
	pushdown(indeks);
	int mid=(kiri+kanan)>>1;
	update(kiri,mid,indeks<<1,l,r,tambah);
	update(mid+1,kanan,(indeks<<1)|1,l,r,tambah);
	pullup(indeks);
	//assert(tree[indeks].terbesar<=totalgram);
}
void update(int l,int r,int tambah){
	update(0,totalbalik,1,l,r,tambah);
}
segtree query(int kiri,int kanan,int indeks,int l,int r){
	if(l<=kiri&&kanan<=r)
		return tree[indeks];
	if(l>kanan||r<kiri)
		return dummy;
	pushdown(indeks);
	int mid=(kiri+kanan)>>1;
	return max(query(kiri,mid,indeks<<1,l,r),query(mid+1,kanan,(indeks<<1)|1,l,r));
}
segtree query(int l,int r){
	return query(0,totalbalik,1,l,r);
}
//done segtree

int gradien(int indeks){			//dari indeksnya diketahui, arahnya akan kemana
	if(indeks&1)			//kalau ganjil
		return -1;
	else
		return 1;
}

//linesweep
void masukkanevent(LL waktu){
	if(waktu>totalgram)			//melebihi MAX TIME
		return;
	event.pb(waktu);
}
void buatevent(){
	for(int i=0;i<q;i++)				//ambil semua query sebagai event
		masukkanevent(querylist[i].fi);
		
	auto it=poshenti.begin();
	int mulaiupdate=0;			//wakktu kapan suatu titik mulai diupdate
	for(int i=1;i<=totalbalik;i++)
	{
		//update nilai dari waktu mulai update
		while((it!=poshenti.end())&&(it->se<i))
		{
			assert(it->se==i-1);
			mulaiupdate+=posbalik[i]-it->fi;				//karena butuh waktu sekian lama agar pos hentinya hilang
			it=next(it);
			masukkanevent(mulaiupdate);
		}
		
		//masukkan juga ke event kapan suatu titik sampai batas maksimalnya
		masukkanevent(mulaiupdate+(totalgram-nilai[i]));
	}
	assert(it==poshenti.end());
	masukkanevent(totalgram);			//kasus sudah full semua
}
bool isfix(){
	if(batas==-1)
		return false;
	if(poshenti.size()==0)
		return true;
	return (batas<=poshenti.begin()->se);
}
int tentbatas(){			//tentukan batas update;
	if(batasfix)
		return batas;
	if(poshenti.size())
		return poshenti.begin()->se;
	return totalbalik;
}
void updatebatas(int batasupdate){
	auto temp=query(0,batasupdate);
	if(temp.terbesar==totalgram)
		batas=temp.pilihan-1;
}
int binser(int waktu){				//return indeks posisi balik terdekat di sebelah kirinya waktu
	int bawah=1,atas=totalbalik,mid;
	while(bawah<=atas)
	{
		mid=(bawah+atas)>>1;
		if(posbalik[mid]>=waktu)
			atas=mid-1;
		else
			bawah=mid+1;
	}
	if(bawah>totalbalik||posbalik[bawah]>waktu)
		return atas;
	return bawah;
}
void jawabquery(int gramawal){
	while(idxquery<querylist.size())
	{
		auto kwery=querylist[idxquery];
		if(kwery.fi!=gramawal)
			break;
		int posnow=kwery.se;
		int tempatbalik=binser(kwery.se);
		ans[kwery.th]=(query(tempatbalik,tempatbalik).terbesar)+(gradien(tempatbalik))*(posnow-posbalik[tempatbalik]);
		ans[kwery.th]=min(totalgram,ans[kwery.th]);
		ans[kwery.th]=max(0,ans[kwery.th]);
		idxquery++;
	}
}
void updateposhenti(int delta){
	auto temp=*poshenti.begin();
	poshenti.erase(temp);
	//assert(temp.fi+delta<=posbalik[temp.se+1]);
	if(temp.fi+delta!=posbalik[temp.se+1])
	{
		temp.fi+=delta;
		poshenti.insert(temp);
	}
}
void printsemua(){
	cout<<endl;
	cout<<"printing all"<<endl;
	for(int i=1;i<=totalbalik;i++)
		cout<<query(i,i).terbesar<<" ";
	cout<<endl<<endl<<endl;
}
void linesweep(){
	sort(all(event));
	event.resize(unique(all(event))-event.begin());
	batasfix=(isfix());
	int tadi=0,delta;			//delta itu pertambahan waktunya
	//printsemua();
	for(int noevent=0;noevent<event.size();noevent++)
	{
		//cout<<"eventnya "<<event[noevent]<<endl;
		//cout<<"pada "<<idxquery<<" "<<batas<<endl;
		delta=event[noevent]-tadi;
		tadi=event[noevent];
		
		int batasupdate=tentbatas();
		//cout<<"batas updatenya "<<batasupdate<<endl;
		update(0,batasupdate,delta);
		
		updatebatas(batasupdate);
		
		//urus poshentinya juga di tambah, incase depends on poshenti
		if(!batasfix&&poshenti.size())			//kasus dimana pasti poshenti.begin() yang dipake
			updateposhenti(delta);
		
		if(!batasfix)
			batasfix=isfix();

		jawabquery(event[noevent]);
		//printsemua();
	}
}
//akhir linesweep

void simulasikan(){			//simulasikan untuk nilai 0 paling pertama,generate nilai awal, generate poshenti
	int now=0,tadi;
	
	posbalik[0]=0;
	nilai[0]=now;
	
	for(int i=1;i<=totalbalik;i++)
	{
		tadi=now;
		now+=gradien(i-1)*(posbalik[i]-posbalik[i-1]);
		if(now<0)
		{
			poshenti.insert(mp(posbalik[i-1]+tadi,i-1));
			now=0;
		}
		else if(now>=totalgram)
		{
			if(batas==-1)			//tujuannya mencari batas paling pertama
				batas=i-1;
			now=totalgram;
		}
		nilai[i]=now;
	}
}
void perbaikians(){
	for(int i=0;i<q;i++)
		ans[i]=totalgram-ans[i];
}
void jawabsemua(){
	for(int i=0;i<q;i++)
		printf("%d\n",ans[i]);
}
void printurutanquery(){
	cout<<"ini urutannya "<<endl;
	for(auto kweri:querylist)
		cout<<kweri.th<<" ";
	cout<<endl;
}
int main()
{
	scan(totalgram,totalbalik);
	posbalik[0]=0;
	for(int i=1;i<=totalbalik;i++)
		scan(posbalik[i]);
	scan(q);
	querylist.resize(q);
	for(int i=0;i<q;i++)
	{
		querylist[i].th=i;
		scan(querylist[i].se,querylist[i].fi);
		querylist[i].fi=totalgram-querylist[i].fi;
	}
	sort(all(querylist));
	//printurutanquery();
	simulasikan();
	buatsegtree();
	buatevent();
	linesweep();
	perbaikians();
	jawabsemua();
	//assert(batas==-1);
}

Measured memory_bytes: 8824