#include <bits/stdc++.h>
using namespace std;
// nichijou
#define REP(i,a,b) for (int i(a); i < (b); ++i)
#define RP(i,n) REP(i,0,n)
#define PER(i,a,b) for(int i((a)-1); i >= (b); --i)
#define PR(i,n) PER(i,n,0)
#define REP1(i,a,b) REP(i,a,(b)+1)
#define RP1(i,n) REP1(i,1,n)
#define PER1(i,a,b) PER(i,(a)+1,b)
#define PR1(i,n) PER1(i,n,1)
#define DO(n) RP(__i,n)
template<class T>
void cmax(T & a, T b) {a = max(a, b);}
template<class T>
void cmin(T & a, T b) {a = min(a, b);}

// data type
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define F first
#define S second

// STL container
typedef vector<int> vi;
typedef vector<ll> vll;
#define SZ(a) ((int)(a).size())
#define ALL(a) begin(a), end(a)
#define CLR(a) (a).clear()
#define BK(a) ((a).back())
#define FT(a) ((a).front())
#define DB(a) (a).pop_back()
#define DF(a) (a).pop_front()
#define PB push_back
#define EB emplace_back

/* I gave you my heart and then you turned around. */
void _BG(const char * s) {}
template<class T, class ... TT>
void _BG(const char * s,T a, TT...b)
{
	for (int c = 0; *s && (c || *s != ','); ++s) {
		cerr<<*s;
		for (char x : "([{") c += *s == x;
		for (char x : ")]}") c -= *s == x;
	}
	cerr<<" = "<<a;
	if (*s) {
		cerr<<", ";
		_BG(++s,b...);
	} else
		cerr<<endl;
}
#define BG(...) do { \
	cerr << __PRETTY_FUNCTION__ << ':' << __LINE__ << ": "; \
	_BG(#__VA_ARGS__,__VA_ARGS__); \
} while(0)

/* Reading input is now 20% cooler! */
bool RD() {return 1;}
bool RD(char & a) {return scanf(" %c", &a) == 1;}
bool RD(char * a) {return scanf("%s", a) == 1;}
bool RD(double & a) {return scanf("%lf", &a) == 1;}
bool RD(int & a) {return scanf("%d", &a) == 1;}
bool RD(ll & a) {return scanf("%lld", &a) == 1;}

template<class T, class ... TT>
bool RD(T & a, TT & ... b) {return RD(a) && RD(b...);}

/* Do princesses dream of magic sheep? */
#define DR(T,...) T __VA_ARGS__; RD(__VA_ARGS__)
#define RI(...) DR(int,__VA_ARGS__)

/* For it's time for you to fulfill your output. */
void PT(const char & a) {putchar(a);}
void PT(char const * const & a) {fputs(a, stdout);}
void PT(const double & a) {printf("%.16f", a);}
void PT(const int & a) {printf("%d", a);}
void PT(const ll & a) {printf("%lld", a);}

/* The line will last forever! */
template<char s = ' ', char e = '\n'>
void PL() {if (e) PT(e);}
template<char s = ' ', char e = '\n', class T, class ... TT>
void PL(const T & a, const TT & ... b)
{PT(a); if (sizeof...(b) && s) PT(s); PL<s,e>(b...);}

/* Good Luck && Have Fun ! */
#define set vovovoovovovovovooovoo
const int N = 1e5 + 87;
pii a[N],e[N*2];
int po[N];
mt19937 ran(time(0));
struct node
{
	int v,p,s,at;
	bool st;
	node * l,* r;
	node(int k) : v(k), p(ran()), s(1), at(0), st(0), l(0), r(0) {}
};
void set(node * t,int v)
{
	if (t) {
		t->v = v;
		t->st = 1;
		t->at = 0;
	}
}
void add(node * t,int v)
{
	if (t) {
		t->v += v;
		if (!(t->st))
			t->at += v;
	}
}
void push(node * t)
{
	if (t->st) {
		set(t->l, t->v);
		set(t->r, t->v);
		t->st = 0;
		return;
	}
	if (t->at) {
		add(t->l, t->at);
		add(t->r, t->at);
		t->at = 0;
		return;
	}
}
int sz(node * t)
{
	return t ? t->s : 0;
}
void pull(node * t)
{
	t->s = 1 + sz(t->l) + sz(t->r);
}
node * meld(node * a,node * b)
{
	if (!a)
		return b;
	if (!b)
		return a;
	if (a->p > b->p) {
		push(a);
		a->r = meld(a->r, b);
		pull(a);
		return a;
	} else {
		push(b);
		b->l = meld(a, b->l);
		pull(b);
		return b;
	}
}
void split(node * t,int v,node *& a,node *& b)
{
	if (!t) {
		a = b = 0;
		return;
	}
	push(t);
	if (t->v < v) {
		a = t;
		split(t->r, v, a->r, b);
		pull(a);
	} else {
		b = t;
		split(t->l, v, a, b->l);
		pull(b);
	}
}
int qry(node * t,int k)
{
	push(t);
	int i = sz(t->l) + 1;
	return i < k ? qry(t->r, k - i) : 
	       i > k ? qry(t->l, k) :
		   t->v;
}
int main()
{
	RI(x,k);
	RP(i,k) {RD(e[i].F); e[i].F<<=1;}
	RI(n);
	RP(i,n) {
		RD(e[k].F,a[i].F);
		e[k].F = e[k].F<<1|1;
		e[k].S = a[i].S = i;
		++k;
	}
	sort(a,a+n);
	node * rt = 0;
	RP(i,n) {
		po[a[i].S] = i;
		rt = meld(rt, new node(a[i].F));
	}
	sort(e,e+k);
	int up = 0, la = 0;
	RP(i,k) {
		int tn = e[i].F;
		int ty = tn&1;
		tn>>=1;
		int w = tn - la;
		la = tn;
		node * l, * r;
		if (!up) {
			split(rt, w, l, r);
			set(l, 0);
			add(r, -w);
			rt = meld(l, r);
		} else {
			split(rt, x - w, l, r);
			add(l, w);
			set(r, x);
			rt = meld(l, r);
		}
		if (ty) {
			PL(qry(rt, po[e[i].S]+1));
		} else {
			up ^= 1;
		}
	}
}


Measured memory_bytes: 8576