Read problems statements [Bengali] , [Mandarin chinese] , [Russian] and [Vietnamese] as well.

Chef is a cook and he has recently opened a restaurant.

The restaurant is open during $N$ time intervals $[L_{1}, R_{1}), [L_{2}, R_{2}), \dots, [L_{N}, R_{N})$. No two of these intervals overlap — formally, for each valid $i$, $j$ such that $i \neq j$, either $R_{i} < L_{j}$ or $R_{j} < L_{i}$.

$M$ people (numbered $1$ through $M$) are planning to eat at the restaurant; let's denote the time when the $i$-th person arrives by $P_{i}$. If the restaurant is open at that time, this person does not have to wait, but if it is closed, this person will wait until it is open. Note that if this person arrives at an exact time when the restaurant is closing, they have to wait for the next opening time.

For each person, calculate how long they have to wait (possibly $0$ time), or determine that they will wait forever for the restaurant to open.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of the input contains two space-separated integers $N$ and $M$.
$N$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $L_{i}$ and $R_{i}$.
$M$ lines follow. For each valid $i$, the $i$-th of these lines contains a single integer $P_{i}$.

------  Output ------
For each test case, print $M$ lines. For each valid $i$, the $i$-th of these lines should contain a single integer — the time person $i$ has to wait, or $-1$ if person $i$ has to wait forever.

------  Constraints  ------
$1 ≤ T ≤ 100$
$1 ≤ N, M ≤ 10^{5}$
$1 ≤ L_{i} < R_{i} ≤ 10^{9}$ for each valid $i$
$1 ≤ P_{i} ≤ 10^{9}$ for each valid $i$
the intervals are pairwise disjoint
the sum of $N$ for all test cases does not exceed $3 \cdot 10^{5}$
the sum of $M$ for all test cases does not exceed $3 \cdot 10^{5}$

------  Subtasks ------
Subtask #1 (30 points):
the sum of $N$ for all test cases does not exceed $1,000$
the sum of $M$ for all test cases does not exceed $1,000$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
1
4 5
5 7
9 10
2 3
20 30
5
6
7
35
1
----- Sample Output 1 ------ 
0
0
2
-1
1
----- explanation 1 ------ 
Query $1$: The person coming at time $5$ does not have to wait as the restaurant is open in $[5,7)$ slot.

Query $2$: The person coming at time $6$ does not have to wait as the restaurant is open in $[5,7)$ slot.

Query $3$: The person coming at time $7$ has to wait since the restaurant is closed at time $7$. The next slot in which the restaurant opens is $[9,10)$. Thus, the person waits for $2$ units of time.

Query $4$: The person coming at time $35$ has to wait forever as the restaurant does not open after time $30$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Sorting

Complete search


Solutions:
import sys
import bisect
from os import path
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	r = []
	for __ in range(n):
		(x, y) = map(int, input().split())
		l.append(x)
		r.append(y)
	p = []
	for ___ in range(m):
		p.append(int(input()))
	l.sort()
	r.sort()
	for i in range(m):
		if l[0] <= p[i]:
			idx = bisect.bisect_right(l, p[i])
			try:
				if p[i] - l[idx - 1] < r[idx - 1] - l[idx - 1]:
					print(0)
				else:
					print(l[idx] - p[i])
			except:
				print(-1)
		else:
			print(l[0] - p[i])


def check(l, val):
	if l[0][0] > val:
		print(l[0][0] - val)
		return
	elif l[-1][1] <= val:
		print(-1)
		return
	else:
		start = 0
		end = len(l) - 1
		while start <= end:
			mid = (start + end) // 2
			if l[mid][0] <= val and l[mid][1] > val:
				print(0)
				return
			elif l[mid][1] <= val and l[mid + 1][0] > val:
				print(l[mid + 1][0] - val)
				return
			elif l[mid][0] > val and l[mid - 1][1] <= val:
				print(l[mid][0] - val)
				return
			elif l[mid][0] < val:
				start = mid + 1
			else:
				end = mid - 1
for _ in range(int(input())):
	l = []
	(n, m) = map(int, input().split())
	for i in range(n):
		temp = list(map(int, input().split()))
		l.append(temp)
	l.sort()
	time = [int(input()) for i in range(m)]
	for i in time:
		check(l, i)


def binary(a, q, n):
	i = 0
	j = n - 1
	ans = -1
	while i <= j:
		mid = (i + j) // 2
		if q >= a[mid][1]:
			i = mid + 1
		else:
			ans = mid
			j = mid - 1
	return ans

def total_wait(a, n, t):
	a.sort(key=lambda a: a[0])
	while t:
		t -= 1
		q = int(input())
		pos = binary(a, q, n)
		if pos == -1 or q > a[pos][1]:
			print(-1)
		elif a[pos][0] <= q < a[pos][1]:
			print('0')
		else:
			print(a[pos][0] - q)
t = int(input())
while t:
	t -= 1
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		l = []
		(i, j) = map(int, input().split())
		l.append(i)
		l.append(j)
		a.append(l)
	total_wait(a, n, m)


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	lr = []
	for _ in range(n):
		(a, b) = list(map(int, input().split()))
		lr.append([a, b])
	p = []
	for _ in range(m):
		p.append(int(input()))
	lr.sort(key=lambda x: x[0])
	for myTime in p:
		start = 0
		end = n - 1
		while start <= end:
			if start == end:
				if myTime >= lr[start][1]:
					print(-1)
					break
				elif myTime >= lr[start][0]:
					print(0)
					break
				else:
					print(lr[start][0] - myTime)
					break
			mid = (start + end) // 2
			if myTime >= lr[mid][1]:
				start = mid + 1
			elif myTime < lr[mid][0]:
				end = mid
			else:
				print(0)
				break


t = int(input())

def lowerbound(intervals, ass):
	s = 0
	e = len(intervals) - 1
	lower_bound = -1
	while s <= e:
		mid = (s + e) // 2
		if intervals[mid][0] <= ass:
			s = mid + 1
		else:
			lower_bound = mid
			e = mid - 1
	return lower_bound if lower_bound != -1 else len(intervals)
for tc in range(t):
	pers = []
	intervals = []
	(n, m) = map(int, input().split(' '))
	for j in range(n):
		(l, r) = map(int, input().split(' '))
		intervals.append([l, r])
	intervals.sort()
	for j in range(m):
		pers = int(input())
		pos = lowerbound(intervals, pers)
		if pos == 0:
			ans = intervals[0][0] - pers
			print(ans)
		else:
			ans = -1
			if intervals[pos - 1][1] > pers:
				ans = 0
			elif pos < len(intervals):
				ans = intervals[pos][0] - pers
			print(ans)


import bisect
t = int(input())
for _ in range(t):
	(n, m) = [int(i) for i in input().split()]
	arr = []
	dic = {}
	for i in range(n):
		(l, r) = [int(i) for i in input().split()]
		arr.append(l)
		dic[l] = r
	arr.sort()
	for i in range(m):
		val = int(input())
		ind = bisect.bisect_right(arr, val)
		if arr[ind - 1] == val:
			print(0)
		elif val < dic[arr[ind - 1]] and val > arr[ind - 1]:
			print(0)
		elif ind == n and val >= dic[arr[ind - 1]]:
			print(-1)
		elif ind == 0:
			print(arr[0] - val)
		elif ind == n:
			print(0)
		else:
			print(arr[ind] - val)


from bisect import insort, bisect_right
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	intervals = []
	for i in range(n):
		inp = tuple(map(int, input().split()))
		insort(intervals, inp)
	inte = [k[1] for k in intervals]
	for i in range(m):
		ip = int(input())
		c = bisect_right(inte, ip)
		if c >= n:
			print(-1)
		else:
			curr = intervals[c]
			if ip >= curr[0] and ip < curr[1]:
				print(0)
			else:
				print(curr[0] - ip)


def binsearch(x):
	l = 0
	r = len(times)
	while l < r:
		i = (l + r) // 2
		ele = times[i]
		if x >= ele[1]:
			l = i + 1
		elif x < ele[0]:
			r = i
		elif x in range(ele[0], ele[1]):
			return 0
	if ele[0] - x > 0:
		return ele[0] - x
	elif ele[0] - x < 0 and i + 1 < len(times):
		return times[i + 1][0] - x
	elif i + 1 == len(times):
		return -1
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	times = []
	for _ in range(n):
		times.append(list(map(int, input().split())))
	times.sort()
	for _ in range(m):
		inp = int(input())
		print(binsearch(inp))


from sys import stdin, stdout
import bisect

def main():
	for _ in range(int(stdin.readline())):
		(n, m) = map(int, stdin.readline().split())
		arr = []
		dic = {}
		for i in range(n):
			(l, r) = map(int, stdin.readline().split())
			arr.append(l)
			dic[l] = r
		arr.sort()
		for i in range(m):
			val = int(stdin.readline())
			ind = bisect.bisect_right(arr, val)
			if arr[ind - 1] == val:
				print(0)
			elif val < dic[arr[ind - 1]] and val > arr[ind - 1]:
				print(0)
			elif ind == n and val >= dic[arr[ind - 1]]:
				print(-1)
			elif ind == 0:
				print(arr[0] - val)
			elif ind == n:
				print(0)
			else:
				print(arr[ind] - val)
main()


def searchP(p, arr, n):
	(low, high) = (0, n - 1)
	ans = -1
	while low <= high:
		mid = low + (high - low) // 2
		if arr[mid][1] > p:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	if ans == -1:
		return -1
	return max(0, arr[ans][0] - p)
t = int(input())
for tc in range(t):
	(n, m) = map(int, input().split())
	arr = [[int(j) for j in input().split()] for i in range(n)]
	arr.sort()
	for i in range(m):
		wt = 0
		p = int(input())
		wt = searchP(p, arr, n)
		print(wt)


t = int(input())
for k in range(t):
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	inv = []
	for i in range(n):
		(l, r) = input().split()
		inv.append([int(l), int(r)])

	def f(x):
		return x[0]
	inv = sorted(inv, key=f)
	for i in range(m):
		q = int(input())
		if q >= inv[n - 1][1]:
			print(-1)
			continue
		time = -1
		l = 0
		r = n - 1
		while l <= r:
			mid = l + (r - l) // 2
			if q < inv[mid][0]:
				time = inv[mid][0] - q
				r = mid - 1
			elif q >= inv[mid][1]:
				l = mid + 1
			else:
				time = 0
				break
		print(time)


try:
	from bisect import bisect
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		a = []
		for i in range(n):
			(l, r) = map(int, input().split())
			a.append([l, r])
		a.sort()
		for j in range(m):
			p = int(input())
			b = bisect(a, [p])
			(start, end) = a[b - 1]
			if start <= p < end:
				print(0)
			elif len(a) <= b:
				print(-1)
			else:
				print(a[b][0] - p)
except:
	pass


from sys import stdin

def binary_search(interval, x):
	(start, end) = (0, len(interval) - 1)
	while start <= end:
		mid = (start + end) // 2
		if interval[mid][0] <= x < interval[mid][1]:
			return mid
		elif interval[mid][0] > x:
			end = mid - 1
		elif interval[mid][0] < x:
			start = mid + 1
	return [start, end]
t = int(stdin.readline())
while t > 0:
	(n, m) = map(int, stdin.readline().split())
	interval = []
	for i in range(n):
		(l, r) = map(int, stdin.readline().split())
		interval.append([l, r])
	p = []
	for i in range(m):
		p.append(int(stdin.readline()))
	interval = sorted(interval, key=lambda x: x[0])
	for x in p:
		wait_time = binary_search(interval, x)
		if isinstance(wait_time, list):
			(l, r) = wait_time
			wait_time = -1 if l >= n else interval[l][0] - x
		else:
			wait_time = 0
		print(wait_time)
	t -= 1


from bisect import bisect
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = []
	for _ in range(n):
		(l, r) = map(int, input().split())
		a.append([l, r])
	a.sort()
	for _ in range(m):
		p = int(input())
		i = bisect(a, [p])
		(start, end) = a[i - 1]
		if start <= p < end:
			print(0)
		elif len(a) <= i:
			print(-1)
		else:
			print(a[i][0] - p)


def merge(arr, start, mid, end):
	i = start
	j = mid
	k = 0
	temp = [0] * (end - start + 1)
	while i < mid and j <= end:
		if arr[i][0] <= arr[j][0]:
			temp[k] = arr[i]
			i += 1
			k += 1
		else:
			temp[k] = arr[j]
			j += 1
			k += 1
	while i < mid:
		temp[k] = arr[i]
		i += 1
		k += 1
	while j <= end:
		temp[k] = arr[j]
		j += 1
		k += 1
	k = 0
	for i in range(start, end + 1):
		arr[i] = temp[k]
		k += 1

def merge_sort(arr, first, last):
	if first >= last:
		return
	mid = first + (last - first) // 2
	merge_sort(arr, first, mid)
	merge_sort(arr, mid + 1, last)
	merge(arr, first, mid + 1, last)

def binarySearch(arr, target, end):
	start = 0
	ans = end + 1
	while start <= end:
		mid = start + (end - start) // 2
		if arr[mid][0] < target:
			start = mid + 1
		else:
			ans = mid
			end = mid - 1
	return ans
tests = int(input().strip())
for t in range(tests):
	(n, m) = [int(x) for x in input().strip().split()]
	intervals = [0] * n
	for i in range(n):
		(x, y) = input().strip().split()
		intervals[i] = (int(x), int(y))
	merge_sort(intervals, 0, n - 1)
	persons = [0] * m
	for i in range(m):
		persons[i] = int(input().strip())
	for p in persons:
		index = binarySearch(intervals, p, n - 1)
		ans = -1
		if index == 0:
			ans = intervals[index][0] - p
		elif intervals[index - 1][1] > p:
			ans = 0
		elif index < n:
			ans = intervals[index][0] - p
		print(ans)


def binarySearch(arr, target, end):
	start = 0
	ans = end + 1
	while start <= end:
		mid = start + (end - start) // 2
		if arr[mid][0] < target:
			start = mid + 1
		else:
			ans = mid
			end = mid - 1
	return ans
tests = int(input().strip())
for t in range(tests):
	(n, m) = [int(x) for x in input().strip().split()]
	intervals = [0] * n
	for i in range(n):
		(x, y) = input().strip().split()
		intervals[i] = (int(x), int(y))
	intervals.sort(key=lambda x: x[0])
	persons = [0] * m
	for i in range(m):
		persons[i] = int(input().strip())
	for p in persons:
		index = binarySearch(intervals, p, n - 1)
		ans = -1
		if index == 0:
			ans = intervals[index][0] - p
		elif intervals[index - 1][1] > p:
			ans = 0
		elif index < n:
			ans = intervals[index][0] - p
		print(ans)


class point:

	def __init__(self, a, b):
		self.st = a
		self.en = b

def f(p):
	return p.st
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	points = []
	for i in range(n):
		(a, b) = map(int, input().split())
		temp = point(a, b)
		points.append(temp)
	points.sort(key=f)
	for __ in range(m):
		x = int(input())
		ans = -1
		s = 0
		e = n - 1
		check = -1
		while s <= e:
			mid = (s + e) // 2
			ele = points[mid]
			if ele.st <= x and ele.en > x:
				ans = 0
				check = mid
				break
			elif ele.en > x:
				e = mid - 1
			else:
				s = mid + 1
			if ele.st >= x:
				check = mid
		if ans != 0 and check != -1:
			ans = points[check].st - x
		print(ans)


from sys import stdin, stdout
input = stdin.readline

def binarySearch(arr, p):
	n = len(arr)
	low = 0
	high = n - 1
	ans = -1
	while high >= low:
		mid = (low + high) // 2
		(l, r) = arr[mid]
		if p >= l and p < r:
			return 0
		elif p < l:
			high = mid - 1
			ans = l - p
		elif p >= r:
			low = mid + 1
	return ans
t = int(input().strip())
for _ in range(t):
	intervals = list()
	(n, m) = list(map(int, input().strip().split()))
	for _ in range(n):
		(l, r) = list(map(int, input().strip().split()))
		intervals.append([l, r])
	intervals.sort()
	for _ in range(m):
		p = int(input().strip())
		ans = binarySearch(intervals, p)
		print(ans)


from sys import stdin, stdout
input = stdin.readline

def binarySearch(arr, p):
	n = len(arr)
	low = 0
	high = n - 1
	pos = -1
	while high >= low:
		mid = (low + high) // 2
		if arr[mid][1] > p:
			pos = mid
			high = mid - 1
		else:
			low = mid + 1
	if pos == -1:
		return -1
	return max(0, arr[pos][0] - p)
t = int(input().strip())
for _ in range(t):
	intervals = list()
	(n, m) = list(map(int, input().strip().split()))
	for _ in range(n):
		(l, r) = list(map(int, input().strip().split()))
		intervals.append([l, r])
	intervals.sort(key=lambda x: x[0])
	for _ in range(m):
		p = int(input().strip())
		ans = binarySearch(intervals, p)
		print(ans)


t = int(input())

def findRange(time, P, N):
	low = 0
	high = N - 1
	result = -1
	while low <= high:
		mid = (low + high) // 2
		if time[mid][1] > P:
			result = mid
			high = mid - 1
		else:
			low = mid + 1
	if result == -1:
		return -1
	return max(0, time[result][0] - P)

def solve(time, N, M):
	time.sort(key=lambda x: x[0])
	for i in range(M):
		P = int(input())
		ans = findRange(time, P, N)
		print(ans)
for i in range(t):
	(N, M) = map(int, input().split())
	time = []
	for i in range(N):
		(L, R) = map(int, input().split())
		time.append([L, R])
	solve(time, N, M)


def waitTime(timeIV, N, P):
	(low, high) = (0, N - 1)
	ans = -1
	while low <= high:
		mid = low + (high - low) // 2
		if timeIV[mid][1] > P:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	if ans == -1:
		return ans
	return max(0, timeIV[ans][0] - P)

def solve(timeIV, N, M):
	timeIV.sort(key=lambda x: x[0])
	for j in range(M):
		p = int(input())
		ans = waitTime(timeIV, N, p)
		print(ans)
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	timeIV = []
	for i in range(N):
		(l, r) = map(int, input().split())
		timeIV.append([l, r])
	solve(timeIV, N, M)


def solve(times, people):
	(l, r) = (0, len(times) - 1)
	ans = -1
	while l <= r:
		mid = (l + r) // 2
		if times[mid][1] > people:
			ans = mid
			r = mid - 1
		else:
			l = mid + 1
	if ans == -1:
		return ans
	return max(0, times[ans][0] - people)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	times = []
	for t in range(n):
		(e, q) = map(int, input().split())
		times.append([e, q])
	times.sort()
	for t in range(m):
		people = int(input())
		print(solve(times, people))


def findClosestRange(timeIntervals, N, P):
	(low, high) = (0, N - 1)
	ans = -1
	while low <= high:
		mid = low + (high - low) // 2
		if timeIntervals[mid][1] > P:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	if ans == -1:
		return -1
	return max(0, timeIntervals[ans][0] - P)

def solve(timeIntervals, N, M):
	timeIntervals.sort(key=lambda x: x[0])
	for i in range(M):
		P = int(input())
		ans = findClosestRange(timeIntervals, N, P)
		print(ans)
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	timeIntervals = []
	for i in range(0, N):
		(l, r) = map(int, input().split())
		timeIntervals.append([l, r])
	solve(timeIntervals, N, M)


def before_after_time(s, e, li, time):
	if len(li) == 1:
		return (li[0], False)
	mid = (s + e) // 2
	if li[mid] == time:
		return (li[mid], True)
	if abs(e - s) == 1:
		return (li[s], li[e])
	if time > li[mid]:
		return before_after_time(mid, e, li, time)
	else:
		return before_after_time(s, mid, li, time)

def restaurent():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		d = dict()
		li = []
		arriving_time = []
		for _ in range(n):
			(start, end) = map(int, input().split())
			d[start] = end
			li.append(start)
		for _ in range(m):
			arriving_time.append(int(input()))
		li.sort()
		(s, e) = (0, len(li) - 1)
		for x in arriving_time:
			if x > d[li[e]]:
				print(-1)
				continue
			elif x < li[s]:
				print(li[0] - x)
				continue
			(before, after) = before_after_time(s, e, li, x)
			if after == True:
				print(0)
			elif after == False:
				if li[0] <= x < d[li[0]]:
					print(0)
				elif x < li[0]:
					print(li[0] - x)
				else:
					print(-1)
			elif before <= x < d[before] or after <= x < d[after]:
				print(0)
			elif x >= d[after]:
				print(-1)
			else:
				print(after - x)
restaurent()


from bisect import bisect
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a += list(map(int, input().split()))
	a.sort()
	for i in range(m):
		x = int(input())
		if x < a[0]:
			print(a[0] - x)
		elif x >= a[-1]:
			print(-1)
		else:
			b = bisect(a, x)
			if b % 2 == 1:
				print(0)
			else:
				print(a[b] - x)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	lst = []
	for __ in range(n):
		(a, b) = map(int, input().split())
		lst.append([a, b])
	lst.sort(key=lambda x: x[0])
	for __ in range(m):
		curr = int(input())
		si = 0
		ei = n - 1
		ans = -1
		while si <= ei:
			mid = (si + ei) // 2
			if lst[mid][0] < curr:
				si = mid + 1
			elif lst[mid][0] > curr:
				ei = mid - 1
				ans = mid
			else:
				ans = mid
				break
		if ans == -1:
			if lst[n - 1][0] <= curr and lst[n - 1][1] > curr:
				print(0)
			else:
				print(-1)
		elif ans == 0:
			print(lst[ans][0] - curr)
		elif lst[ans - 1][0] <= curr and lst[ans - 1][1] > curr:
			print(0)
		else:
			print(lst[ans][0] - curr)


def chefRest(timings, personTime, n):
	high = n - 1
	low = 0
	while low <= high:
		mid = low + (high - low) // 2
		if timings[mid][0] <= personTime <= timings[mid][1]:
			if timings[mid][0] <= personTime < timings[mid][1]:
				return 0
			elif mid == n - 1:
				return -1
			else:
				return timings[mid + 1][0] - personTime
		elif personTime < timings[mid][0]:
			high = mid - 1
		elif personTime > timings[mid][1]:
			low = mid + 1
	if low == n:
		return -1
	else:
		return timings[low][0] - personTime
test = int(input())
while test:
	(timeInp, personTims) = list(map(int, input().strip().split()))
	n = timeInp
	timings = []
	while timeInp:
		pair = list(map(int, input().strip().split()))
		timings.append(pair)
		timeInp -= 1
	timings.sort()
	while personTims:
		time = int(input())
		print(chefRest(timings, time, n))
		personTims -= 1
	test -= 1


import bisect
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		(x, y) = map(int, input().split())
		arr.append([x, y])
	arr.sort(key=lambda x: x[0])
	for i in range(m):
		curr_time = int(input())
		position = bisect.bisect(arr, [curr_time, 0])
		if position == 0:
			print(arr[0][0] - curr_time)
		elif arr[position - 1][1] > curr_time:
			print(0)
		elif position < n:
			print(arr[position][0] - curr_time)
		else:
			print(-1)
print()


t = int(input().strip())

def findRight(arr, start, end, num):
	if start > end:
		return -1
	if start == end:
		return start
	mid = int((start + end) / 2)
	if arr[mid] == num:
		return mid
	if num > arr[mid]:
		return findRight(arr, mid + 1, end, num)
	else:
		return findRight(arr, start, mid, num)
for _ in range(t):
	hashmap = {}
	l = []
	(N, M) = [int(n) for n in input().strip().split()]
	for _ in range(N):
		(low, high) = [int(n) for n in input().strip().split()]
		hashmap[low] = high
		l.append(low)
	l.sort()
	for _ in range(M):
		num = int(input().strip())
		index = findRight(l, 0, N - 1, num)
		if l[index] == num:
			print(0)
		elif num < l[0]:
			print(l[0] - num)
		elif num >= hashmap[l[-1]]:
			print(-1)
		elif num > l[index]:
			print(0)
		else:
			x = hashmap[l[index - 1]]
			if num >= x:
				print(abs(l[index] - num))
			else:
				print(0)


import bisect
T = int(input())
while T > 0:
	T -= 1
	(N, M) = [int(x) for x in input().split(' ')]
	listOpen = []
	for i in range(N):
		(L, R) = [int(x) for x in input().split(' ')]
		listOpen.append([L, R])
	listOpen.sort()
	list1StartTime = [x[0] for x in listOpen]
	listP = []
	for i in range(M):
		P = int(input())
		ans = -1
		index = bisect.bisect_right(list1StartTime, P, lo=0, hi=len(list1StartTime))
		if index != 0 and listOpen[index - 1][1] > P:
			ans = 0
		elif index != len(listOpen):
			ans = listOpen[index][0] - P
		print(ans)


from bisect import bisect_right
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	li_left = []
	li_right = []
	for j in range(n):
		(l, r) = map(int, input().split())
		li_left.append(l)
		li_right.append(r)
	li_left.sort()
	li_right.sort()
	for j in range(m):
		pi = int(input())
		ans = -1
		index = bisect_right(li_right, pi)
		if index != n:
			if li_left[index] <= pi:
				ans = 0
			elif li_left[index] > pi:
				ans = li_left[index] - pi
		else:
			ans = -1
		print(ans)


from bisect import bisect_left as lower_bound
T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	time = []
	for i in range(n):
		(li, ri) = map(int, input().split())
		time.append([li, ri])
	time.sort(key=lambda x: x[0])
	l = []
	r = []
	for i in range(n):
		l.append(time[i][0])
		r.append(time[i][1])
	for i in range(m):
		p = int(input())
		if n == 1:
			if l[0] <= p < r[0]:
				print(0)
			elif p < l[0]:
				print(l[0] - p)
			else:
				print(-1)
			continue
		ans = 0
		index = lower_bound(l, p)
		if index >= 1 and index < n:
			if l[index] > p and r[index - 1] <= p:
				ans = l[index] - p
		elif index == 0:
			if l[index] > p:
				ans = l[index] - p
		elif p >= r[-1]:
			ans = -1
		print(ans)


import bisect
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	opening = {}
	closing = []
	for N in range(n):
		(o, c) = map(int, input().split())
		closing.append(c)
		opening[c] = o
	closing.sort()
	for M in range(m):
		q = int(input())
		idx = bisect.bisect_right(closing, q)
		if idx == n:
			print(-1)
		elif opening[closing[idx]] <= q:
			print(0)
		else:
			print(opening[closing[idx]] - q)


from bisect import bisect_left
from os import wait
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	TimeSlot = []
	N2 = N * 2
	for i in range(N):
		(s, e) = map(int, input().split())
		TimeSlot.append(s)
		TimeSlot.append(e)
	TimeSlot.sort()
	Pi = [int(input()) for _ in range(M)]
	for p in Pi:
		waittime = 0
		index = bisect_left(TimeSlot, p)
		if index == N2:
			waittime = -1
		elif index % 2 == 0:
			waittime = TimeSlot[index] - p
		else:
			waittime = TimeSlot[index] - p
			if waittime == 0:
				index += 1
				if index == N2:
					waittime = -1
				else:
					waittime = TimeSlot[index] - p
			else:
				waittime = 0
		print(waittime)


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	l = []
	for j in range(N):
		(L, R) = list(map(int, input().split()))
		l.append(L)
		l.append(R)
	l.sort()
	for i in range(0, M):
		p = int(input())
		if p < l[0]:
			print(l[0] - p)
			continue
		elif p >= l[len(l) - 1]:
			print(-1)
			continue
		(lo, hi) = (0, len(l) - 1)
		z = False
		while lo <= hi:
			mid = lo + (hi - lo) // 2
			if l[mid] == p:
				if mid % 2 != 0:
					ans = l[mid + 1] - l[mid]
				else:
					ans = 0
				z = True
				break
			elif l[mid] > p:
				hi = mid - 1
			elif l[mid] < p:
				ans = mid
				lo = mid + 1
		if z == False:
			if ans % 2 == 0:
				ans = 0
			elif ans % 2 != 0:
				ans = l[ans + 1] - p
		print(ans)


t = int(input())
for co in range(t):
	l = []
	(n, m) = list(map(int, input().split()))
	for i in range(n):
		l.append(list(map(int, input().split())))
	l.sort()
	for i in range(m):
		c = 0
		s = int(input())
		if s >= l[-1][1]:
			print('-1')
		elif s < l[0][0]:
			print(l[0][0] - s)
		elif s > l[-1][0] and s < l[-1][1] and (c == 0):
			print('0')
		else:
			hi = n - 1
			lo = 0
			ans = -1
			while lo <= hi:
				j = (lo + hi) // 2
				if s >= l[j][0] and s < l[j][1]:
					print('0')
					c = 1
					break
				elif s < l[j][0]:
					ans = j
					hi = j - 1
				else:
					lo = j + 1
			if c == 0:
				print(l[ans][0] - s)


def ChefRes(TimeIntervals, n, m):
	for i in range(m):
		x = int(input())
		start = 0
		end = 2 * n - 1
		if x <= TimeIntervals[start]:
			print(TimeIntervals[start] - x)
			continue
		elif x >= TimeIntervals[end]:
			print(-1)
			continue
		else:
			while start <= end:
				mid = (start + end) // 2
				if mid % 2 == 0:
					openTime = TimeIntervals[mid]
					CloseTime = TimeIntervals[mid + 1]
					if x < CloseTime and x >= openTime:
						print(0)
						break
					elif x < openTime and x >= TimeIntervals[mid - 1]:
						print(openTime - x)
						break
					elif x >= CloseTime and x < TimeIntervals[mid + 2]:
						print(TimeIntervals[mid + 2] - x)
						break
					elif x < openTime:
						end = mid - 1
					else:
						start = mid + 2
				else:
					openTime = TimeIntervals[mid - 1]
					CloseTime = TimeIntervals[mid]
					if x < CloseTime and x >= openTime:
						print(0)
						break
					elif x < openTime and x >= TimeIntervals[mid - 2]:
						print(openTime - x)
						break
					elif x >= CloseTime and x < TimeIntervals[mid + 1]:
						print(TimeIntervals[mid + 1] - x)
						break
					elif x < openTime:
						end = mid - 2
					else:
						start = mid + 1
t = int(input())
for i in range(t):
	TimeIntervals = list()
	(n, m) = [int(x) for x in input().split()]
	for j in range(n):
		(L, R) = [int(x) for x in input().split()]
		TimeIntervals.append(L)
		TimeIntervals.append(R)
	TimeIntervals.sort()
	ChefRes(TimeIntervals, n, m)


def find_index(arr, n, K):
	start = 0
	end = n - 1
	while start <= end:
		mid = (start + end) // 2
		if arr[mid] == K:
			return mid
		elif arr[mid] < K:
			start = mid + 1
		else:
			end = mid - 1
	return end + 1
t = int(input())
for test in range(t):
	(n, m) = map(int, input().split())
	resT = []
	l = []
	p = []
	for i in range(n):
		(left, r) = map(int, input().split())
		resT.append([left, r])
		l.append(left)
	for j in range(m):
		p.append(int(input()))
	resT.sort()
	l.sort()
	for i in range(m):
		time = p[i]
		ind = find_index(l, n, time)
		if ind == 0:
			if l[ind] == time:
				print(0)
			else:
				print(l[0] - time)
		elif ind == n:
			if resT[ind - 1][1] > time:
				print(0)
			else:
				print(-1)
		elif resT[ind - 1][1] > time:
			print(0)
		else:
			print(l[ind] - time)


def fun(ar, x):
	l = 0
	u = len(ar)
	an = -1
	while l <= u:
		m = (l + u) // 2
		if m >= len(ar) or m < 0:
			return an
		(s, e) = (ar[m][0], ar[m][1])
		if x >= e:
			l = m + 1
		elif e > x:
			an = m
			u = m - 1
	return an
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ar = []
	for i in range(n):
		(l, r) = map(int, input().split())
		ar.append([l, r])
	ar.sort()
	for i in range(m):
		x = int(input())
		an = fun(ar, x)
		if an == -1:
			print(an)
		elif x >= ar[an][0]:
			print(0)
		else:
			print(ar[an][0] - x)


def least_greater_than(a, N, key):
	start = 0
	end = N
	ans = -1
	while end >= start:
		mid = (start + end) // 2
		if mid >= N or mid < 0:
			break
		elif a[mid][1] <= key:
			start = mid + 1
		elif a[mid][1] > key:
			ans = mid
			end = mid - 1
	return ans
T = int(input())
ans = []
for _ in range(T):
	(N, M) = [int(i) for i in input().split()]
	L = []
	R = []
	P = []
	A = []
	for i in range(N):
		(l, r) = [int(i) for i in input().split()]
		A.append([l, r])
	A.sort()
	for i in range(M):
		p = int(input())
		x = least_greater_than(A, N, p)
		if x == -1:
			ans.append(-1)
		elif p >= A[x][0]:
			ans.append(0)
		else:
			ans.append(A[x][0] - p)
for i in ans:
	print(i)


def binary_search(interval, x):
	start = 0
	end = len(interval) - 1
	while start <= end:
		mid = start + (end - start) // 2
		if interval[mid][0] <= x < interval[mid][1]:
			return mid
		elif interval[mid][0] > x:
			end = mid - 1
		else:
			start = mid + 1
	return [start, mid]
t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	interval = []
	for i in range(n):
		(l, r) = map(int, input().split())
		interval.append([l, r])
	p = []
	for i in range(m):
		p.append(int(input()))
	interval = sorted(interval, key=lambda x: x[0])
	for x in p:
		res = binary_search(interval, x)
		if isinstance(res, list):
			(l, r) = res
			if l >= n:
				print(-1)
			else:
				print(interval[l][0] - x)
		else:
			print(0)
	t -= 1


def binary_search(num):
	start = 0
	end = n - 1
	if num < intervals[0][0]:
		return intervals[0][0] - num
	elif num >= intervals[-1][1]:
		return -1
	elif num < intervals[-1][1] and num >= intervals[-1][0]:
		return 0
	while start <= end:
		mid = (start + end) // 2
		if num >= intervals[mid][0] and num < intervals[mid][1]:
			return 0
		if num < intervals[mid][0]:
			ans = intervals[mid][0] - num
			end = mid - 1
		else:
			start = mid + 1
	return ans
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	intervals = []
	for _ in range(n):
		intervals.append(list(map(int, input().split())))
	intervals = sorted(intervals, key=lambda x: x[0])
	for _ in range(m):
		c = int(input())
		print(binary_search(c))


from sys import maxsize, stdout, stdin, stderr
mod = int(1000000000.0 + 7)

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

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

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

def S():
	return input().strip()

def grid(r, c):
	return [lint() for i in range(r)]

def debug(*args, c=6):
	print('\x1b[3{}m'.format(c), *args, '\x1b[0m', file=stderr)
from bisect import bisect
for _ in range(I()):
	(n, m) = tup()
	ls = []
	for i in range(n):
		ls.extend(lint())
	ls.sort()
	for j in range(m):
		x = I()
		b = bisect(ls, x)
		debug(b)
		if b > len(ls) - 1:
			print(-1)
		elif b % 2 == 0:
			print(abs(x - ls[b]))
		else:
			print(0)


import bisect
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = []
	l = []
	r = []
	for _ in range(n):
		(a, b) = map(int, input().split())
		l.append(a)
		r.append(b)
	l.sort()
	r.sort()
	for j in range(m):
		item = int(input())
		a = bisect.bisect(l, item)
		if a == 0:
			print(l[0] - item)
		elif item < r[a - 1]:
			print(0)
		elif a != n:
			print(l[a] - item)
		else:
			print(-1)


import bisect
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	l1 = []
	l2 = []
	for i in range(n):
		(l, r) = list(map(int, input().split()))
		l1.append(l)
		l2.append(r)
	l1.sort()
	l2.sort()
	for j in range(m):
		p = int(input())
		a = bisect.bisect(l1, p)
		if a == 0:
			print(l1[0] - p)
		elif p < l2[a - 1]:
			print(0)
		elif a != n:
			print(l1[a] - p)
		else:
			print(-1)


def binary_search(a, m):
	start = 0
	end = len(a) - 1
	mid = 0
	while start <= end:
		mid = (start + end) // 2
		if m >= a[mid][0] and m < a[mid][1]:
			return 0
		elif m == a[mid][1]:
			if mid == len(a) - 1:
				return -1
			else:
				return a[mid + 1][0] - m
		elif m < a[mid][0]:
			end = mid - 1
		else:
			start = mid + 1
	if a[mid][0] > m:
		return a[mid][0] - m
	elif mid + 1 == len(a):
		return -1
	else:
		return a[mid + 1][0] - m
t = int(input())
while t > 0:
	a = input().split()
	n = int(a[0])
	m = int(a[1])
	a = []
	for i in range(n):
		x = input().split()
		a.append(int(x[0]))
		a.append(int(x[1]))
	a.sort()
	b = []
	for i in range(1, len(a), 2):
		b.append([a[i - 1], a[i]])
	for i in range(m):
		query = int(input())
		print(binary_search(b, query))
	t -= 1


def bSearch(i, j, arr, x):
	ans = -1
	while i <= j:
		mid = (i + j) // 2
		if x < arr[mid][1]:
			if arr[mid][0] <= x:
				ans = 0
				return ans
			else:
				ans = arr[mid][0] - x
				j = mid - 1
		else:
			i = mid + 1
	return ans

def solve():
	(n, m) = list(map(int, input().split()))
	arr = []
	for _ in range(n):
		temp = list(map(int, input().split()))
		arr.append(temp)
	arr.sort()
	for i in range(m):
		x = int(input())
		print(bSearch(0, n - 1, arr, x))
t = int(input())
while t != 0:
	solve()
	t -= 1


def binarySearch(time, data):
	i = 0
	j = len(time) - 1
	while i <= j:
		m = (i + j) // 2
		if time[m][0] < data:
			i = m + 1
		elif time[m][0] > data:
			j = m - 1
		else:
			return m
	return j
test = int(input())
for _ in range(test):
	(n, m) = map(int, input().split())
	time = []
	for i in range(n):
		temp = list(map(int, input().split()))
		time.append(temp)
	time = sorted(time, key=lambda item: item[0])
	for i in range(m):
		data = int(input())
		if data < time[0][0]:
			print(time[0][0] - data)
		else:
			index = binarySearch(time, data)
			if time[index][1] > data:
				print(0)
			elif index < n - 1:
				print(time[index + 1][0] - data)
			else:
				print(-1)