AtCoder Regular Contest 082 - Sandglass

We have a sandglass consisting of two bulbs, bulb A and bulb B. These bulbs contain some amount of sand.
When we put the sandglass, either bulb A or B lies on top of the other and becomes the upper bulb. The other bulb becomes the lower bulb.
The sand drops from the upper bulb to the lower bulb at a rate of 1 gram per second.
When the upper bulb no longer contains any sand, nothing happens.
Initially at time 0, bulb A is the upper bulb and contains a grams of sand; bulb B contains X-a grams of sand (for a total of X grams).
We will turn over the sandglass at time r_1,r_2,..,r_K. Assume that this is an instantaneous action and takes no time. Here, time t refer to the time t seconds after time 0.
You are given Q queries.
Each query is in the form of (t_i,a_i).
For each query, assume that a=a_i and find the amount of sand that would be contained in bulb A at time t_i.

-----Constraints-----
 - 1≤X≤10^9
 - 1≤K≤10^5
 - 1≤r_1<r_2< .. <r_K≤10^9
 - 1≤Q≤10^5
 - 0≤t_1<t_2< .. <t_Q≤10^9
 - 0≤a_i≤X (1≤i≤Q)
 - All input values are integers.

-----Input-----
The input is given from Standard Input in the following format:
X
K
r_1 r_2 .. r_K
Q
t_1 a_1
t_2 a_2
:
t_Q a_Q

-----Output-----
For each query, print the answer in its own line.

-----Sample Input-----
180
3
60 120 180
3
30 90
61 1
180 180

-----Sample Output-----
60
1
120

In the first query, 30 out of the initial 90 grams of sand will drop from bulb A, resulting in 60 grams.
In the second query, the initial 1 gram of sand will drop from bulb A, and nothing will happen for the next 59 seconds. Then, we will turn over the sandglass, and 1 second after this, bulb A contains 1 gram of sand at the time in question.

Difficulty: VERY_HARD

Starter code:

Solutions:
import bisect

def inpl():
	return [int(i) for i in input().split()]
X = int(input())
K = int(input())
r = [0] + inpl()
stu = [()] * (K + 1)
stu[0] = (X, 0, 0)
for (i, v) in enumerate(r[1:], 1):
	(s, t, u) = stu[i - 1]
	if i % 2:
		rs = r[i - 1] - r[i]
		ap = -rs - t
		if ap >= s:
			stu[i] = (0, 0, 0)
		elif ap >= u:
			stu[i] = (s, t + rs, ap)
		else:
			stu[i] = (s, t + rs, u)
	else:
		rs = r[i] - r[i - 1]
		ap = X - rs - t
		if ap >= s:
			stu[i] = (s, t + rs, u)
		elif ap >= u:
			stu[i] = (ap, t + rs, u)
		else:
			stu[i] = (X, 0, X)
Q = int(input())
for _ in range(Q):
	(ti, a) = inpl()
	x = bisect.bisect_right(r, ti)
	ti -= r[x - 1]
	(s, t, u) = stu[x - 1]
	if a >= s:
		R = s + t
	elif a >= u:
		R = a + t
	else:
		R = u + t
	if x % 2:
		print(max(0, R - ti))
	else:
		print(min(X, R + ti))


input = __import__('sys').stdin.readline
MIS = lambda : map(int, input().split())

class Sandgraph:

	def __init__(_, X):
		_.z = _.x1 = 0
		_.x2 = X

	def add(_, dt):
		d1 = min(dt, X - (_.x2 + _.z - _.x1))
		_.z += d1
		dt -= d1
		d1 = min(dt, _.x2 - _.x1)
		_.z += d1
		_.x2 -= d1

	def sub(_, dt):
		d1 = min(dt, _.z)
		_.z -= d1
		dt -= d1
		d1 = min(dt, _.x2 - _.x1)
		_.x1 += d1

	def __call__(_, a):
		if a <= _.x1:
			return _.z
		elif a <= _.x2:
			return a + _.z - _.x1
		else:
			return _.x2 + _.z - _.x1
X = int(input())
k = int(input())
rev = list(MIS())
Q = int(input())
sand = Sandgraph(X)
last_t = 0
i = 0
for QUERY in range(Q):
	(t, a) = MIS()
	while i < k and rev[i] <= t:
		dt = rev[i] - last_t
		if i % 2 == 0:
			sand.sub(dt)
		else:
			sand.add(dt)
		last_t = rev[i]
		i += 1
	dt = t - last_t
	if i % 2 == 0:
		sand.sub(dt)
	else:
		sand.add(dt)
	print(sand(a))
	last_t = t


import sys
read = sys.stdin.read
readline = sys.stdin.readline
(x,) = map(int, readline().split())
(k,) = map(int, readline().split())
(*r,) = map(int, readline().split())
(q,) = map(int, readline().split())
r.append(1 << 30)
INF = 1 << 30
ID_M = (-INF, INF, 0)

def compose(lst1, lst2):
	return (funcval(lst1[0], lst2), funcval(lst1[1], lst2), lst1[2] + lst2[2])

def funcval(x, lst):
	(a, b, c) = lst
	if x <= a - c:
		return a
	elif x >= b - c:
		return b
	else:
		return x + c
seg = (0, x, 0)
tai = []
for i in range(q):
	(t, a) = map(int, readline().split())
	tai.append((t, a, i))
tai.sort(key=lambda x: x[0])
idx = 0
ans = [0] * q
t0 = 0
coeff = -1
for (i, ri) in enumerate(r):
	while idx < q and tai[idx][0] < ri:
		(t, a, j) = tai[idx]
		v = funcval(a, seg)
		ans[j] = min(x, max(v + coeff * (t - t0), 0))
		idx += 1
	seg = compose(seg, (0, x, coeff * (ri - t0)))
	t0 = ri
	coeff *= -1
print(*ans, sep='\n')


def main():
	import sys
	from operator import itemgetter
	input = sys.stdin.readline
	X = int(input())
	K = int(input())
	R = list(map(int, input().split()))
	Q = []
	for r in R:
		Q.append((r, -1))
	q = int(input())
	for _ in range(q):
		(t, a) = list(map(int, input().split()))
		Q.append((t, a))
	Q.sort(key=itemgetter(0))
	prev = 0
	m = 0
	M = X
	flg = -1
	R_cs = 0
	for (t, a) in Q:
		if a < 0:
			r = t - prev
			R_cs -= r * flg
			if flg == -1:
				m = max(0, m - r)
				M = max(0, M - r)
				flg = 1
			else:
				m = min(X, m + r)
				M = min(X, M + r)
				flg = -1
			prev = t
		elif m == M:
			if flg == 1:
				print(min(X, m + t - prev))
			else:
				print(max(0, m - t + prev))
		else:
			am = m + R_cs
			aM = M + R_cs
			if a <= am:
				if flg == 1:
					print(min(X, m + t - prev))
				else:
					print(max(0, m - t + prev))
			elif a >= aM:
				if flg == 1:
					print(min(X, M + t - prev))
				else:
					print(max(0, M - t + prev))
			elif flg == 1:
				print(min(X, m + (a - am) + t - prev))
			else:
				print(max(0, m + (a - am) - t + prev))

def __starting_point():
	main()
__starting_point()


X = int(input())
K = int(input())
R = list(map(int, input().split()))
Q = int(input())
ami = [0] * (K + 1)
ama = [X] + [0] * K
cusummi = [0] * (K + 1)
cusumma = [0] * (K + 1)
cusum = [0] * (K + 1)
pr = 0
for (i, r) in enumerate(R):
	d = pr - r if i % 2 == 0 else r - pr
	cusum[i + 1] = cusum[i] + d
	cusummi[i + 1] = min(cusummi[i], cusum[i + 1])
	cusumma[i + 1] = max(cusumma[i], cusum[i + 1])
	ami[i + 1] = min(max(ami[i] + d, 0), X)
	ama[i + 1] = min(max(ama[i] + d, 0), X)
	pr = r
import bisect
for _ in range(Q):
	(t, a) = list(map(int, input().split()))
	i = bisect.bisect_right(R, t)
	t1 = R[i - 1] if i != 0 else 0
	t2 = t - t1
	d = -t2 if i % 2 == 0 else t2
	if ama[i] == ami[i]:
		print(min(max(ama[i] + d, 0), X))
		continue
	ans = a + cusum[i]
	if -cusummi[i] > a:
		ans += -cusummi[i] - a
	if cusumma[i] > X - a:
		ans -= cusumma[i] - (X - a)
	print(min(max(ans + d, 0), X))


import bisect
oX = int(input())
K = int(input())
r = list(map(int, input().split()))

def calc_time(t):
	val = bisect.bisect_left(t, r)
	diff = t - r[val]
	return (val, diff)
last = (0, oX, 0, 0, oX)
res = [last]
for (i, tr) in enumerate(r):
	(sep1, sep2, X, Y, Z) = last
	dt = tr if i == 0 else tr - r[i - 1]
	if i % 2 == 0:
		X = max(0, X - dt)
		Y = Y - dt
		Z = max(0, Z - dt)
		sep1 = max(sep1, -Y)
	else:
		X = min(oX, X + dt)
		Y = Y + dt
		Z = min(oX, Z + dt)
		sep2 = min(sep2, oX - Y)
	last = (sep1, sep2, X, Y, Z)
	res.append(last)
Q = int(input())
r_index = 0
r.insert(0, 0)
r.append(10000000000)
for i in range(Q):

	def calc(X, r_index, diff):
		tmp = 1 if r_index % 2 else -1
		return min(oX, max(0, X + tmp * diff))
	(t, a) = list(map(int, input().split()))
	while r[r_index] < t:
		if r[r_index + 1] > t:
			break
		r_index += 1
	(sep1, sep2, X, Y, Z) = res[r_index]
	diff = t - r[r_index]
	if a < sep1:
		print(calc(X, r_index, diff))
	elif a > sep2:
		print(calc(Z, r_index, diff))
	else:
		print(calc(a + Y, r_index, diff))


import sys

def read_int_list():
	return list(map(int, input().split()))

def read_int():
	return int(input())

def read_str_list():
	return input().split()

def read_str():
	return input()

def solve():
	X = read_int()
	K = read_int()
	r = read_int_list()
	Q = read_int()
	j = 0
	sign = -1
	s = 0
	e = X
	y = 0
	origin = 0
	out = [0] * Q
	for i in range(Q):
		(t, a) = read_int_list()
		while j < K and r[j] < t:
			d = r[j] - origin
			y += d * sign
			if y < 0:
				s += abs(y)
				if s > e:
					s = e
				y = 0
			if y + e - s > X:
				diff = y + e - s - X
				e -= diff
				if e < s:
					e = s
			if y > X:
				y = X
			origin = r[j]
			j += 1
			sign *= -1
		d = t - origin
		if a <= s:
			res = y
		elif a <= e:
			res = y + a - s
		else:
			res = y + e - s
		res += d * sign
		if res < 0:
			res = 0
		if res > X:
			res = X
		out[i] = res
	return out

def main():
	res = solve()
	print(*res, sep='\n')
main()


X = int(input())
K = int(input())
R = [int(x) for x in reversed(input().split())]
for i in range(0, K - 1):
	R[i] -= R[i + 1]
Q = int(input())
aM = X
M = X
am = 0
m = 0
now = 0
sign = -1
timer = R.pop()

def Go(time):
	global aM, M, am, m
	if sign == 1:
		if m + time > X:
			m = X
			M = X
			aM = am
		elif M + time > X:
			m += time
			M = X
			aM = am + M - m
		else:
			m += time
			M += time
	elif M - time < 0:
		m = 0
		M = 0
		am = aM
	elif m - time < 0:
		m = 0
		M -= time
		am = aM + m - M
	else:
		m -= time
		M -= time
for i in range(Q):
	(t, a) = [int(x) for x in input().split()]
	t -= now
	now += t
	while t >= timer:
		Go(timer)
		t -= timer
		if R:
			timer = R.pop()
		else:
			timer = float('inf')
		sign *= -1
	Go(t)
	timer -= t
	if a < am:
		print(m)
	elif a > aM:
		print(M)
	else:
		print(m + a - am)


X = int(input())
K = int(input())
r = list(map(int, input().split()))
Q = int(input())
p = [tuple(map(int, input().split())) for i in range(Q)]
N = Q
L = 0
R = Q - 1
start = 0
sign = '-'
N0 = 2 ** (N - 1).bit_length()
data = [0] * (2 * N0)
INF = 0

def update(l, r, v):
	L = l + N0
	R = r + N0
	while L < R:
		if R & 1:
			R -= 1
			data[R - 1] += v
		if L & 1:
			data[L - 1] += v
			L += 1
		L >>= 1
		R >>= 1

def query(k):
	k += N0 - 1
	s = INF
	while k >= 0:
		s += data[k]
		k = (k - 1) // 2
	return s
q = []
for i in range(Q):
	(t, a) = p[i]
	p[i] = (a, t, i)
p.sort()
dic = [-1] * Q
for i in range(Q):
	(a, t, id) = p[i]
	update(i, i + 1, a)
	dic[id] = i
	q.append((t, id, 0))
for i in range(K):
	q.append((r[i], -1, r[i] - r[i - 1] * (i > 0)))
q.sort()
ans = [0] * Q
for (val, id, c) in q:
	if id == -1:
		if sign == '-':
			update(L, R + 1, -c)
			while query(L + 1) < 0 and L < R:
				L += 1
			a = query(L)
			if a < 0:
				update(L, L + 1, -a)
			start = val
			sign = '+'
		else:
			update(L, R + 1, c)
			while query(R - 1) > X and L < R:
				R -= 1
			a = query(R)
			if a > X:
				update(R, R + 1, X - a)
			start = val
			sign = '-'
	else:
		(pid, id) = (id, dic[id])
		if sign == '-':
			if id < L:
				res = max(query(L) - (val - start), 0)
			elif id > R:
				res = max(query(R) - (val - start), 0)
			else:
				res = max(query(id) - (val - start), 0)
		elif id < L:
			res = min(query(L) + (val - start), X)
		elif id > R:
			res = min(query(R) + (val - start), X)
		else:
			res = min(query(id) + (val - start), X)
		ans[pid] = res
for i in range(Q):
	print(ans[i])


import bisect

def main():
	X = int(input())
	K = int(input())
	r = list(map(int, input().split()))
	Q = int(input())
	q_list = []
	for i in range(Q):
		q_list.append(list(map(int, input().split())))
	r = [0] + r
	a = [0]
	upper_limit = [X]
	lower_limit = [0]
	(x, ux, lx) = (0, X, 0)
	for i in range(1, K + 1):
		diff = r[i] - r[i - 1]
		if i % 2 == 1:
			x -= diff
			ux -= diff
			ux = max(ux, 0)
			lx -= diff
			lx = max(lx, 0)
		else:
			x += diff
			ux += diff
			ux = min(ux, X)
			lx += diff
			lx = min(lx, X)
		a.append(x)
		upper_limit.append(ux)
		lower_limit.append(lx)
	asc_i = [0]
	dsc_i = [1]
	x = 0
	for i in range(2, K + 1, 2):
		if x < a[i]:
			x = a[i]
			asc_i.append(i)
	x = a[1]
	for i in range(3, K + 1, 2):
		if a[i] < x:
			x = a[i]
			dsc_i.append(i)
	asc_a = [a[i] for i in asc_i]
	dsc_a = [-a[i] for i in dsc_i]
	for [t, a0] in q_list:
		ri = bisect.bisect_right(r, t) - 1
		ui = bisect.bisect_left(asc_a, X - a0)
		li = bisect.bisect_left(dsc_a, a0)
		(ai, di) = (None, None)
		if ui < len(asc_i):
			ai = asc_i[ui]
			if ri < ai:
				ai = None
		if li < len(dsc_i):
			di = dsc_i[li]
			if ri < di:
				di = None
		d = 0
		if not ai is None or not di is None:
			if ai is None:
				d = -1
			elif di is None:
				d = 1
			else:
				d = 1 if ai < di else -1
		x = a0 + a[ri]
		if d == 1:
			x = upper_limit[ri]
		elif d == -1:
			x = lower_limit[ri]
		x += (t - r[ri]) * (-1 if ri % 2 == 0 else 1)
		x = min(max(x, 0), X)
		print(x)
main()


from collections import deque
X = int(input())
K = int(input())
r = list(map(int, input().split()))
r.append(float('inf'))
r.append(0)
ta = deque([])
Q = int(input())
for i in range(Q):
	(t, a) = map(int, input().split())
	ta.append([t, a])
ZA = 0
XA = X
D = 0
Zmax = 0
Xmin = X
for i in range(K + 1):
	time = r[i] - r[i - 1]
	if i % 2 == 0:
		while len(ta) > 0 and ta[0][0] <= r[i]:
			(t, a) = ta.popleft()
			td = t - r[i - 1]
			if a <= Zmax:
				print(max(0, ZA - td))
			elif a >= Xmin:
				print(max(0, XA - td))
			else:
				print(max(0, a + D - td))
		D -= time
		Zmax = max(Zmax, -1 * D)
		ZA = max(0, ZA - time)
		XA = max(0, XA - time)
	else:
		while len(ta) > 0 and ta[0][0] <= r[i]:
			(t, a) = ta.popleft()
			td = t - r[i - 1]
			if a <= Zmax:
				print(min(X, ZA + td))
			elif a >= Xmin:
				print(min(X, XA + td))
			else:
				print(min(X, a + D + td))
		D += time
		Xmin = min(Xmin, X - D)
		ZA = min(X, ZA + time)
		XA = min(X, XA + time)


from bisect import bisect
X = int(input())
K = int(input())
r_list = [0] + list(map(int, input().split()))
Q = int(input())
query_list = [list(map(int, input().split())) for _ in range(Q)]
MmRL_list = []
M = X
m = 0
R = X
L = 0
MmRL_list.append([M, m, R, L])
for i in range(K):
	M_ = M
	m_ = m
	R_ = R
	L_ = L
	lag = r_list[i + 1] - r_list[i]
	if i % 2 == 0:
		if M_ - lag < 0:
			M = 0
			R = 0
		else:
			M = M_ - lag
			R = R_
		if m_ - lag < 0:
			m = 0
			L = L_ + lag - m_
		else:
			m = m_ - lag
			L = L_
	else:
		if M_ + lag > X:
			M = X
			R = R_ - (M_ + lag - X)
		else:
			M = M_ + lag
			R = R_
		if m_ + lag > X:
			m = X
			L = X
		else:
			m = m_ + lag
			L = L_
	MmRL_list.append([M, m, R, L])
for q in range(Q):
	(t, a) = query_list[q]
	j = bisect(r_list, t) - 1
	(M, m, R, L) = MmRL_list[j]
	if a <= L:
		a_ = m
	elif a >= R:
		a_ = M
	else:
		a_ = m + (a - L)
	t_ = t - r_list[j]
	if j % 2 == 0:
		res = max(a_ - t_, 0)
	else:
		res = min(a_ + t_, X)
	print(res)


X = int(input())
K = int(input())
r_lst = [int(_) for _ in input().split()]
Q = int(input())
(t_lst, a_lst) = ([], [])
for i in range(Q):
	buf = input().split()
	t_lst.append(int(buf[0]))
	a_lst.append(int(buf[1]))
pos_lst = []
for (i, r) in enumerate(r_lst):
	direc = '+' if i % 2 == 0 else '-'
	pos_lst.append((r, direc))
for (i, t) in enumerate(t_lst):
	pos_lst.append((t, i))
pos_lst = sorted(pos_lst, key=lambda tup: tup[0])
(left, right) = (0, X)
val = [0, 0, X]
direc = '-'
prv = 0
for pos in pos_lst:
	elapsed = pos[0] - prv
	prv = pos[0]
	if direc == '+':
		val[0] = min(X, val[0] + elapsed)
		val[1] += elapsed
		val[2] = min(X, val[2] + elapsed)
		right = min(right, X - val[1])
	else:
		val[0] = max(0, val[0] - elapsed)
		val[1] -= elapsed
		val[2] = max(0, val[2] - elapsed)
		left = max(left, -val[1])
	if pos[1] == '+' or pos[1] == '-':
		direc = pos[1]
	else:
		a = a_lst[pos[1]]
		if a <= left:
			print(val[0])
		elif a >= right:
			print(val[2])
		else:
			print(a + val[1])


X = int(input())
K = int(input())
R = list(map(int, input().split()))
R.append(0)
A = [X for _ in range(K + 1)]
B = [0 for _ in range(K + 1)]
C = [X for _ in range(K + 1)]
D = [0 for _ in range(K + 1)]
state = -1
for i in range(K):
	dr = R[i] - R[i - 1]
	if state == -1:
		C[i + 1] = max(0, C[i] - dr)
		D[i + 1] = max(0, D[i] - dr)
		B[i + 1] = min(B[i] + -min(0, D[i] - dr), A[i])
		A[i + 1] = A[i]
	else:
		C[i + 1] = min(X, C[i] + dr)
		D[i + 1] = min(X, D[i] + dr)
		A[i + 1] = max(A[i] - max(0, C[i] + dr - X), B[i])
		B[i + 1] = B[i]
	state *= -1
Q = int(input())
R.pop()
import bisect
for _ in range(Q):
	(t, a) = list(map(int, input().split()))
	j = bisect.bisect_right(R, t)
	if j == 0:
		r = 0
	else:
		r = R[j - 1]
	pre_ans = min(A[j], max(B[j], a)) - B[j] + D[j]
	pre_ans += (-1) ** (1 - j % 2) * (t - r)
	print(min(X, max(0, pre_ans)))


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
gosa = 1.0 / 10 ** 10
mod = 10 ** 9 + 7

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def main():
	x = I()
	k = I()
	r = LI()
	q = I()
	t = [LI() for _ in range(q)]
	a = [[0, 0, 0, x, 0, 0]]
	d = 0
	for i in range(k):
		c = a[-1][:]
		rr = r[i] - d
		d = r[i]
		if i % 2 == 0:
			c[1] -= rr
			c[3] -= rr
			c[4] -= rr
			if c[0] > c[1]:
				c[0] = c[1]
		else:
			c[1] += rr
			c[3] += rr
			c[4] += rr
			if c[2] < c[1]:
				c[2] = c[1]
		if c[3] > x:
			c[3] = x
		if c[3] < 0:
			c[3] = 0
		if c[4] > x:
			c[4] = x
		if c[4] < 0:
			c[4] = 0
		c[5] = r[i]
		a.append(c)

	def bs(i):
		ma = k
		mi = 0
		mm = 0
		while ma > mi and (ma + mi) // 2 != mm:
			mm = (ma + mi) // 2
			if a[mm][5] < i:
				mi = mm
			else:
				ma = mm - 1
		if a[mm][5] > i:
			return mm - 1
		if mm == k:
			return k
		if a[mm + 1][5] <= i:
			return mm + 1
		return mm
	rr = []
	for (c, d) in t:
		ti = bs(c)
		ai = a[ti]
		e = x - d
		if d + ai[0] <= 0:
			tt = ai[4]
		elif e - ai[2] <= 0:
			tt = ai[3]
		else:
			tt = d + ai[1]
		if ti % 2 == 0:
			tt -= c - ai[5]
		else:
			tt += c - ai[5]
		if tt < 0:
			tt = 0
		elif tt > x:
			tt = x
		rr.append(tt)
	return '\n'.join(map(str, rr))
print(main())


import sys
input = sys.stdin.readline
X = int(input())
K = int(input())
R = [int(x) for x in input().split()]
Q = int(input())
TA = [tuple((int(x) for x in input().split())) for _ in range(Q)]
task = sorted([(r, -1) for r in R] + [(t, a) for (t, a) in TA])
L = 0
R = X
A = 0
B = X
dx = -1
current = 0
answer = []
for (t, a) in task:
	A += dx * (t - current)
	B += dx * (t - current)
	current = t
	if a != -1:
		if a <= L:
			x = A
		elif a >= R:
			x = B
		else:
			x = A + (B - A) // (R - L) * (a - L)
		if x < 0:
			x = 0
		if x > X:
			x = X
		answer.append(x)
	else:
		dx = -dx
		if A < B:
			if A < 0:
				L += -A
				A = 0
			if B > X:
				R -= B - X
				B = X
			if A > X:
				A = X
				B = X
				L = 0
				R = 0
			if B < 0:
				A = 0
				B = 0
				L = 0
				R = 0
		elif A >= B:
			if A > X:
				L += A - X
				A = X
			if B < 0:
				R -= -B
				B = 0
			if A < 0:
				A = 0
				B = 0
				L = 0
				R = 0
			if B > X:
				A = X
				B = X
				L = 0
				R = 0
		if R < L:
			R = L
print(*answer, sep='\n')


x = int(input())
k = int(input())
(*R,) = map(int, input().split() + [1 << 30])
Q = int(input())
ta = [tuple(map(int, input().split())) for _ in range(Q)]

def f(x, l):
	return max(l[0], min(l[1], x + l[2]))
L = (a, b, c) = (0, x, 0)
idx = t0 = 0
g = -1
for r in R:
	while idx < Q and ta[idx][0] < r:
		print(f(f(ta[idx][1], L) + g * (ta[idx][0] - t0), (0, x, 0)))
		idx += 1
	(d, t0) = (g * (r - t0), r)
	L = (a, b, c) = (f(a, (0, x, d)), f(b, (0, x, d)), c + d)
	g *= -1


X = int(input())
K = int(input())
rs = list(map(int, input().split()))
Q = int(input())
qs = [tuple(map(int, input().split())) for i in range(Q)]
dx = -1
ri = 0
offset = 0
(upper, lower) = (X, 0)
prev_r = 0
ans = []
for (t, a) in qs:
	while ri < len(rs) and rs[ri] <= t:
		tmp_offset = dx * (rs[ri] - prev_r)
		if dx == 1:
			upper = min(X, upper + tmp_offset)
			lower = min(X, lower + tmp_offset)
		else:
			upper = max(0, upper + tmp_offset)
			lower = max(0, lower + tmp_offset)
		offset += tmp_offset
		dx *= -1
		prev_r = rs[ri]
		ri += 1
	a = max(lower, min(upper, a + offset))
	dt = t - prev_r
	a = max(0, min(X, a + dx * dt))
	ans.append(a)
print(*ans, sep='\n')


def calc_ans(x):
	if x < 0:
		return 0
	elif x < X:
		return x
	else:
		return X
X = int(input())
K = int(input())
r = list(map(int, input().split()))
Q = int(input())
j = 0
sign = -1
s = 0
e = X
y = 0
sand_quantity = [r[0]]
for i in range(1, K):
	sand_quantity.append(r[i] - r[i - 1])
chasm_time = 0
for i in range(Q):
	(t, a) = list(map(int, input().split()))
	while j < K and r[j] < t:
		y += sign * sand_quantity[j]
		if y < 0:
			s += -y
			if e < s:
				s = e
			y = 0
		if X < y + e - s:
			tmp_diff = y + e - s - X
			e -= tmp_diff
			if e < s:
				e = s
		if X < y:
			y = X
		chasm_time = r[j]
		j += 1
		sign *= -1
	tmp_time = t - chasm_time
	if a < s:
		ret = y
	elif a < e:
		ret = y + a - s
	else:
		ret = y + e - s
	ret += tmp_time * sign
	print(calc_ans(ret))


def main1(x, k, rary, q, ta):
	aary = []
	tary = []
	for (i, (t, a)) in enumerate(ta):
		aary.append([a, i])
		tary.append([t, i])
	tary.sort(key=lambda x: x[0])
	aary.sort(key=lambda x: x[0])
	(l, r) = (0, x)
	(lt, rt) = (-1, -1)
	tidx = 0
	nowt = 0
	nowu = 'A'
	da = 0
	ret = [-1] * q
	daary = {}
	rary.append(10 ** 9 + 1)
	k += 1
	for (i, ri) in enumerate(rary):
		while tidx < q and tary[tidx][0] <= ri:
			(t, j) = tary[tidx]
			tidx += 1
			a = ta[j][1]
			if nowu == 'A':
				if l <= a <= r:
					ret[j] = a + da - (t - nowt)
				elif a < l:
					ret[j] = da - daary[lt] - (t - nowt)
				else:
					ret[j] = x + da - daary[rt] - (t - nowt)
			elif l <= a <= r:
				ret[j] = a + da + (t - nowt)
			elif a < l:
				ret[j] = da - daary[lt] + (t - nowt)
			else:
				ret[j] = x + da - daary[rt] + (t - nowt)
			ret[j] = max(0, ret[j])
			ret[j] = min(x, ret[j])
		if nowu == 'A':
			dt = ri - nowt
			da -= dt
			if l < -da:
				l = -da
				lt = ri
			nowt = ri
			nowu = 'B'
		else:
			dt = ri - nowt
			da += dt
			if r > x - da:
				r = x - da
				rt = ri
			nowt = ri
			nowu = 'A'
		daary[nowt] = da
		if l >= r:
			if nowu == 'B':
				da = 0
			else:
				da = x
			for ii in range(i + 1, k):
				ri = rary[ii]
				while tidx < q and tary[tidx][0] <= ri:
					(t, j) = tary[tidx]
					tidx += 1
					if nowu == 'A':
						ret[j] = da - (t - nowt)
					else:
						ret[j] = da + (t - nowt)
					ret[j] = max(0, ret[j])
					ret[j] = min(x, ret[j])
				if nowu == 'A':
					da -= ri - nowt
					da = max(da, 0)
					nowu = 'B'
				else:
					da += ri - nowt
					da = min(da, x)
					nowu = 'A'
				nowt = ri
			break
	return ret
import sys
input = sys.stdin.readline

def __starting_point():
	x = int(input())
	k = int(input())
	r = list(map(int, input().split()))
	q = int(input())
	ta = [list(map(int, input().split())) for _ in range(q)]
	print(*main1(x, k, r, q, ta), sep='\n')
__starting_point()


import sys
from bisect import bisect

def input():
	return sys.stdin.readline()[:-1]
x = int(input())
k = int(input())
z = [0] + list(map(int, input().split()))
s = [z[i + 1] - z[i] for i in range(k)]
lr = [[0, x]]
pq = [[0, x]]
for i in range(k):
	(l, r) = lr[-1]
	(p, q) = pq[-1]
	if i % 2 == 0:
		lr.append([max(l - s[i], 0), max(r - s[i], 0)])
		pq.append([min(p + max(min(s[i], x) - l, 0), q), q])
	else:
		lr.append([min(l + s[i], x), min(r + s[i], x)])
		pq.append([p, max(q - max(r - max(x - s[i], 0), 0), p)])
q = int(input())
for _ in range(q):
	(t, a) = map(int, input().split())
	i = bisect(z, t) - 1
	t -= z[i]
	if a <= pq[i][0]:
		y = lr[i][0]
	elif a >= pq[i][1]:
		y = lr[i][1]
	else:
		y = lr[i][0] + a - pq[i][0]
	if i % 2 == 0:
		print(max(y - t, 0))
	else:
		print(min(y + t, x))


import sys
input = sys.stdin.readline
x = int(input())
k = int(input())
R = [(_r, i % 2) for (i, _r) in enumerate(map(int, input().split()))]
n = int(input())
TA = [list(map(int, input().split())) for _ in range(n)]
(T, A) = zip(*TA)
L = [None] * n
b = 0
for (i, t) in enumerate(T, 1):
	R.append((t, -i))
R.sort()
dx = 1
(l, r, p, q) = (0, x, 0, x)
for (_r, i) in R:
	d = _r - b
	b = _r
	if dx == 1:
		if d <= p:
			p -= d
			q -= d
		elif d < q:
			q -= d
			l = r - q
			p = 0
		else:
			l = 0
			r = 0
			p = 0
			q = 0
	elif d <= x - q:
		p += d
		q += d
	elif d < x - p:
		p += d
		r = l + (x - p)
		q = x
	else:
		l = x
		r = x
		p = x
		q = x
	if i >= 0:
		dx = i
	else:
		a = A[-i - 1]
		if a < l:
			res = p
		elif a <= r:
			res = a - l + p
		else:
			res = q
		L[-i - 1] = res
print(*L, sep='\n')


import sys
from heapq import *
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def main():
	x = int(input())
	k = int(input())
	rr = LI()
	q = int(input())
	ta = LLI(q)
	timeline = []
	for r in rr:
		heappush(timeline, [r, 0, 0])
	for (t, a) in ta:
		heappush(timeline, [t, 1, a])
	sl = sm = 0
	sr = x
	al = 0
	ar = x
	rev_t = 0
	trend = False
	while timeline:
		(t, op, a) = heappop(timeline)
		sd = t - rev_t
		if op:
			if trend:
				if a < al:
					print(min(sl + sd, x))
				elif a > ar:
					print(min(sr + sd, x))
				else:
					print(min(a + sm + sd, x))
			elif a < al:
				print(max(sl - sd, 0))
			elif a > ar:
				print(max(sr - sd, 0))
			else:
				print(max(a + sm - sd, 0))
		else:
			if trend:
				sl = min(sl + sd, x)
				sr = min(sr + sd, x)
				ar = min(ar, x - sm - sd - 1)
				sm += sd
			else:
				sl = max(sl - sd, 0)
				sr = max(sr - sd, 0)
				al = max(al, sd - sm + 1)
				sm -= sd
			trend = not trend
			rev_t = t
main()


from bisect import bisect
X = int(input())
K = int(input())
rs = [0]
for r in input().split():
	rs.append(int(r))
A = [[(0, 0), (X, X)]]
min_sup = 0
max_inf = X
pre_r = 0
for (i, r) in enumerate(rs[1:]):
	d = r - pre_r
	pre_r = r
	(m, M) = (A[-1][0][0], A[-1][1][0])
	if i % 2 == 0:
		if m - d >= 0:
			new_m = m - d
		else:
			new_m = 0
			min_sup = min_sup + d - m
		if M - d > 0:
			new_M = M - d
		else:
			new_M = 0
			max_inf = 0
	else:
		if M + d <= X:
			new_M = M + d
		else:
			new_M = X
			max_inf = max_inf - (d - (X - M))
		if m + d < X:
			new_m = m + d
		else:
			new_m = X
			min_sup = X
	if new_m == new_M:
		min_sup = X
		max_inf = 0
	A.append([(new_m, min_sup), (new_M, max_inf)])
Q = int(input())
for q in range(Q):
	(t, a) = list(map(int, input().split()))
	r_num = bisect(rs, t) - 1
	(m, min_sup) = A[r_num][0]
	(M, max_inf) = A[r_num][1]
	r = rs[r_num]
	if r_num % 2 == 0:
		if a <= min_sup:
			print(max(m - (t - r), 0))
		elif min_sup < a < max_inf:
			print(max(m + (a - min_sup) - (t - r), 0))
		else:
			print(max(M - (t - r), 0))
	elif a <= min_sup:
		print(min(m + (t - r), X))
	elif min_sup < a < max_inf:
		print(min(m + (a - min_sup) + (t - r), X))
	else:
		print(min(M + (t - r), X))