AtCoder Beginner Contest 128 - Roadwork

There is an infinitely long street that runs west to east, which we consider as a number line.
There are N roadworks scheduled on this street.
The i-th roadwork blocks the point at coordinate X_i from time S_i - 0.5 to time T_i - 0.5.
Q people are standing at coordinate 0. The i-th person will start the coordinate 0 at time D_i, continue to walk with speed 1 in the positive direction and stop walking when reaching a blocked point.
Find the distance each of the Q people will walk.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N, Q \leq 2 \times 10^5
 - 0 \leq S_i < T_i \leq 10^9
 - 1 \leq X_i \leq 10^9
 - 0 \leq D_1 < D_2 < ... < D_Q \leq 10^9
 - If i \neq j and X_i = X_j, the intervals [S_i, T_i) and [S_j, T_j) do not overlap.

-----Input-----
Input is given from Standard Input in the following format:
N Q
S_1 T_1 X_1
:
S_N T_N X_N
D_1
:
D_Q

-----Output-----
Print Q lines. The i-th line should contain the distance the i-th person will walk or -1 if that person walks forever.

-----Sample Input-----
4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8

-----Sample Output-----
2
2
10
-1
13
-1

The first person starts coordinate 0 at time 0 and stops walking at coordinate 2 when reaching a point blocked by the first roadwork at time 2.
The second person starts coordinate 0 at time 1 and reaches coordinate 2 at time 3. The first roadwork has ended, but the fourth roadwork has begun, so this person also stops walking at coordinate 2.
The fourth and sixth persons encounter no roadworks while walking, so they walk forever. The output for these cases is -1.

Difficulty: MEDIUM

Starter code:

Solutions:
import sys
input = sys.stdin.readline
INF = 1 << 31
from heapq import heapify, heappop, heappush
from collections import defaultdict
(N, Q) = map(int, input().split())
event = []
for _ in range(N):
	(s, t, x) = map(int, input().split())
	event.append((s - x, -1, x))
	event.append((t - x, 0, x))
for i in range(Q):
	d = int(input())
	event.append((d, 1, i))
q = []
ans = [-1] * Q
event.sort()
push = defaultdict(int)
pop = defaultdict(int)
for i in range(2 * N + Q):
	(t, typ, x) = event[i]
	if typ == -1:
		heappush(q, x)
		push[x] += 1
	elif typ == 0:
		pop[x] += 1
	else:
		p = -1
		if q:
			p = q[0]
		while p != -1 and push[p] - pop[p] == 0:
			heappop(q)
			if q:
				p = q[0]
			else:
				p = -1
				break
		ans[x] = p
print('\n'.join(map(str, ans)))


from bisect import bisect_left, bisect_right
(N, Q) = map(int, input().split())
STX = [[int(i) for i in input().split()] for _ in range(N)]
D = [int(input()) for _ in range(Q)]
STX.sort(key=lambda x: x[2])
ans = [-1] * Q
skip = [-1] * Q
for (S, T, X) in STX:
	left = bisect_left(D, S - X)
	right = bisect_right(D, T - X - 1)
	while left < right:
		if skip[left] < 0:
			skip[left] = right
			ans[left] = X
			left += 1
		else:
			left = skip[left]
print(*ans, sep='\n')


import sys
input = sys.stdin.readline
from bisect import bisect_left
(n, q) = map(int, input().split())
STX = [tuple(map(int, input().split())) for _ in range(n)]
STX.sort(key=lambda x: x[2])
D = [int(input()) for _ in range(q)]
Ans = [-1] * q
Jump = [-1] * q
for (s, t, x) in STX:
	l = bisect_left(D, s - x)
	r = bisect_left(D, t - x)
	while l < r:
		s = Jump[l]
		if s == -1:
			Ans[l] = x
			Jump[l] = r
			l += 1
		else:
			l = s
print(*Ans, sep='\n')


from bisect import bisect_left
from operator import itemgetter
(N, Q) = map(int, input().split(' '))
check_points = [tuple(map(int, input().split(' '))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = [-1] * Q
jump = [-1] * Q
check_points = sorted(check_points, key=itemgetter(2))
b_left = bisect_left
for line in check_points:
	(s, f, x) = line
	start = s - x
	end = f - x
	left = b_left(querys, start)
	right = b_left(querys, end)
	while left < right:
		if time[left] == -1:
			time[left] = x
			jump[left] = right
			left += 1
		else:
			left = jump[left]
for t in time:
	print(t)


import sys
input = lambda : sys.stdin.buffer.readline().rstrip().decode('utf-8')
from heapq import heappush, heappop
(n, q) = map(int, input().split())
STX = [tuple(map(int, input().split())) for i in range(n)]
D = [int(input()) for i in range(q)]
event = []
for (si, ti, xi) in STX:
	event.append((si - xi, 0, xi))
	event.append((ti - xi, -1, xi))
for di in D:
	event.append((di, 1, di))
event.sort()
hq = []
S = set()
for (time, query, number) in event:
	if query == 0:
		heappush(hq, number)
		S.add(number)
	elif query == -1:
		S.remove(number)
	else:
		while hq and hq[0] not in S:
			heappop(hq)
		if not hq:
			print(-1)
		else:
			print(hq[0])


from heapq import heappush, heappop
(N, Q) = list(map(int, input().split()))
(l, q) = ([], [])
u = set()
for _ in range(N):
	(S, T, X) = list(map(int, input().split()))
	l.append((S - X, 1, X))
	l.append((T - X, 0, X))
for i in range(Q):
	l.append((int(input()), 2, i))
l.sort()
for (_, m, x) in l:
	if m == 0:
		u.remove(x)
	elif m == 1:
		heappush(q, x)
		u.add(x)
	else:
		while q:
			if q[0] not in u:
				heappop(q)
			else:
				break
		print(q[0] if q else -1)


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
imos = []
for i in range(n):
	(s, t, x) = map(int, input().split())
	imos.append((s - x, x))
	imos.append((t - x, -x))
ans = set()
j = 0
for i in range(q):
	d = int(input())
	imos.append((d, 1e+100))
imos.sort()
m = 1e+100
flag = False
for (t, stop) in imos:
	if stop == 1e+100:
		if ans:
			if not flag:
				m = min(ans)
				flag = True
			print(m)
		else:
			print(-1)
	elif stop > 0:
		ans.add(stop)
		if stop < m:
			m = stop
			flag = True
	else:
		ans.remove(-stop)
		if m == -stop:
			flag = False


import heapq
(N, Q) = list(map(int, input().split()))
(S, T, X) = ([], [], [])
Ev = []
for _ in range(N):
	(s, t, x) = list(map(int, input().split()))
	Ev.append((s - x, True, x))
	Ev.append((t - x, False, x))
Ev.sort()
h = []
closed = set()
eidx = 0
for i in range(Q):
	d = int(input())
	while eidx < 2 * N and Ev[eidx][0] <= d:
		(t, e, x) = Ev[eidx]
		eidx += 1
		if e:
			heapq.heappush(h, x)
			closed.add(x)
		else:
			closed.remove(x)
	while h and h[0] not in closed:
		heapq.heappop(h)
	if h:
		print(h[0])
	else:
		print(-1)


from heapq import heappop, heappush
from collections import defaultdict
(N, Q) = map(int, input().split())
events = []
for _ in range(N):
	(s, t, x) = map(int, input().split())
	events.append((s - x, 1, x))
	events.append((t - x, 2, x))
for _ in range(Q):
	d = int(input())
	events.append((d, 3, 0))
events.sort()
minimumStop = [float('INF')]
stopCount = {float('INF'): 1}
for (sec, e, x) in events:
	if e == 1:
		heappush(minimumStop, x)
		if x not in stopCount:
			stopCount[x] = 0
		stopCount[x] += 1
	if e == 3:
		while stopCount[minimumStop[0]] == 0:
			heappop(minimumStop)
		if minimumStop[0] == float('INF'):
			print(-1)
		else:
			print(minimumStop[0])
	if e == 2:
		stopCount[x] -= 1


import bisect
(N, Q) = (int(x) for x in input().split())
stop_arr = [tuple(map(int, input().split())) for _ in range(N)]
Q_arr = [int(input()) for _ in range(Q)]
stop_arr_ind = list(range(N))
stop_arr_ind.sort(key=lambda x: stop_arr[x][2])
ans_arr = [-1] * Q
skip_arr = [-1] * (Q + 1)

def update_skip(skip_arr, x):
	if skip_arr[x] == -1:
		return x
	x_dest = update_skip(skip_arr, skip_arr[x])
	skip_arr[x] = x_dest
	return x_dest
for i in stop_arr_ind:
	(s, t, x) = stop_arr[i]
	q_start = bisect.bisect_left(Q_arr, s - x)
	q_stop = bisect.bisect_left(Q_arr, t - x)
	l = q_start
	while l < q_stop:
		if skip_arr[l] == -1:
			skip_arr[l] = q_stop
			ans_arr[l] = x
			l += 1
		else:
			l = update_skip(skip_arr, l)
print(*ans_arr, sep='\n')


from bisect import bisect_left
(N, Q) = map(int, input().split())
consts = []
for _ in range(N):
	(s, t, x) = map(int, input().split())
	consts.append((x, s, t))
consts.sort()
D = [int(input()) for _ in range(Q)]
ans = [-1] * Q
jump = [-1] * Q
for (x, s, t) in consts:
	left = bisect_left(D, s - x)
	right = bisect_left(D, t - x)
	while left < right:
		if jump[left] == -1:
			ans[left] = x
			jump[left] = right
			left += 1
		else:
			left = jump[left]
print(*ans, sep='\n')


import sys
from heapq import heappush, heappop
input = sys.stdin.readline
(n, q) = map(int, input().split())
e = []
for i in range(n):
	(s, t, x) = map(int, input().split())
	e.append((s - x, 1, x))
	e.append((t - x, -1, x))
for i in range(q):
	d = int(input())
	e.append((d, 2, 0))
e.sort()
s = set()
a = []
for (time_, type_, x_) in e:
	if type_ == 1:
		s.add(x_)
		heappush(a, x_)
	elif type_ == -1:
		s.remove(x_)
	else:
		while a and a[0] not in s:
			heappop(a)
		if a:
			print(a[0])
		else:
			print(-1)


import sys
from bisect import bisect_left
(n, q) = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:n]:
	(s, t, x) = map(int, line.split())
	kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[n:]))
ans = [-1] * q
skip = [-1] * q
for (x, s, t) in kkk:
	ss = bisect_left(ddd, s - x)
	tt = bisect_left(ddd, t - x)
	while ss < tt:
		sk = skip[ss]
		if sk == -1:
			ans[ss] = x
			skip[ss] = tt
			ss += 1
		else:
			skip[ss] = max(sk, tt)
			ss = sk
print('\n'.join(map(str, ans)))


import heapq

def main():
	(N, Q) = list(map(int, input().split()))
	STX = tuple((list(map(int, input().split())) for _ in range(N)))
	D = tuple([int(input()) for _ in range(Q)])
	L = []
	for (s, t, x) in STX:
		L.append((x, s - x, t - x))
	L.sort(key=lambda x: x[1])
	q = []
	cnt = 0
	push = heapq.heappush
	pop = heapq.heappop
	t = []
	for i in range(Q):
		while cnt < len(L) and D[i] >= L[cnt][1]:
			if t != []:
				push(q, t)
				t = []
			push(q, L[cnt])
			cnt += 1
		if t != [] and t[2] > D[i]:
			print(t[0])
		else:
			while q != []:
				t = pop(q)
				if t[2] > D[i]:
					print(t[0])
					break
			else:
				t = []
				print(-1)
main()


import heapq

def main():
	(N, Q) = map(int, input().split())
	STX = [tuple(map(int, input().split())) for _ in range(N)]
	ev = []
	for (s, t, x) in STX:
		ev.append((s - x, True, x))
		ev.append((t - x, False, x))
	ev.sort(reverse=True)
	bar = []
	dead = {}
	for d in [int(input()) for _ in range(Q)]:
		while ev and ev[-1][0] <= d:
			(t, a, x) = ev.pop()
			if a:
				heapq.heappush(bar, x)
			else:
				dead[x] = dead.get(x, 0) + 1
				while bar and bar[0] in dead:
					x = heapq.heappop(bar)
					if dead[x] == 1:
						del dead[x]
					else:
						dead[x] = dead[x] - 1
		print(bar[0] if bar else -1)
main()


import sys
from heapq import *
input = sys.stdin.readline
(n, Q) = [int(i) for i in input().split()]
stx = [[0] * 3 for _ in range(n)]
for j in range(n):
	a = [int(i) for i in input().split()]
	stx[j] = [a[0] - a[2], a[1] - a[2], a[2]]
q = [int(input()) for i in range(Q)]
stx.sort()
xt = []
pt = 0
for d in q:
	while pt < n and stx[pt][0] <= d:
		heappush(xt, (stx[pt][2], stx[pt][1]))
		pt += 1
	while xt and xt[0][1] <= d:
		heappop(xt)
	if xt:
		print(xt[0][0])
	else:
		print(-1)


import bisect
import sys
sys.setrecursionlimit(10000)
INF = float('inf')
(N, Q) = list(map(int, next(sys.stdin).split()))
STX = [list(map(int, next(sys.stdin).split())) for _ in range(N)]
D = [int(next(sys.stdin)) for _ in range(Q)]
ans = [-1] * Q
nexts = [-1] * Q
for (s, t, x) in sorted(STX, key=lambda stx: (stx[2], stx[1])):
	lo = max(0, bisect.bisect_left(D, s - x))
	hi = min(len(D), bisect.bisect_left(D, t - x))
	p = lo
	while p < hi:
		if nexts[p] == -1:
			ans[p] = x
			nexts[p] = hi
			p += 1
		else:
			prev = p
			p = nexts[p]
			nexts[prev] = hi
print('\n'.join(map(str, ans)))


import sys
input = sys.stdin.readline
(n, Q) = map(int, input().split())
b_num = 2 ** (n - 1).bit_length()
mx = 10 ** 9
segl = [mx] * 2 * b_num

def update(k, x):
	k += b_num - 1
	segl[k] = x
	while k + 1:
		k = (k - 1) // 2
		segl[k] = min(segl[k * 2 + 1], segl[k * 2 + 2])
xs = []
for i in range(n):
	(s, t, x) = map(int, input().split())
	xs += [(s - x, True, x, i), (t - x, False, x, i)]
qs = []
for _ in range(Q):
	qs.append(int(input()))
xs.sort(key=lambda x: x[0])
j = 0
for x in xs:
	while Q - j:
		if qs[j] < x[0]:
			print(segl[0] if segl[0] != mx else -1)
			j += 1
			continue
		break
	update(x[3], x[2] if x[1] else mx)
while Q - j:
	print(-1)
	j += 1


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
import heapq
S = []
D = dict()
for i in range(n):
	(s, t, x) = map(int, input().split())
	S.append((1, x, max(0, s - x)))
	S.append((-1, x, max(0, t - x)))
	D[x] = False
S.sort(key=lambda x: x[2])
X = []
cur = 0
for i in range(q):
	d = int(input())
	while cur < 2 * n:
		(a, b, c) = S[cur]
		if c > d:
			break
		else:
			cur += 1
			if a == 1:
				heapq.heappush(X, b)
				D[b] = True
			else:
				D[b] = False
	while X:
		ans = heapq.heappop(X)
		if D[ans]:
			print(ans)
			heapq.heappush(X, ans)
			break
	if not X:
		print(-1)


import sys
from heapq import heappush, heappop
from operator import itemgetter
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

def main():
	(N, Q) = map(int, readline().split())
	work = [0] * N
	for i in range(N):
		(s, t, x) = map(int, readline().split())
		work[i] = (x, s - x, t - x)
	query = list(map(int, read().split()))
	work.sort(key=itemgetter(1))
	hq = []
	ans = [0] * Q
	idx = 0
	for (i, d) in enumerate(query):
		while idx < N and work[idx][1] <= d:
			heappush(hq, work[idx])
			idx += 1
		while hq and hq[0][2] <= d:
			heappop(hq)
		if not hq:
			ans[i] = -1
		else:
			ans[i] = hq[0][0]
	print(*ans, sep='\n')
	return

def __starting_point():
	main()
__starting_point()


import sys
input = sys.stdin.readline
from heapq import heappop, heappush
from collections import defaultdict
(N, Q) = map(int, input().split())
lst = []
for i in range(N):
	(s, t, x) = map(int, input().split())
	lst.append((t - x, 0, x))
	lst.append((s - x, 1, x))
for i in range(Q):
	lst.append((int(input()), 2, i))
lst.sort()
ans = [-1] * Q
se = set()
se_hp = []
for (a, b, c) in lst:
	if b == 0:
		se.remove(c)
	elif b == 1:
		se.add(c)
		heappush(se_hp, c)
	else:
		while se_hp and se_hp[0] not in se:
			heappop(se_hp)
		ans[c] = se_hp[0] if se_hp else -1
print('\n'.join(map(str, ans)))


def main():
	from bisect import bisect_left
	I = 10 ** 9 + 1
	(n, q, *t) = map(int, open(0).read().split())
	d = tuple(t[-q:])
	t = t[:-q]
	N0 = 2 ** (q - 1).bit_length()
	data = [I] * 2 * N0
	for (x, l, r) in sorted(((x, bisect_left(d, s - x) + N0, bisect_left(d, t - x) + N0) for (s, t, x) in zip(t[::3], t[1::3], t[2::3])), reverse=1):
		while l < r:
			if r & 1:
				r -= 1
				data[r - 1] = x
			if l & 1:
				data[l - 1] = x
				l += 1
			l >>= 1
			r >>= 1
	for k in range(N0 - 1, q + N0 - 1):
		s = I
		while ~k:
			if data[k] < s:
				s = data[k]
			k = (k - 1) // 2
		print(-(s == I) or s)
main()


from collections import defaultdict
from heapq import heappush, heappop
(N, Q) = map(int, input().split())
events = []
for i in range(N):
	(s, t, x) = map(int, input().split())
	events.append((s - x, 0, x))
	events.append((t - x, 1, x))
for i in range(Q):
	d = int(input())
	events.append((d, 2, i))
events = sorted(events)
INF = 10 ** 13
q = [INF]
cnt = defaultdict(int)
ans = [INF] * Q
for (a, b, c) in events:
	if b == 0:
		heappush(q, c)
		cnt[c] += 1
	elif b == 1:
		cnt[c] -= 1
	else:
		while len(q) > 1 and cnt[q[0]] == 0:
			heappop(q)
		if q[0] == INF:
			ans[c] = -1
		else:
			ans[c] = q[0]
for a in ans:
	print(a)


(N, Q) = list(map(int, input().split()))
STX = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]
L = [(s - x - 0.5, t - x - 0.5, x) for (s, t, x) in STX] + [(d,) for d in D]
L.sort()
import heapq
hp = []
memo = {}
for l in L:
	if len(l) == 1:
		while hp and l[0] > memo[hp[0]]:
			heapq.heappop(hp)
		if hp:
			print(hp[0])
		else:
			print(-1)
	else:
		heapq.heappush(hp, l[2])
		memo[l[2]] = l[1]


from bisect import bisect_left
import sys
input = sys.stdin.readline

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def same(self, x, y):
		return self.find(x) == self.find(y)

def main():
	(N, Q) = list(map(int, input().split()))
	kouji = [list(map(int, input().split())) for _ in range(N)]
	D = [int(input()) for _ in range(Q)]
	ans = [-1] * Q
	nxt = [i + 1 for i in range(Q)]
	uf = UnionFind(Q)
	kouji.sort(key=lambda x: x[2])
	for i in range(N):
		(S, T, X) = kouji[i]
		L = S - X
		R = T - X - 1
		L_idx = bisect_left(D, L)
		R_idx = bisect_left(D, R + 1)
		p = L_idx
		while p < R_idx:
			if ans[p] == -1:
				ans[p] = X
				uf.union(L_idx, p)
				nxt[p] = R_idx
				p += 1
			else:
				par = uf.find(p)
				p = nxt[par]
				uf.union(L_idx, par)
				par = uf.find(par)
				if nxt[par] < R_idx:
					nxt[par] = R_idx
				if nxt[par] < p:
					nxt[par] = p
	for i in range(Q):
		print(ans[i])

def __starting_point():
	main()
__starting_point()


def main():
	import sys
	input = lambda : sys.stdin.readline().rstrip()
	from heapq import heappush, heappop
	running = []
	events = []
	delete = set()
	(n, q) = list(map(int, input().split()))
	for _ in range(n):
		(s, t, x) = list(map(int, input().split()))
		events.append((s - x, x, 1))
		events.append((t - x, x, 0))
	for _ in range(q):
		d = int(input())
		events.append((d, 10 ** 10, 2))
	events.sort()
	for i in range(len(events)):
		temp = events[i]
		if temp[-1] == 1:
			heappush(running, temp[1])
			delete.discard(temp[1])
		elif temp[-1] == 0:
			delete.add(temp[1])
		else:
			flag = 1
			while running:
				p = heappop(running)
				if p not in delete:
					flag = 0
					heappush(running, p)
					print(p)
					break
			if flag:
				print(-1)

def __starting_point():
	main()
__starting_point()


import sys
import bisect
input = sys.stdin.readline
(N, Q) = map(int, input().split(' '))
construction = [list(map(int, input().split(' '))) for _ in range(N)]
D = [int(input()) for _ in range(Q)]
construction = sorted(construction, key=lambda x: x[2])
dist = [-1] * Q
jump = [-1] * Q
indices = list(range(Q))
for (s, t, x) in construction:
	i1 = bisect.bisect_left(D, s - x)
	i2 = bisect.bisect_left(D, t - x)
	i = i1
	while i < i2:
		k = jump[i]
		if k != -1:
			i = k
		else:
			jump[i] = i2
			dist[i] = x
			i += 1
for d in dist:
	print(d)


from heapq import heappush, heappop
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
(N, Q) = map(int, input().split())
STX = [[int(x) for x in input().split()] for _ in range(N)]
EVENT = []
for (s, t, x) in STX:
	EVENT.append((s - x, 1, x))
	EVENT.append((t - x, 0, x))
for i in range(Q):
	d = int(input())
	EVENT.append((d, 2, i))
ans = [-1] * Q
EVENT.sort()
STOP = set()
h = []
for (t, op, x) in EVENT:
	if op == 2 and STOP:
		while h and h[0] not in STOP:
			heappop(h)
		ans[x] = h[0]
	elif op == 1:
		STOP.add(x)
		heappush(h, x)
	elif op == 0:
		STOP.remove(x)
print('\n'.join(map(str, ans)))


from heapq import heappush, heappop
import sys
input = sys.stdin.buffer.readline
(n, q) = map(int, input().split())
STX = [list(map(int, input().split())) for _ in range(n)]
task = []
for (s, t, x) in STX:
	task.append((t - x, 0, x))
	task.append((s - x, 1, x))
for i in range(q):
	d = int(input())
	task.append((d, 2, i))
task.sort()
kouho = set()
kouho_hp = []
ans = [-1] * q
for (a, b, c) in task:
	if b == 0:
		kouho.remove(c)
	if b == 1:
		kouho.add(c)
		heappush(kouho_hp, c)
	if b == 2:
		while kouho_hp and kouho_hp[0] not in kouho:
			heappop(kouho_hp)
		if not kouho_hp:
			continue
		else:
			ans[c] = kouho_hp[0]
print(*ans, sep='\n')


from heapq import heappush, heappop
(N, Q) = map(int, input().split())
l = []
ans = [0] * Q
used = set()
q = []
for i in range(N):
	(S, T, X) = map(int, input().split())
	l.append((S - X, 1, X))
	l.append((T - X, 0, X))
for i in range(Q):
	v = int(input())
	l.append((v, 2, i))
l.sort()
for (pos, m, x) in l:
	if m == 0:
		used.remove(x)
	elif m == 1:
		heappush(q, x)
		used.add(x)
	else:
		while q:
			if q[0] not in used:
				heappop(q)
			else:
				break
		ans[x] = q[0] if q else -1
for i in range(Q):
	print(ans[i])


import sys
input = sys.stdin.readline
from bisect import bisect_left
(N, Q) = map(int, input().split())
W = [tuple(map(int, input().split())) for _ in range(N)]
W.sort(key=lambda x: x[2])
D = [int(input()) for _ in range(Q)]
ans = [-1] * Q
skip = [-1] * Q
for (s, t, x) in W:
	l = bisect_left(D, s - x)
	r = bisect_left(D, t - x)
	while l < r:
		if skip[l] == -1:
			ans[l] = x
			skip[l] = r
			l += 1
		else:
			l = skip[l]
print(*ans, sep='\n')


import sys
input = sys.stdin.readline
INF = 1 << 31
from bisect import bisect_left

def main():
	(N, Q) = map(int, input().split())
	roadwork = [tuple(map(int, input().split())) for _ in range(N)]
	roadwork.sort(key=lambda x: x[2])
	D = [int(input()) for _ in range(Q)]
	ans = [-1] * Q
	skip = [-1] * Q
	for (s, t, x) in roadwork:
		L = bisect_left(D, s - x)
		R = bisect_left(D, t - x)
		while L < R:
			if skip[L] == -1:
				ans[L] = x
				skip[L] = R
				L += 1
			else:
				L = skip[L]
	print('\n'.join(map(str, ans)))

def __starting_point():
	main()
__starting_point()


from bisect import *
b = bisect_left
(n, q, *t) = map(int, open(0).read().split())
p = t[-q:]
(*a,) = o = [-1] * q
for (x, t, s) in sorted(zip(*[iter(t[~q::-1])] * 3)):
	(l, r) = (b(p, s - x), b(p, t - x))
	while l < r:
		if ~o[l]:
			l = o[l]
		else:
			(a[l], o[l]) = (x, r)
			l += 1
print(*a)


import sys
from bisect import bisect_left
input = sys.stdin.readline
(N, Q) = map(int, input().split())
STX = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]
STX = sorted(STX, key=lambda x: x[2])
MASK = [-1] * Q
ANS = [-1] * Q
for (s, t, x) in STX:
	s2 = s - x
	t2 = t - x
	start = bisect_left(D, s2)
	end = bisect_left(D, t2, lo=start)
	while start < end:
		if -1 == MASK[start]:
			ANS[start] = x
			MASK[start] = end
			start += 1
		else:
			start = MASK[start]
print(*ANS, sep='\n')


import sys
from bisect import bisect_left
(N, Q) = map(int, input().split())
STX = [None] * N
for i in range(N):
	(s, t, x) = map(int, input().split())
	STX[i] = [x, s, t]
STX.sort()
Dn = [None] * (Q + 1)
for i in range(Q):
	Dn[i] = int(input())
Dn[Q] = 10 ** 10
ans = [-1] * Q
skip = [-1] * Q
for (x, s, t) in STX:
	ss = bisect_left(Dn, s - x)
	tt = bisect_left(Dn, t - x)
	while ss < tt:
		sk = skip[ss]
		if sk == -1:
			ans[ss] = x
			skip[ss] = tt
			ss += 1
		else:
			ss = sk
print('\n'.join(map(str, ans)))


import sys
input = sys.stdin.readline

def bs(d, x):
	(l, r) = (0, len(d))
	while l < r:
		mid = (l + r) // 2
		if d[mid] < x:
			l = mid + 1
		else:
			r = mid
	return l

def main():
	(n, q) = map(int, input().split())
	stx = [tuple(map(int, input().split())) for _ in range(n)]
	stx = list(sorted(stx, key=lambda x: x[2]))
	dlist = [int(input()) for _ in range(q)]
	ans = [-1 for _ in range(q)]
	skip = [-1 for _ in range(q)]
	for (s, t, x) in stx:
		l = bs(dlist, s - x)
		r = bs(dlist, t - x)
		while l < r:
			if skip[l] == -1:
				ans[l] = x
				skip[l] = r
				l += 1
			else:
				l = skip[l]
	print(*ans, sep='\n')
main()


from bisect import bisect_left
from operator import itemgetter
(N, Q) = [int(i) for i in input().split()]
Construction = [tuple((int(i) for i in input().split())) for j in range(N)]
D = [int(input()) for _ in range(Q)]
ans = [-1] * Q
skip = [-1] * Q
Construction.sort(key=itemgetter(2))
for (s, t, x) in Construction:
	l = bisect_left(D, s - x)
	r = bisect_left(D, t - x)
	t = l
	while t < r:
		if skip[t] == -1:
			ans[t] = x
			skip[t] = r
			t += 1
		else:
			t = skip[t]
print(*ans, sep='\n')


import sys
input = sys.stdin.readline
from bisect import bisect_left
(n, q) = map(int, input().split())
stop = []
for i in range(n):
	(s, t, x) = map(int, input().split())
	stop.append((s, t, x))
stop.sort(key=lambda x: x[2])
d = [int(input()) for i in range(q)]
R = [-1] * q
ans = [-1] * q
for (s, t, x) in stop:
	l = bisect_left(d, s - x)
	r = bisect_left(d, t - x)
	while l < r:
		if R[l] == -1:
			ans[l] = x
			R[l] = r
			l += 1
		else:
			l = R[l]
for x in ans:
	print(x)


import sys
import bisect
input = sys.stdin.readline
(N, Q) = map(int, input().split())
STX = [list(map(int, input().split())) for _ in range(N)]
STX = sorted(STX, key=lambda x: x[2])
D = [int(input()) for _ in range(Q)]
ans = [-1] * Q
index = [-1] * Q
for (s, t, x) in STX:
	left = bisect.bisect_left(D, s - x - 0.5)
	right = bisect.bisect_left(D, t - x - 0.5)
	now = left
	while now < right:
		if index[now] == -1:
			ans[now] = x
			index[now] = right
			now += 1
		else:
			now = index[now]
for a in ans:
	print(a)


import sys
input = sys.stdin.readline
from heapq import heappop, heappush
(N, Q) = map(int, input().split())
task = []
STX = [[int(x) for x in input().split()] for _ in range(N)]
for (s, t, x) in STX:
	task.append((t - x, 0, x))
	task.append((s - x, 1, x))
for i in range(Q):
	d = int(input())
	task.append((d, 2, i))
answer = [-1] * Q
task.sort()
se = set()
se_hp = []
for (a, b, c) in task:
	if not b:
		se.remove(c)
	elif b & 1:
		se.add(c)
		heappush(se_hp, c)
	else:
		while se_hp and se_hp[0] not in se:
			heappop(se_hp)
		answer[c] = se_hp[0] if se_hp else -1
print('\n'.join(map(str, answer)))


from heapq import heappush, heappop
import sys
input = sys.stdin.buffer.readline
(N, Q) = map(int, input().split())
E = []
for i in range(N):
	(s, t, x) = map(int, input().split())
	E.append((0, t - x, x, i))
	E.append((1, s - x, x, i))
D = [int(input()) for _ in range(Q)]
E.sort(key=lambda a: a[1], reverse=True)
ans = []
que = [(10 ** 18, -1)]
V = set()
for d in D:
	while E and E[-1][1] <= d:
		(f, _, x, i) = E.pop()
		if f == 0:
			V.add(i)
		else:
			heappush(que, (x, i))
	while que[0][1] in V:
		heappop(que)
	ans.append(que[0][0])
ans = [a if a < 10 ** 18 else -1 for a in ans]
print(*ans, sep='\n')


import bisect
import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
events = [list(map(int, input().split())) for _ in range(n)]
events.sort(key=lambda x: x[2])
departures = [int(input()) for _ in range(q)]
ans = ['-1'] * q
skip = [-1] * q
for (start, end, pos) in events:
	left = bisect.bisect_left(departures, start - pos)
	right = bisect.bisect_left(departures, end - pos)
	while left < right:
		if skip[left] == -1:
			ans[left] = str(pos)
			skip[left] = right
			left += 1
		else:
			left = skip[left]
print('\n'.join(ans))


from bisect import bisect_left
import sys
(n, Q) = [int(x) for x in sys.stdin.readline().split()]
stx = [[int(x) for x in sys.stdin.readline().split()] for i in range(n)]
q = [int(sys.stdin.readline()) for i in range(Q)]
stx.sort(key=lambda x: x[2])
ans = [-1 for i in range(Q)]
skip = [-1 for i in range(Q)]
for (s, t, x) in stx:
	begin = bisect_left(q, s - x)
	end = bisect_left(q, t - x)
	while begin < end:
		if skip[begin] == -1:
			ans[begin] = x
			skip[begin] = end
			begin += 1
		else:
			begin = skip[begin]
for e in ans:
	print(e)


import sys
from bisect import bisect_left

def main():
	input = sys.stdin.readline
	(N, Q) = map(int, input().split())
	closure = []
	for _ in range(N):
		(start, end, pos) = map(int, input().split())
		closure.append((pos, start, end))
	closure.sort()
	D = [int(input()) for _ in range(Q)]
	ans = [-1] * Q
	skip = [-1] * Q
	for (pos, start, end) in closure:
		left = bisect_left(D, start - pos)
		right = bisect_left(D, end - pos)
		while left < right:
			if skip[left] == -1:
				ans[left] = pos
				skip[left] = right
				left += 1
			else:
				left = skip[left]
	return ans
print(*main(), sep='\n')


import sys
from heapq import heappush, heappop
(N, Q) = map(int, input().split())
P = []
for i in range(1, N + 1):
	(s, t, x) = map(int, sys.stdin.readline().split())
	P.append((s - x, t - 1 - x, x))
P.sort()
q = []
cur = 0
ans = [-1] * Q
for (i, d) in enumerate(map(int, sys.stdin)):
	while cur < N and P[cur][0] <= d:
		(s, t, x) = P[cur]
		heappush(q, (x, t))
		cur += 1
	while q and q[0][1] < d:
		heappop(q)
	if q:
		ans[i] = q[0][0]
print(*ans, sep='\n')


def main():
	import bisect
	import sys
	input = sys.stdin.readline
	(n, q) = map(int, input().split())
	l = [list(map(int, input().split())) for i in range(n)]
	l = sorted(l, key=lambda x: x[2])
	d = [int(input()) for i in range(q)]
	ans = [-1] * q
	skip = [-1] * q
	for (s, t, x) in l:
		le = bisect.bisect_left(d, s - x)
		ri = bisect.bisect_left(d, t - x)
		while le < ri:
			if skip[le] == -1:
				ans[le] = x
				skip[le] = ri
				le += 1
			else:
				le = skip[le]
	for i in ans:
		print(i)
main()


import sys
input = lambda : sys.stdin.readline().rstrip()
from heapq import heappush, heappop
running = []
events = []
delete = set()
(n, q) = map(int, input().split())
for _ in range(n):
	(s, t, x) = map(int, input().split())
	time = max(s - x, 0)
	if t - x < 0:
		continue
	events.append((s - x, x, 1))
	events.append((t - x, x, 0))
events.sort()
ans = []
idx = -1
for _ in range(q):
	d = int(input())
	if d >= events[-1][0]:
		print(-1)
		continue
	while events[idx + 1][0] <= d:
		idx += 1
		if events[idx][2] == 1:
			heappush(running, events[idx][1])
			delete.discard(events[idx][1])
		else:
			delete.add(events[idx][1])
	flag = 1
	while running:
		x = heappop(running)
		if x not in delete:
			heappush(running, x)
			print(x)
			flag = 0
			break
	if flag:
		print(-1)


import sys
import heapq as hq
from operator import itemgetter
sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline

def solve():
	(N, Q) = map(int, rl().split())
	event = []
	for _ in range(N):
		(s, t, x) = map(int, rl().split())
		event.append((t - x, 0, x))
		event.append((s - x, 1, x))
	for _ in range(Q):
		d = int(rl())
		event.append((d, 2, -1))
	event.sort(key=itemgetter(0, 1))
	pos_set = set()
	pos_hq = []
	ans = []
	for (_, com, pos) in event:
		if com == 0:
			pos_set.remove(pos)
		elif com == 1:
			pos_set.add(pos)
			hq.heappush(pos_hq, pos)
		else:
			while pos_hq:
				if pos_hq[0] not in pos_set:
					hq.heappop(pos_hq)
				else:
					break
			ans.append(pos_hq[0] if pos_hq else -1)
	print(*ans, sep='\n')

def __starting_point():
	solve()
__starting_point()


import sys
input = sys.stdin.readline
import heapq
from operator import itemgetter
from bisect import bisect_right
(N, Q) = map(int, input().split())
Stop = []
for i in range(N):
	(S, T, X) = map(int, input().split())
	Stop.append([S - X, X, 0, i])
	Stop.append([T - X, X, 1, i])
Stop.sort(key=itemgetter(0))
q = []
notClosed = [False] * N
A = [(-1, -1)]
for (time, pos, lr, idx) in Stop:
	if lr == 0:
		heapq.heappush(q, (pos, idx))
	else:
		notClosed[idx] = True
		while len(q) > 0 and notClosed[q[0][1]]:
			aaa = heapq.heappop(q)[1]
	if len(q):
		A.append((time, q[0][0]))
	else:
		A.append((time, -1))
A0 = list(map(itemgetter(0), A))
for _ in range(Q):
	D = int(input())
	idx = bisect_right(A0, D)
	print(A[idx - 1][1])


import sys
input = sys.stdin.readline
(N, Q) = [int(_) for _ in input().split()]
STX = [[int(_) for _ in input().split()] for _ in range(N)]
D = [int(input()) for _ in range(Q)]
events = []
for stx in STX:
	(s, t, x) = stx
	events += [[s - x, 1, x], [t - x, 0, x]]
for i in range(Q):
	events += [[D[i], 2, i]]
events.sort()
block = set()
ans = [-1] * Q
m = float('inf')
for e in events:
	if e[1] == 0:
		block.remove(e[2])
		if m == e[2]:
			if block:
				m = min(block)
			else:
				m = float('inf')
	elif e[1] == 1:
		block.add(e[2])
		m = min(m, e[2])
	elif block:
		if m == float('inf'):
			ans[e[2]] = -1
		else:
			ans[e[2]] = m
print(*ans, sep='\n')


import sys
from heapq import heappush, heappop
I = sys.stdin.readlines()
(N, Q) = map(int, I[0].split())
P = []
for i in range(1, N + 1):
	(s, t, x) = map(int, I[i].split())
	P.append((s - x, t - 1 - x, x))
P.sort()
q = []
cur = 0
cnt = 0
for i in range(N + 1, N + Q + 1):
	d = int(I[i])
	while cur < N and P[cur][0] <= d:
		(s, t, x) = P[cur]
		heappush(q, (x, t))
		cnt += 1
		cur += 1
	ans = -1
	while cnt:
		if d <= q[0][1]:
			ans = q[0][0]
			break
		else:
			heappop(q)
			cnt -= 1
	print(ans)


import math
import numpy as np
import decimal
import collections
import itertools
import sys
import random

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.par = [-1 for i in range(self.n)]

	def find(self, x):
		if self.par[x] < 0:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def unite(self, x, y):
		p = self.find(x)
		q = self.find(y)
		if p == q:
			return None
		if p > q:
			(p, q) = (q, p)
		self.par[p] += self.par[q]
		self.par[q] = p

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def size(self, x):
		return -self.par[self.find(x)]

def prime_numbers(x):
	if x < 2:
		return []
	prime_numbers = [i for i in range(x)]
	prime_numbers[1] = 0
	for prime_number in prime_numbers:
		if prime_number > math.sqrt(x):
			break
		if prime_number == 0:
			continue
		for composite_number in range(2 * prime_number, x, prime_number):
			prime_numbers[composite_number] = 0
	return [prime_number for prime_number in prime_numbers if prime_number != 0]

def is_prime(x):
	if x < 2:
		return False
	if x == 2 or x == 3 or x == 5:
		return True
	if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
		return False
	prime_number = 7
	difference = 4
	while prime_number <= math.sqrt(x):
		if x % prime_number == 0:
			return False
		prime_number += difference
		difference = 6 - difference
	return True

def prime_factorize(n):
	res = []
	while n % 2 == 0:
		res.append(2)
		n //= 2
	f = 3
	while f ** 2 <= n:
		if n % f == 0:
			res.append(f)
			n //= f
		else:
			f += 2
	if n != 1:
		res.append(n)
	return res
mod = 10 ** 9 + 7

class nCr:

	def __init__(self, n):
		self.n = n
		self.fa = [1] * (self.n + 1)
		self.fi = [1] * (self.n + 1)
		for i in range(1, self.n + 1):
			self.fa[i] = self.fa[i - 1] * i % mod
			self.fi[i] = pow(self.fa[i], mod - 2, mod)

	def comb(self, n, r):
		if n < r:
			return 0
		if n < 0 or r < 0:
			return 0
		return self.fa[n] * self.fi[r] % mod * self.fi[n - r] % mod

def extgcd(a, b, d=0):
	g = a
	if b == 0:
		(x, y) = (1, 0)
	else:
		(x, y, g) = extgcd(b, a % b)
		(x, y) = (y, x - a // b * y)
	return (x, y, g)

class BinaryIndexedTree:

	def __init__(self, n):
		self.n = n
		self.BIT = [0] * (self.n + 1)

	def add(self, i, x):
		while i <= self.n:
			self.BIT[i] += x
			i += i & -i

	def query(self, i):
		res = 0
		while i > 0:
			res += self.BIT[i]
			i -= i & -i
		return res

class AssociativeArray:

	def __init__(self, q):
		self.dic = dict()
		self.q = q

	def solve(self):
		for i in range(self.q):
			Query = list(map(int, input().split()))
			if Query[0] == 0:
				(x, y, z) = Query
				self.dic[y] = z
			else:
				(x, y) = Query
				if y in self.dic:
					print(self.dic[y])
				else:
					print(0)

def floor_sum(n, m, a, b):
	res = 0
	if a >= m:
		res += (n - 1) * n * (a // m) // 2
		a %= m
	if b >= m:
		res += n * (b // m)
		b %= m
	y_max = (a * n + b) // m
	x_max = y_max * m - b
	if y_max == 0:
		return res
	res += y_max * (n + -x_max // a)
	res += floor_sum(y_max, a, m, (a - x_max % a) % a)
	return res

def z_algorithm(s):
	str_len = len(s)
	res = [0] * str_len
	res[str_len - 1] = str_len
	(i, j) = (1, 0)
	while i < str_len:
		while i + j < str_len and s[i + j] == s[j]:
			j += 1
		res[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < str_len and j > res[k] + k:
			res[i + k] = res[k]
			k += 1
		i += k
		j -= k
	return res

class Manacher:

	def __init__(self, s):
		self.s = s

	def coustruct(self):
		(i, j) = (0, 0)
		s_len = len(self.s)
		res = [0] * s_len
		while i < s_len:
			while i - j >= 0 and i + j < s_len and (self.s[i - j] == self.s[i + j]):
				j += 1
			res[i] = j
			k = 1
			while i - k >= 0 and k + res[i - k] < j:
				k += 1
			i += k
			j -= k

def mod_sqrt(a, p):
	if a == 0:
		return 0
	if p == 2:
		return 1
	k = (p - 1) // 2
	if pow(a, k, p) != 1:
		return -1
	while True:
		n = random.randint(2, p - 1)
		r = (n ** 2 - a) % p
		if r == 0:
			return n
		if pow(r, k, p) == p - 1:
			break
	k += 1
	(w, x, y, z) = (n, 1, 1, 0)
	while k:
		if k % 2:
			(y, z) = (w * y + r * x * z, x * y + w * z)
		(w, x) = (w * w + r * x * x, 2 * w * x)
		w %= p
		x %= p
		y %= p
		z %= p
		k >>= 1
	return y
import bisect
(n, q) = map(int, input().split())
stx = [list(map(int, input().split())) for i in range(n)]
d = [int(input()) for i in range(q)]
stx.sort(key=lambda x: x[2])
ans = [-1 for i in range(q)]
lis = [-1 for i in range(q)]
for (s, t, x) in stx:
	l = bisect.bisect_left(d, s - x)
	r = bisect.bisect_left(d, t - x)
	while l < r:
		if lis[l] == -1:
			ans[l] = x
			lis[l] = r
			l += 1
		else:
			l = lis[l]
print(*ans, sep='\n')


from itertools import *
import math
from collections import *
from heapq import *
from bisect import bisect_left, bisect_right
from copy import deepcopy
inf = float('inf')
mod = 10 ** 9 + 7
from functools import reduce
import sys
sys.setrecursionlimit(10 ** 7)
(n, q) = list(map(int, input().split()))
lines = sys.stdin.readlines()
stx = []
for line in lines[:n]:
	(s, t, x) = map(int, line.split())
	stx.append((x, s, t))
stx.sort()
D = list(map(int, lines[n:]))
ans = [-1] * q
skip = [-1] * q
for (x, s, t) in stx:
	ss = bisect_left(D, s - x)
	tt = bisect_left(D, t - x)
	while ss < tt:
		if skip[ss] == -1:
			ans[ss] = x
			skip[ss] = tt
			ss += 1
		else:
			ss = skip[ss]
print('\n'.join(map(str, ans)))


from heapq import heappop, heappush
from collections import defaultdict
(n, q) = list(map(int, input().split()))
task = []
for _ in range(n):
	(s, t, x) = list(map(int, input().split()))
	task.append((t - x, 0, x))
	task.append((s - x, 1, x))
for i in range(q):
	d = int(input())
	task.append((d, 2, i))
answer = [-1] * q
task.sort()
se = set()
se_hp = []
for (a, b, c) in task:
	if b == 0:
		se.remove(c)
	elif b == 1:
		se.add(c)
		heappush(se_hp, c)
	else:
		while se_hp and se_hp[0] not in se:
			heappop(se_hp)
		answer[c] = se_hp[0] if se_hp else -1
print('\n'.join(map(str, answer)))


from bisect import bisect_left as bl
(N, Q) = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
X.sort(key=lambda x: x[2])
Y = [int(input()) for _ in range(Q)]
res = [-1] * Q
jump = [-1] * Q
for (s, t, x) in X:
	l = bl(Y, s - x)
	r = bl(Y, t - x)
	while l < r:
		s = jump[l]
		if s == -1:
			res[l] = x
			jump[l] = r
			l += 1
		else:
			l = s
print(*res, sep='\n')


import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub
input = sys.stdin.readline
sys.setrecursionlimit(100000)

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

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

def read_float():
	return float(input())

def read_float_n():
	return list(map(float, input().split()))

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

def read_str_n():
	return list(map(str, input().split()))

def error_print(*args):
	print(*args, file=sys.stderr)

def mt(f):
	import time

	def wrap(*args, **kwargs):
		s = time.time()
		ret = f(*args, **kwargs)
		e = time.time()
		error_print(e - s, 'sec')
		return ret
	return wrap

@mt
def slv(N, Q, STX, D):
	E = []
	for (i, (s, t, x)) in enumerate(STX):
		E.append((s - x, 1, x, i))
		E.append((t - x, -1, x, i))
	E.sort(reverse=True)
	q = []
	done = set()
	ans = [-1] * Q
	for (j, d) in enumerate(D):
		while E and E[-1][0] <= d:
			(t, e, x, i) = E.pop()
			if e == 1:
				heapq.heappush(q, (x, i))
			else:
				done.add((x, i))
		while q and q[0] in done:
			done.remove(heapq.heappop(q))
		if q:
			ans[j] = q[0][0]
	for i in range(Q):
		print(ans[i])

def main():
	(N, Q) = read_int_n()
	STX = list((read_int_n() for _ in range(N)))
	D = list((read_int() for _ in range(Q)))
	slv(N, Q, STX, D)

def __starting_point():
	main()
__starting_point()


def main():
	from collections import deque, namedtuple
	from heapq import heappush, heappop
	from operator import attrgetter
	import sys
	input = sys.stdin.readline
	Event = namedtuple('Event', 'pos start end')
	UC = namedtuple('UC', 'pos end')
	(N, Q) = map(int, input().split())
	events = []
	for _ in range(N):
		(s, t, x) = map(int, input().split())
		e = Event(pos=x, start=s - x, end=t - x)
		events.append(e)
	events.sort(key=attrgetter('start'))
	events = deque(events)
	D = (int(input()) for _ in range(Q))
	ans = [-1] * Q
	h = []
	for (idx, d) in enumerate(D):
		while events and events[0].start <= d:
			e = events.popleft()
			heappush(h, UC(pos=e.pos, end=e.end))
		while h and h[0].end <= d:
			heappop(h)
		if h:
			ans[idx] = h[0].pos
	print(*ans, sep='\n')

def __starting_point():
	main()
__starting_point()


import sys
input = sys.stdin.readline
from heapq import *
(N, Q) = map(int, input().split())
X = []
for _ in range(N):
	(s, t, x) = map(int, input().split())
	X.append((s - x, t - x, x))
X = sorted(X, key=lambda x: x[0])
D = [int(input()) for _ in range(Q)]
i = 0
j = 0
A = []
B = []
C = []
for q in range(Q):
	while i < len(X) and D[q] >= X[i][0]:
		(a, b, x) = X[i]
		heappush(A, (x, b))
		heappush(B, (b, x))
		i += 1
	while len(B) and B[0][0] <= D[q]:
		(b, x) = heappop(B)
		heappush(C, (x, b))
	while len(C) and len(A) and (C[0][0] == A[0][0]):
		heappop(A)
		heappop(C)
	print(A[0][0] if A else -1)


import sys
from collections import deque, defaultdict
import copy
import bisect
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
(N, Q) = list(map(int, input().split()))
STX = []
D = []
for i in range(N):
	(S, T, X) = list(map(int, input().split()))
	STX.append((X, S, T))
STX = sorted(STX, key=lambda x: x[0])
for i in range(Q):
	D.append(int(input()))
skip = [-1] * Q
dist = [-1] * Q
for (X, S, T) in STX:
	s = S - X
	t = T - X - 1
	a = bisect.bisect_left(D, s)
	b = bisect.bisect_right(D, t)
	j = a
	while j < b:
		if skip[j] == -1:
			skip[j] = b
			dist[j] = X
			j += 1
		else:
			j = skip[j]
for i in range(Q):
	print(dist[i])


import bisect
(N, Q) = map(int, input().split())
road = []
pos = []
for _ in range(N):
	(s, t, x) = map(int, input().split())
	road.append((s - x, t - x, x))
for _ in range(Q):
	pos.append(int(input()))
road.sort(key=lambda x: x[2])
ans = [-1] * Q
ischecked = [-1] * Q
for (s, t, x) in road:
	l = bisect.bisect_left(pos, s)
	r = bisect.bisect_left(pos, t)
	while l < r:
		if ischecked[l] == -1:
			ischecked[l] = r
			ans[l] = x
			l += 1
		else:
			l = ischecked[l]
for i in range(Q):
	print(ans[i])


import sys
input = sys.stdin.readline

def main():
	(n, q) = map(int, input().split())
	V = []
	for i in range(n):
		(s, t, x) = map(int, input().split())
		V.append((s - x, x, 1))
		V.append((t - x, x, 0))
	D = []
	for i in range(q):
		d = int(input())
		V.append((d, i, 2))
	V.sort(key=lambda x: (x[0], x[2]))
	se = set()
	hq = []
	import heapq
	heapq.heapify(hq)
	ans = [-1] * q
	for (t, v, p) in V:
		if p == 1:
			se.add(v)
			heapq.heappush(hq, v)
		elif p == 0:
			se.remove(v)
		else:
			while hq and hq[0] not in se:
				heapq.heappop(hq)
			if hq:
				ans[v] = hq[0]
	for i in range(q):
		print(ans[i])
main()


import sys
(n, q) = map(int, input().split())
lines = sys.stdin.readlines()
coordinates = set()
kkk = []
for line in lines[:n]:
	(s, t, x) = map(int, line.split())
	sx = s - x
	tx = t - x
	kkk.append((x, sx, tx))
	coordinates.add(sx)
	coordinates.add(tx)
kkk.sort()
ddd = list(map(int, lines[n:]))
coordinates.update(ddd)
coordinates = {d: i for (i, d) in enumerate(sorted(coordinates))}
coord_len = len(coordinates)
ans = [-1] * coord_len
skip = [-1] * coord_len
for (x, sx, tx) in kkk:
	ss = coordinates[sx]
	tt = coordinates[tx]
	while ss < tt:
		sk = skip[ss]
		if sk == -1:
			ans[ss] = x
			skip[ss] = tt
			ss += 1
		else:
			ss = sk
print('\n'.join(map(str, map(ans.__getitem__, map(coordinates.get, ddd)))))


from heapq import heappush, heappop
(N, Q, *L) = map(int, open(0).read().split())
D = L[3 * N:]
ls = []
for i in range(N):
	(s, t, x) = (L[3 * i], L[3 * i + 1], L[3 * i + 2])
	ls.append((s - x, 1, x))
	ls.append((t - x, 0, x))
for (i, d) in enumerate(D):
	ls.append((d, 2, i))
ls.sort()
ans = [0] * Q
S = set()
hq = []
for (a, b, c) in ls:
	if b == 0:
		S.remove(c)
	elif b == 1:
		S.add(c)
		heappush(hq, c)
	else:
		while hq and hq[0] not in S:
			heappop(hq)
		ans[c] = hq[0] if hq else -1
print('\n'.join(map(str, ans)))


from bisect import bisect_left
(N, Q) = map(int, input().split())
STX = []
D = []
for _ in range(N):
	STX.append(list(map(int, input().split())))
for _ in range(Q):
	D.append(int(input()))
STX.sort(key=lambda x: x[2])
ans = [-1] * Q
skip = [-1] * Q
for (s, t, x) in STX:
	left = bisect_left(D, s - x)
	right = bisect_left(D, t - x)
	while left < right:
		if skip[left] == -1:
			ans[left] = x
			skip[left] = right
			left += 1
		else:
			left = skip[left]
for a in ans:
	print(a)


from heapq import heappush, heappop
import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
E = []
for i in range(N):
	(s, t, x) = map(int, input().split())
	E.append((s - x, t - x, x))
D = []
for i in range(Q):
	d = int(input())
	D.append(d)
E = sorted(E)
que = []
(s, t, x) = E[0]
j = 1
(y, e) = (N, N)
ans = [-1] * Q
for (i, d) in enumerate(D):
	while j < N + 1 and s <= d:
		heappush(que, (x, t))
		(y, e) = que[0]
		if j < N:
			(s, t, x) = E[j]
		j += 1
	while que and e <= d:
		heappop(que)
		if que:
			(y, e) = que[0]
	if que:
		ans[i] = y
for i in ans:
	print(i)


from bisect import bisect_left
(N, Q) = map(int, input().split())
R = [tuple(map(int, input().split())) for i in range(N)]
R.sort(key=lambda r: r[2])
q = [int(input()) for _ in range(Q)]
ans = [-1] * Q
skip = [-1] * (Q + 1)
for (s, t, x) in R:
	l = bisect_left(q, s - x)
	r = bisect_left(q, t - x)
	while l < r:
		if skip[l] == -1:
			skip[l] = r
			ans[l] = x
			l += 1
		else:
			l = skip[l]
for i in range(Q):
	print(ans[i])


import bisect
import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
STX = [tuple(map(int, input().split())) for i in range(N)]
STX.sort(key=lambda x: x[2])
ans = [-1] * Q
jump = [-1] * Q
D = [int(input()) for i in range(Q)]
for (s, t, x) in STX:
	l = bisect.bisect_left(D, s - x)
	r = bisect.bisect_left(D, t - x)
	while l < r:
		k = jump[l]
		if k == -1:
			ans[l] = x
			jump[l] = r
			l += 1
		else:
			l = k
for i in range(Q):
	print(ans[i])


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
stx = [list(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]
stx = sorted(stx, key=lambda x: x[2])
ans = [-1 for _ in range(q)]
skip = [-1 for _ in range(q)]
from bisect import bisect_left
for (s, t, x) in stx:
	left = bisect_left(d, s - x)
	right = bisect_left(d, t - x)
	while left < right:
		if skip[left] == -1:
			ans[left] = x
			skip[left] = right
			left += 1
		else:
			left = skip[left]
print('\n'.join(map(str, ans)))


from bisect import bisect_left
(n, q) = map(int, input().split())
work = [list(map(int, input().split())) for _ in range(n)]
work = sorted(work, key=lambda x: x[2])
pos = [int(input()) for _ in range(q)]
ans = [-1] * q
checked = [-1] * q
for (s, t, x) in work:
	l = bisect_left(pos, s - x)
	r = bisect_left(pos, t - x)
	while l < r:
		if checked[l] == -1:
			checked[l] = r
			ans[l] = x
			l += 1
		else:
			l = checked[l]
for i in ans:
	print(i)


import sys
from heapq import heapify, heappop, heappush
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
(N, Q) = lr()
STX = [tuple(lr()) for _ in range(N)]
event = []
for (s, t, x) in STX:
	event.append((s - x, 0, x))
	event.append((t - x, -1, x))
for i in range(Q):
	d = ir()
	event.append((d, 1, i))
event.sort()
answer = [-1] * Q
cur = set()
flag = False
INF = 10 ** 10
min_x = INF
for (a, b, c) in event:
	if b == 0:
		cur.add(c)
		if c < min_x:
			min_x = c
			flag = True
	elif b == -1:
		cur.remove(c)
		if min_x == c:
			flag = False
	elif b == 1:
		if cur:
			if not flag:
				min_x = min(cur)
				flag = True
			answer[c] = min_x
print('\n'.join(map(str, answer)))


from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline

def main():
	(N, Q) = map(int, input().split())
	constructions = [None] * N
	for i in range(N):
		(S, T, X) = map(int, input().split())
		constructions[i] = (S, T, X)
	constructions.sort(key=itemgetter(2))
	D = [int(input()) for _ in range(Q)]
	ans = [-1] * Q
	nxt = list(range(1, Q + 1))
	for (S, T, X) in constructions:
		l = bisect_left(D, S - X)
		r = bisect_right(D, T - X - 1)
		idx = l
		while idx < r:
			if ans[idx] == -1:
				ans[idx] = X
			nidx = nxt[idx]
			nxt[idx] = max(nxt[idx], r)
			idx = nidx
	for a in ans:
		print(a)
main()


from bisect import bisect_left

def solve(n, q, s, t, x, d):
	v = sorted(list(zip(s, t, x)), key=lambda _: _[2])
	res = [-1] * q
	jump = [-1] * q
	for (s, t, x) in v:
		l = bisect_left(d, s - x)
		r = bisect_left(d, t - x)
		while l < r:
			s = jump[l]
			if s == -1:
				res[l] = x
				jump[l] = r
				l += 1
			else:
				l = s
	return res
(n, q) = map(int, input().split())
s = [-1] * n
t = [-1] * n
x = [-1] * n
for i in range(n):
	(s[i], t[i], x[i]) = map(int, input().split())
d = [int(input()) for i in range(q)]
print(*solve(n, q, s, t, x, d), sep='\n')


import sys
from heapq import heappush, heappop
from collections import defaultdict
input = sys.stdin.readline
(num, person) = map(int, input().split())
arr = []
for i in range(num):
	(s, t, x) = map(int, input().split())
	arr.append((s - x - 0.5, 1, x, i))
	arr.append((t - x - 0.5, -1, x, i))
for i in range(person):
	d = int(input())
	arr.append((d,))
arr.sort()
heap = []
done = set()
for elem in arr:
	if len(elem) == 1:
		d = elem[0]
		while heap and heap[0][1] in done:
			heappop(heap)
		if heap:
			print(heap[0][0])
		else:
			print(-1)
		continue
	(time, kind, x, i) = elem
	if kind == 1:
		heappush(heap, (x, i))
	elif kind == -1:
		done.add(i)


import bisect as bs
(N, Q) = map(int, input().split())
E = []
for i in range(N):
	(s, t, x) = map(int, input().split())
	a = [s - x, t - x, x]
	E.append(a)
E.sort(key=lambda x: x[2])
D = []
for i in range(Q):
	D.append(int(input()))
ans = [-1] * Q
check = [-1] * Q
for e in E:
	l = bs.bisect_left(D, e[0])
	r = bs.bisect_left(D, e[1])
	while l < r:
		if check[l] == -1:
			ans[l] = e[2]
			check[l] = r
			l += 1
		else:
			l = check[l]
[print(i) for i in ans]


from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline

def solve():
	(N, Q) = list(map(int, input().split()))
	events = []
	for i in range(N):
		(S, T, X) = list(map(int, input().split()))
		events.append((S - X - 0.5, 1, X))
		events.append((T - X - 0.5, 0, X))
	for i in range(Q):
		D = int(input())
		events.append((D, 2, i))
	events.sort()
	anss = [-1] * Q
	PQ = []
	isClosed = dict()
	for (tm, tp, x) in events:
		if tp == 0:
			isClosed[x] = 0
		elif tp == 1:
			isClosed[x] = 1
			heappush(PQ, x)
		else:
			while PQ:
				if isClosed[PQ[0]] == 1:
					anss[x] = PQ[0]
					break
				heappop(PQ)
	print('\n'.join(map(str, anss)))
solve()


(N, Q) = map(int, input().split())
work = []
for i in range(N):
	(start, end, pos) = map(int, input().split())
	work.append((start - pos - 0.5, end - pos - 0.5, pos))
work.sort(key=lambda x: x[0])
depart_time = [int(input()) for _ in range(Q)]
heap = []
end_time = {}
import heapq
i = 0
for depart in depart_time:
	while i < len(work) and work[i][0] < depart:
		(start, end, pos) = work[i]
		heapq.heappush(heap, pos)
		end_time[pos] = end
		i += 1
	while heap and end_time[heap[0]] < depart:
		heapq.heappop(heap)
	if heap:
		print(heap[0])
	else:
		print(-1)


import sys
input = sys.stdin.buffer.readline
import heapq

def main():
	(N, Q) = map(int, input().split())
	event = []
	for _ in range(N):
		(s, t, x) = map(int, input().split())
		event.append((s - x, 1, x))
		event.append((t - x, 0, x))
	for i in range(Q):
		a = int(input())
		event.append((a, 2, i))
	event.sort()
	ans = [-1] * Q
	use = set()
	stop = []
	for (a, b, c) in event:
		if b == 1:
			use.add(c)
			heapq.heappush(stop, c)
		elif b == 0:
			use.remove(c)
		else:
			while stop and stop[0] not in use:
				heapq.heappop(stop)
			ans[c] = -1 if len(stop) == 0 else stop[0]
	for num in ans:
		print(num)
main()


from bisect import bisect_left
import heapq
(n, q) = map(int, input().split())
stx = [tuple(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]
events = []
for (s, t, x) in stx:
	events.append((s - x, 1, x))
	events.append((t - x, -1, x))
events.sort(key=lambda x: x[0])
hp = []
st = set()
res = [-1] * q
now = 0
for (t, b, x) in events:
	while now < q and d[now] < t:
		if len(st) > 0:
			while hp[0] not in st:
				heapq.heappop(hp)
			res[now] = hp[0]
		now += 1
	if b == 1:
		heapq.heappush(hp, x)
		st.add(x)
	else:
		st.discard(x)
print(*res)


import heapq

class HeapDict:

	def __init__(self):
		self.h = []
		self.d = {}

	def insert(self, x):
		if x not in self.d or self.d[x] == 0:
			heapq.heappush(self.h, x)
		self.d.setdefault(x, 0)
		self.d[x] += 1

	def erase(self, x):
		if x not in self.d or self.d[x] == 0:
			return
		else:
			self.d[x] -= 1
		while self.h:
			if self.d[self.h[0]] == 0:
				heapq.heappop(self.h)
			else:
				break

	def get_min(self):
		if not self.h:
			return None
		else:
			return self.h[0]

	def pop(self):
		poped_val = self.h[0]
		self.erase(poped_val)
		return poped_val

	def exist(self, x):
		return x in self.d and self.d[x] > 0

	def show_h(self):
		elems = [v for v in self.h if self.d[v] > 0]
		print(elems)

	def show_d(self):
		print(self.d)

def main():
	(n, q) = map(int, input().split())
	eventl = []
	for _ in range(n):
		(s, t, x) = map(int, input().split())
		eventl.append((s - x, 'a-stop', x))
		eventl.append((t - x, 'b-start', x))
	for i in range(q):
		d = int(input())
		eventl.append((d, 'c-go', i))
	eventl.sort()
	ans = [0] * q
	hd = HeapDict()
	for e in eventl:
		if e[1] == 'a-stop':
			hd.insert(e[2])
		elif e[1] == 'b-start':
			hd.erase(e[2])
		else:
			min_x = hd.get_min()
			if min_x is not None:
				ans[e[2]] = min_x
			else:
				ans[e[2]] = -1
	for a in ans:
		print(a)

def __starting_point():
	main()
__starting_point()


import bisect
import heapq
import sys
(N, Q) = [int(x) for x in sys.stdin.readline().split()]
hitos = []
ans = [-1 for _ in range(Q)]
queries = []
jump = ans[:]
queries = [[int(x) for x in sys.stdin.readline().split()] for i in range(N)]
hitos = [int(sys.stdin.readline()) for i in range(Q)]
queries.sort(key=lambda x: x[2])
for (l, r, x) in queries:
	lind = bisect.bisect_left(hitos, l - x - 0.5)
	rind = bisect.bisect_left(hitos, r - x - 0.5)
	while lind < rind:
		if ans[lind] == -1:
			ans[lind] = x
			jump[lind] = rind
			lind += 1
		else:
			lind = jump[lind]
for i in ans:
	print(i)


from heapq import heappush, heappop
(n, q) = map(int, input().split())
events = []
for i in range(n):
	(s, t, x) = map(int, input().split())
	if t >= x:
		events.append([t - x, 0, x])
		events.append([s - x, 1, x])
for i in range(q):
	d = int(input())
	events.append([d, 2, i])
events.sort()
dist = [-1] * q
walker = []
working = set()
heap = []
for (t, kind, x) in events:
	if kind == 0:
		working.remove(x)
	elif kind == 1:
		working.add(x)
		heappush(heap, x)
	elif working:
		while not heap[0] in working:
			heappop(heap)
		dist[x] = heap[0]
print(*dist, sep='\n')


import heapq, sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
event = []
for _ in range(n):
	(s, t, x) = map(int, input().split())
	event.append((s - x, 1, x))
	event.append((t - x, -1, x))
for _ in range(q):
	d = int(input())
	event.append((d, 2, 0))
event.sort(key=lambda x: (x[0], x[1]))
now = []
memo = set()
tmp = 0
for (i, (t, flg, x)) in enumerate(event):
	if flg == -1:
		memo.remove(x)
	elif flg == 1:
		heapq.heappush(now, x)
		memo.add(x)
	else:
		while len(now) > 0 and now[0] not in memo:
			heapq.heappop(now)
		if len(now) > 0:
			print(now[0])
		else:
			print(-1)


from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
events = []
for iR in range(N):
	(S, T, X) = map(int, input().split())
	events.append((S - X, T - X, X))
events.sort()
iE = 0
anss = []
PQ = []
for _ in range(Q):
	D = int(input())
	while iE < N and events[iE][0] <= D:
		(tmSt, tmEn, x) = events[iE]
		heappush(PQ, (x, tmEn))
		iE += 1
	xMin = -1
	while PQ:
		(x, tmEn) = heappop(PQ)
		if tmEn > D:
			xMin = x
			heappush(PQ, (x, tmEn))
			break
	anss.append(xMin)
print('\n'.join(map(str, anss)))


from bisect import bisect_left
from operator import itemgetter
(n, q) = map(int, input().split())
stx = [tuple((int(x) for x in input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]
ans = [-1] * q
skip = [-1] * q
stx.sort(key=itemgetter(2))
for (s, t, x) in stx:
	L = bisect_left(d, s - x)
	R = bisect_left(d, t - x)
	while L < R:
		if skip[L] == -1:
			ans[L] = x
			skip[L] = R
			L += 1
		else:
			L = skip[L]
for x in ans:
	print(x)


from bisect import bisect_left
from operator import itemgetter

def main():
	(N, Q, *STXD) = map(int, open(0).read().split())
	(STX, D) = (sorted(zip(*[iter(STXD[:3 * N])] * 3), key=itemgetter(2)), STXD[3 * N:])
	ans = [-1] * Q
	road = [-1] * Q
	for (s, t, x) in STX:
		(l, r) = (bisect_left(D, s - x), bisect_left(D, t - x))
		while l < r:
			if road[l] == -1:
				ans[l] = x
				road[l] = r
				l += 1
			else:
				l = road[l]
	print('\n'.join(map(str, ans)))
main()


def main():
	import sys
	input = sys.stdin.readline
	from bisect import bisect_left
	(N, Q) = map(int, input().split())
	c = []
	c_append = c.append
	for _ in range(N):
		(s, t, x) = map(int, input().split())
		c_append((x, s, t))
	c.sort()
	D = [int(input()) for _ in range(Q)]
	ans = [-1] * Q
	skip = [-1] * Q
	for (x, s, t) in c:
		left = bisect_left(D, s - x)
		right = bisect_left(D, t - x)
		while left < right:
			if skip[left] == -1:
				ans[left] = x
				skip[left] = right
				left += 1
			else:
				left = skip[left]
	print('\n'.join(map(str, ans)))
main()


import heapq
import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
H = []
for i in range(N):
	(s, t, x) = map(int, input().split())
	H.append([s - x, t - x, x])
H.sort()
P = 0
q = []
heapq.heapify(q)
for i in range(Q):
	n = int(input())
	if P < N:
		while H[P][0] <= n:
			heapq.heappush(q, [H[P][2], H[P][0], H[P][1]])
			P += 1
			if P == N:
				break
	if len(q) > 0:
		while q[0][2] <= n:
			heapq.heappop(q)
			if len(q) == 0:
				break
	if len(q) == 0:
		print(-1)
	else:
		print(q[0][0])


from bisect import bisect_left

def main():
	(ConstNum, PersonNum) = map(int, input().split())
	S = []
	T = []
	X = []
	for i in range(ConstNum):
		(s, t, x) = map(int, input().split())
		S.append(s)
		T.append(t)
		X.append(x)
	DepartureTime = []
	for i in range(PersonNum):
		d = int(input())
		DepartureTime.append(d)
	XST = zip(X, S, T)
	XST = sorted(XST)
	res = [-1] * PersonNum
	stop = [-1] * PersonNum
	for (x, s, t) in XST:
		left_value = s - x
		right_value = t - x
		left_index = bisect_left(DepartureTime, left_value)
		right_index = bisect_left(DepartureTime, right_value)
		while left_index < right_index:
			if stop[left_index] == -1:
				res[left_index] = x
				stop[left_index] = right_index
				left_index += 1
			else:
				left_index = stop[left_index]
	for i in range(PersonNum):
		print(res[i])

def __starting_point():
	main()
__starting_point()


def main():
	import sys
	input = sys.stdin.readline
	sys.setrecursionlimit(10 ** 7)
	from collections import Counter, deque
	from itertools import combinations, permutations, accumulate, groupby, product
	from bisect import bisect_left, bisect_right
	from heapq import heapify, heappop, heappush
	import math
	(n, q) = map(int, input().split())
	l = []
	for _ in range(n):
		(s, t, x) = map(int, input().split())
		l.append((s, t, x))
	l.sort(key=lambda a: a[2])
	start = [int(input()) for _ in range(q)]
	skip = [-1] * q
	res = [-1] * q
	for (s, t, x) in l:
		left = bisect_left(start, s - x)
		right = bisect_left(start, t - x)
		while left < right:
			if skip[left] == -1:
				res[left] = x
				skip[left] = right
				left += 1
			else:
				left = skip[left]
	for i in res:
		print(i)

def __starting_point():
	main()
__starting_point()


from bisect import bisect_left as bisect
(N, Q) = map(int, input().split())
event = [tuple(map(int, input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]
event.sort(key=lambda x: x[2])
ans = [-1] * Q
neg = [-1] * Q
for (s, t, x) in event:
	l = bisect(D, s - x)
	r = bisect(D, t - x)
	t = l
	while t < r:
		if neg[t] == -1:
			ans[t] = x
			neg[t] = r
			t += 1
		else:
			t = neg[t]
for i in range(Q):
	print(ans[i])


import re
import math
import fractions
import random
from heapq import heappop, heappush
import time
import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
E = []
for a in range(N):
	(s, t, x) = map(int, input().split())
	E.append((s - x, 1, x))
	E.append((t - x, 0, x))
for a in range(Q):
	E.append((int(input()), 2, 0))
E.sort()
S = set()
H = []
for (time_, type_, x) in E:
	if type_ & 1:
		S.add(x)
		heappush(H, x)
	elif not type_:
		S.remove(x)
	else:
		while H and H[0] not in S:
			heappop(H)
		print(H[0] if H else -1)


import sys
input = sys.stdin.readline
(n, q) = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(n)]
D = [int(input()) for i in range(q)]
E = []
F = {}
for i in range(n):
	s = A[i][0]
	t = A[i][1]
	x = A[i][2]
	F[x] = 0
	E.append((s - x, x, 1))
	E.append((t - x, x, -1))
E.append((10 ** 10, 10 ** 10, 1))
E.sort()
from heapq import heappush, heappop
Q = []
j = 0
for i in range(q):
	while E[j][0] <= D[i]:
		if E[j][2] == 1:
			F[E[j][1]] += 1
			heappush(Q, E[j][1])
		else:
			F[E[j][1]] -= 1
		j += 1
	while len(Q) > 0 and F[Q[0]] == 0:
		_ = heappop(Q)
	if len(Q) == 0:
		print(-1)
	else:
		print(Q[0])


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
S = [list(map(int, input().split())) for i in range(n)]
D = [int(input()) for i in range(q)]
A = []
for i in range(n):
	s = S[i][0]
	t = S[i][1]
	x = S[i][2]
	A.append([s - x - 0.5, x, i, 0])
	A.append([t - x - 0.5, x, i, 1])
for i in range(q):
	A.append([D[i], 0, 0, 2])
A.sort()
from heapq import heappop, heappush
Q = []
F = [0] * n
for i in range(len(A)):
	s = A[i][0]
	x = A[i][1]
	j = A[i][2]
	f = A[i][3]
	if f == 0:
		heappush(Q, [x, j])
		F[j] = 1
	elif f == 1:
		F[j] = 0
	elif f == 2:
		while len(Q) > 0 and F[Q[0][1]] == 0:
			heappop(Q)
		if len(Q) > 0:
			print(Q[0][0])
		else:
			print(-1)


import heapq

def main():
	(N, Q) = map(int, input().split())
	l = []
	for _ in range(N):
		(s, t, x) = map(int, input().split())
		l.append((s - x, 1, x))
		l.append((t - x, 0, x))
	for i in range(Q):
		d = int(input())
		l.append((d, 2, i))
	r = [-1] * Q
	l.sort()
	h = []
	se = set()
	for (a, b, c) in l:
		if b == 0:
			se.remove(c)
		elif b == 1:
			se.add(c)
			heapq.heappush(h, c)
		else:
			while h and h[0] not in se:
				heapq.heappop(h)
			r[c] = h[0] if h else -1
	print('\n'.join(map(str, r)))
main()


import sys
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush
(N, Q) = map(int, input().split())
INF = float('inf')
events = []
for i in range(N):
	(S, T, X) = map(int, input().split())
	events.append((S - X, 0, X))
	events.append((T - X, 1, X))
for _ in range(Q):
	events.append((int(input()), 2, 0))
events.sort()
cnt = defaultdict(int)
cnt[INF] += 1
que = [INF]
for (t, flag, x) in events:
	if flag == 0:
		if cnt[x] == 0:
			heappush(que, x)
		cnt[x] += 1
	elif flag == 1:
		cnt[x] -= 1
	else:
		while cnt[que[0]] == 0:
			heappop(que)
		print(que[0] if que[0] != INF else -1)


import sys
from bisect import bisect_left
input = sys.stdin.readline
(n, q) = map(int, input().split())
stx = [tuple(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]
stx.sort(key=lambda x: x[2])
ans = [-1] * q
jump = [-1] * q
for (s, t, x) in stx:
	d_start = bisect_left(d, s - x)
	d_stop = bisect_left(d, t - x, lo=d_start)
	while d_start < d_stop:
		if jump[d_start] == -1:
			ans[d_start] = x
			jump[d_start] = d_stop
			d_start += 1
		else:
			d_start = jump[d_start]
for an in ans:
	print(an)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
import time, random
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
mod2 = 998244353
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

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

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

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 pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def main():
	(n, q) = LI()
	stx = [LI() for _ in range(n)]
	da = [I() for _ in range(q)]
	q = []
	for (s, t, x) in stx:
		sx = s - x
		tx = t - x - 1
		heapq.heappush(q, (sx, x, tx))
	t = []
	cx = inf
	ctx = inf
	c = 0
	while len(q):
		(sx, x, tx) = heapq.heappop(q)
		if sx > ctx:
			t.append((sx - 1, cx))
			cx = x
			ctx = tx
		elif cx > x:
			if ctx > tx:
				heapq.heappush(q, (tx + 1, cx, ctx))
			t.append((sx - 1, cx))
			cx = x
			ctx = tx
		elif tx > ctx:
			heapq.heappush(q, (ctx + 1, x, tx))
	t.append((inf, inf))
	r = []
	for d in da:
		i = bisect.bisect_right(t, (d, -1))
		u = t[i][1]
		if u == inf:
			r.append(-1)
		else:
			r.append(u)
	return JA(r, '\n')
print(main())


import sys
input = sys.stdin.readline

def N():
	return int(input())

def NM():
	return map(int, input().split())

def L():
	return list(NM())

def LN(n):
	return [N() for i in range(n)]

def LL(n):
	return [L() for i in range(n)]

def YesNo(x):
	print('Yes') if x == True else print('No')
(n, q) = NM()
l = []
for i in range(n):
	(s, t, x) = NM()
	l.append((s - x, t - x, x))
l.sort()
INF = float('inf')
l += [(INF, INF, INF)]
d = LN(q)
q = []
from heapq import heappush, heappop
j = 0
for i in d:
	while l[j][0] <= i:
		(s, t, x) = l[j]
		heappush(q, (x, t))
		j += 1
	if len(q) == 0:
		print(-1)
	else:
		while q:
			(x, t) = heappop(q)
			if t > i:
				heappush(q, (x, t))
				print(x)
				break
		else:
			print(-1)


from bisect import bisect_left

def main():
	(N, Q) = map(int, input().split())
	W = [tuple(map(int, input().split())) for _ in range(N)]
	W.sort(key=lambda x: x[2])
	D = [int(input()) for _ in range(Q)]
	ans = [-1] * Q
	skip = [-1] * Q
	for (s, t, x) in W:
		l = bisect_left(D, s - x)
		r = bisect_left(D, t - x)
		while l < r:
			if skip[l] == -1:
				ans[l] = x
				skip[l] = r
				l += 1
			else:
				l = skip[l]
	for a in ans:
		print(a)
main()


import bisect
(n, q) = map(int, input().split())
STX = []
for i in range(n):
	(s, t, x) = map(int, input().split())
	STX.append((s, t, x))
STX.sort(key=lambda _: _[2])
(S, T, X) = ([], [], [])
for stx in STX:
	(s, t, x) = stx
	S.append(s)
	T.append(t)
	X.append(x)
D = [int(input()) for j in range(q)]
A = [-1 for j in range(q)]
B = [-1 for j in range(q)]
for i in range(n):
	l = bisect.bisect_left(D, S[i] - X[i])
	r = bisect.bisect_left(D, T[i] - X[i])
	while l < r:
		if B[l] == -1:
			A[l] = X[i]
			B[l] = r
			l += 1
		else:
			l = B[l]
print(*A, sep='\n')


import bisect
(n, q) = list(map(int, input().split()))
list_xst = []
for _ in range(n):
	(s, t, x) = list(map(int, input().split()))
	list_xst.append([x, s - x, t - x])
list_xst.sort(key=lambda l: l[0])
list_d = [int(input()) for _ in range(q)]
retn = [-1] * q
jmp = [-1] * q
for (x, s, t) in list_xst:
	i = bisect.bisect_left(list_d, s)
	tt = bisect.bisect_left(list_d, t)
	while i < tt:
		if jmp[i] != -1:
			i = jmp[i]
		else:
			retn[i] = x
			jmp[i] = tt
			i += 1
print(*retn, sep='\n')


import sys
from operator import itemgetter
from heapq import heapify, heappush, heappop
read = sys.stdin.read
(N, Q, *STXD) = list(map(int, read().split()))
STX = STXD[:3 * N]
queue = []
for (i, (S, T, X)) in enumerate(zip(*[iter(STX)] * 3), 1):
	queue.append((S - X - 0.5, X, i))
	queue.append((T - X - 0.5, -X, i))
for D in STXD[3 * N:]:
	queue.append((D, 0, 0))
queue.sort(key=itemgetter(0), reverse=True)
heap = []
heapify(heap)
(stop, construction) = (-1, 0)
not_available = set()
while queue:
	(_, x, n) = queue.pop()
	if x == 0:
		print(stop)
	elif x < 0:
		not_available.add(n)
		if n == construction:
			while heap:
				(stop, construction) = heappop(heap)
				if construction not in not_available:
					break
			else:
				(stop, construction) = (-1, 0)
	elif stop != -1:
		if stop <= x:
			heappush(heap, (x, n))
		else:
			heappush(heap, (stop, construction))
			(stop, construction) = (x, n)
	else:
		(stop, construction) = (x, n)


import sys
input = sys.stdin.readline
from bisect import bisect_left
(n, q) = map(int, input().split())
road = [list(map(int, input().split())) for i in range(n)]
road.sort(key=lambda x: x[2])
start = [int(input()) for i in range(q)]
skip = [-1] * q
ans = [-1] * q
for (s, t, x) in road:
	left = bisect_left(start, s - x)
	right = bisect_left(start, t - x)
	while left < right:
		if skip[left] == -1:
			ans[left] = x
			skip[left] = right
			left += 1
		else:
			left = skip[left]
print(*ans, sep='\n')


(n, q) = [int(j) for j in input().split()]
l = []
for i in range(n):
	(s, t, x) = [int(j) for j in input().split()]
	l.append((s - x, 1, x))
	l.append((t - x, 0, x))
for i in range(q):
	d = int(input())
	l.append((d, 2, i))
l.sort()
ans = [-1] * q
ll = set()
m = 10 ** 18
p = False
for (i, j, x) in l:
	if j == 1:
		ll.add(x)
		if m > x:
			m = x
			p = True
	elif j == 0:
		ll.remove(x)
		if x == m:
			p = False
	else:
		if not p:
			if ll:
				p = True
				m = min(ll)
			else:
				m = -1
		ans[x] = m
print('\n'.join(map(str, ans)))


import heapq as hq
import sys
stdin = sys.stdin
ns = lambda : stdin.readline().rstrip()
ni = lambda : int(stdin.readline().rstrip())
nm = lambda : map(int, stdin.readline().split())
nl = lambda : list(map(int, stdin.readline().split()))

def main():
	(n, q) = nm()
	tl = []
	ins = list()
	dlt = list()
	vv = [tuple(nm()) for _ in range(n)]
	tl = [(s - x, 1, x) for (s, _, x) in vv]
	tl.extend([(t - x, 0, x) for (_, t, x) in vv])
	ww = [ni() for _ in range(q)]
	tl.extend([(t, 2) for t in ww])
	tl.sort()
	for x in tl:
		if x[1] == 1:
			hq.heappush(ins, x[2])
		elif x[1] == 0:
			hq.heappush(dlt, x[2])
			while dlt and ins[0] == dlt[0]:
				hq.heappop(ins)
				hq.heappop(dlt)
		else:
			print(-1 if not ins else ins[0])

def __starting_point():
	main()
__starting_point()


import sys
from heapq import heappush, heappop
(n, q) = map(int, input().split())
a = sorted(((s - x, t - x, x) for _ in range(n) for (s, t, x) in (map(int, sys.stdin.readline().split()),)), reverse=True)
heap = []
ans = []
for i in range(q):
	d = int(input())
	while a and a[-1][0] <= d:
		e = a.pop()
		heappush(heap, (e[2], e[1]))
	while heap and heap[0][1] <= d:
		heappop(heap)
	if heap:
		ans.append(heap[0][0])
	else:
		ans.append(-1)
print(*ans, sep='\n')


import bisect
(N, Q) = (int(x) for x in input().split())
stop_arr = [tuple(map(int, input().split())) for _ in range(N)]
Q_arr = [int(input()) for _ in range(Q)]
stop_arr.sort(key=lambda x: x[2])
ans_arr = [-1] * Q
skip_arr = [-1] * (Q + 1)
for (s, t, x) in stop_arr:
	q_start = bisect.bisect_left(Q_arr, s - x)
	q_stop = bisect.bisect_left(Q_arr, t - x)
	l = q_start
	while l < q_stop:
		if skip_arr[l] == -1:
			skip_arr[l] = q_stop
			ans_arr[l] = x
			l += 1
		else:
			l = skip_arr[l]
print(*ans_arr, sep='\n')


from operator import itemgetter
from bisect import bisect_left

def main():
	(n, q) = list(map(int, input().split()))
	stops = []
	for _ in range(n):
		(s, t, x) = list(map(int, input().split()))
		stops.append((s, t, x))
	delay = []
	for i in range(q):
		delay.append(int(input()))
	stops = sorted(stops, key=itemgetter(2))
	delay = sorted(delay)
	result = [-1] * q
	skips = [-1] * q
	for (s, t, x) in stops:
		sx = bisect_left(delay, s - x)
		tx = bisect_left(delay, t - x)
		while sx < tx:
			if skips[sx] == -1:
				result[sx] = x
				skips[sx] = tx
				sx += 1
			else:
				sx = skips[sx]
	for r in result:
		print(r)
main()


from heapq import heappush, heappop
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
(n, q) = map(int, readline().split())
stx = [[int(x) for x in readline().split()] for _ in range(n)]
event = []
for (s, t, x) in stx:
	event.append((s - x, 1, x))
	event.append((t - x, -1, x))
for i in range(q):
	event.append((int(readline()), 2, i))
event.sort()
ans = [0] * q
stop = set()
hq = []
for (t, op, x) in event:
	if op == 1:
		heappush(hq, x)
		stop.add(x)
	elif op == -1:
		stop.remove(x)
	else:
		while hq and hq[0] not in stop:
			heappop(hq)
		ans[x] = hq[0] if hq else -1
for x in ans:
	print(x)


import bisect
import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
(S, T, X) = ([0] * N, [0] * N, [0] * N)
work = []
for i in range(N):
	(S[i], T[i], X[i]) = map(int, input().split())
	work.append((X[i], S[i] - X[i], T[i] - X[i]))
D = [int(input()) for _ in range(Q)]
work.sort()
ans = [-1] * Q
skip = [-1] * Q
for i in range(N):
	left = bisect.bisect_left(D, work[i][1])
	right = bisect.bisect_left(D, work[i][2])
	while left < right:
		if skip[left] == -1:
			skip[left] = right
			ans[left] = work[i][0]
			left += 1
		else:
			left = skip[left]
for i in ans:
	print(i)


import sys
input = sys.stdin.readline
import bisect
(n, q) = map(int, input().split())
ran = []
for i in range(n):
	(s, t, x) = map(int, input().split())
	ran.append((s - x, t - x - 1, x))
ran.sort(key=lambda a: a[2])
qu = []
convert = {}
for i in range(q):
	que = int(input())
	convert[que] = i
	qu.append(que)
qu.sort()
memo = [-1] * q
ans = [-1] * q
for i in range(n):
	x = ran[i][2]
	l = ran[i][0]
	r = ran[i][1]
	ql = bisect.bisect_left(qu, l)
	qr = bisect.bisect_right(qu, r)
	if ql >= qr:
		continue
	while ql < qr:
		if memo[ql] >= 0:
			ql = memo[ql]
		else:
			memo[ql] = qr
			ans[convert[qu[ql]]] = x
			ql += 1
for i in ans:
	print(i)


def main():
	from heapq import heappush, heappop
	import sys
	sys.setrecursionlimit(10 ** 7)
	(n, q) = map(int, input().split())
	event = []
	for _ in range(n):
		(s, t, x) = map(int, input().split())
		event.append((s - x, 1, x))
		event.append((t - x, -1, x))
	for i in range(q):
		event.append((int(input()), 2, i))
	event.sort()
	ans = [0] * q
	stop = set()
	hq = []
	for (t, op, x) in event:
		if op == 1:
			heappush(hq, x)
			stop.add(x)
		elif op == -1:
			stop.remove(x)
		else:
			while hq and hq[0] not in stop:
				heappop(hq)
			ans[x] = hq[0] if hq else -1
	for x in ans:
		print(x)
main()


import sys, heapq
input = sys.stdin.readline
(N, Q) = map(int, input().split())
event = []
for _ in range(N):
	(s, t, x) = map(int, input().split())
	event.append([s - x, t - x, x])
D = [int(input()) for _ in range(Q)]
event.sort()
closed = []
ei = 0
for d in D:
	while ei < N and event[ei][0] <= d:
		heapq.heappush(closed, (event[ei][2], event[ei][1]))
		ei += 1
	while closed and closed[0][1] <= d:
		heapq.heappop(closed)
	if closed:
		print(closed[0][0])
	else:
		print(-1)


from collections import deque, defaultdict
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
events = [None] * (2 * N)
for i in range(N):
	(S, T, X) = map(int, input().split())
	events[2 * i] = (S - X, X)
	events[2 * i + 1] = (T - X, -X)
events.sort(key=lambda x: x[0])
events = deque(events)
ans = [0] * Q
cur = []
remove = defaultdict(int)
for i in range(Q):
	D = int(input())
	while events and events[0][0] <= D:
		(t, x) = events.popleft()
		if x > 0:
			heappush(cur, x)
		else:
			remove[-x] += 1
	while cur and remove[cur[0]]:
		remove[cur[0]] -= 1
		heappop(cur)
	ans[i] = cur[0] if cur else -1
print(*ans, sep='\n')


import sys
input = sys.stdin.readline
from heapq import heappop, heappush
from bisect import bisect, bisect_left
(N, Q) = map(int, input().split())
table = []
for i in range(N):
	(s, t, x) = map(int, input().split())
	if t - 1 - x < 0:
		continue
	table.append((x, max(0, s - x), t - 1 - x))
H = []
D = [int(input()) for i in range(Q)]
for (x, a, b) in table:
	heappush(H, (bisect_left(D, a), bisect(D, b), x))
K = []
U = [10 ** 12] * Q
J = []
for i in range(Q):
	while len(H) > 0 and H[0][0] <= i:
		(a, b, x) = heappop(H)
		heappush(J, (x, a, b))
	while len(J) > 0 and J[0][2] <= i:
		(x, a, b) = heappop(J)
	if len(J) > 0:
		U[i] = min(U[i], J[0][0])
for i in range(Q):
	if U[i] == 10 ** 12:
		print(-1)
	else:
		print(U[i])


import heapq
(N, Q) = map(int, input().split())
events = []
for _ in range(N):
	(S, T, X) = map(int, input().split())
	events.append([S - X, 1, X])
	events.append([T - X, 0, X])
for _ in range(Q):
	D = int(input())
	events.append([D, 2, 0])
events.sort()
closed = set()
que = []
idx = 0
for (time, flag, position) in events:
	if flag == 0:
		closed.remove(position)
	elif flag == 1:
		heapq.heappush(que, position)
		closed.add(position)
	else:
		while len(que) > 0 and que[0] not in closed:
			heapq.heappop(que)
		if len(que) > 0:
			print(que[0])
		else:
			print(-1)


from heapq import heappush, heappop
from operator import itemgetter
import sys
input = sys.stdin.readline

class PseudoSet:

	def __init__(self):
		self.s = []
		self.e = []

	def insert(self, x):
		heappush(self.s, x)

	def erase(self, x):
		heappush(self.e, x)

	def get_min(self):
		while self.e and self.e[0] == self.s[0]:
			_ = heappop(self.s)
			_ = heappop(self.e)
		return self.s[0] if len(self.s) > 0 else None
(n, q) = map(int, input().split())
events = []
for i in range(n):
	(s, t, x) = map(int, input().split())
	events.append((s - x, +1, x))
	events.append((t - x, -1, x))
for i in range(q):
	d = int(input())
	events.append((d, 2, i))
ans = [-1] * q
events.sort(key=itemgetter(0, 1))
ps = PseudoSet()
for (c, t, z) in events:
	if t == 1:
		ps.insert(z)
	elif t == -1:
		ps.erase(z)
	else:
		m = ps.get_min()
		if m is not None:
			ans[z] = m
print(*ans, sep='\n')


import sys
from heapq import *
input = sys.stdin.readline

def main():
	(n, q) = list(map(int, input().split()))
	key = []
	for i in range(n):
		(s, t, x) = list(map(int, input().split()))
		(l, r) = (max(0, s - x), max(0, t - x))
		key.append((l, 1, x))
		key.append((r, -1, x))
	for i in range(q):
		d = int(input())
		key.append((d, 2))
	key.sort()
	judge = []
	already = dict()
	for i in range(2 * n + q):
		k = key[i]
		if k[1] == -1:
			if k[2] in already:
				already[k[2]] += 1
			else:
				already[k[2]] = 1
		elif k[1] == 1:
			heappush(judge, k[2])
		else:
			while judge:
				if judge[0] in already and already[judge[0]] > 0:
					already[judge[0]] -= 1
					heappop(judge)
				else:
					break
			if judge:
				print(judge[0])
			else:
				print(-1)

def __starting_point():
	main()
__starting_point()


import sys
from heapq import heappush, heappop
input = sys.stdin.readline
data = []
(n, q) = map(int, input().split())
for i in range(n):
	(s, t, x) = map(int, input().split())
	data.append([s - x, t - x, x])
data.sort(key=lambda x: x[0])
d_index = 0
candidate_x = []
inf = float('inf')
data += [[inf, inf, inf]]
for i in range(q):
	d = int(input())
	while d >= data[d_index][0]:
		heappush(candidate_x, (data[d_index][2], data[d_index][1]))
		d_index += 1
	if len(candidate_x) == 0:
		print(-1)
	else:
		while candidate_x:
			(x, finish_t) = heappop(candidate_x)
			if finish_t > d:
				heappush(candidate_x, (x, finish_t))
				print(x)
				break
		else:
			print(-1)


from heapq import heappop, heappush
from collections import defaultdict
(N, Q) = map(int, input().split())
event = []
for _ in range(N):
	(s, t, x) = map(int, input().split())
	event.append((s - x, 1, x))
	event.append((t - x, 2, x))
for i in range(Q):
	d = int(input())
	event.append((d, 3, i))
event.sort()
memo = defaultdict(int)
nowStop = []
ans = [-1] * Q
for (t, e, x) in event:
	if e == 1:
		heappush(nowStop, x)
		memo[x] += 1
	if e == 2:
		memo[x] -= 1
	if e == 3:
		while nowStop:
			s = nowStop[0]
			if memo[s] == 0:
				heappop(nowStop)
			else:
				ans[x] = s
				break
for a in ans:
	print(a)


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

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

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

def ZIP(n):
	return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
(N, Q) = MAP()
event = [None] * (2 * N + Q)
Xl = [0] * N
for i in range(N):
	(S, T, X) = MAP()
	event[2 * i] = (S - X, 1, X)
	event[2 * i + 1] = (T - X, 0, X)
	Xl[i] = X
t = 2 * N
for i in range(Q):
	D = INT()
	event[t + i] = (D, 2, 0)
event.sort()
p = []
q = []
for (t, c, x) in event:
	if c == 0:
		heappush(q, x)
	elif c == 1:
		heappush(p, x)
	else:
		while q and p[0] == q[0]:
			heappop(p)
			heappop(q)
		print(-1 if not p else p[0])


import heapq
import sys
input = sys.stdin.readline
(N, Q) = (int(i) for i in input().split())
L = [0] * 2 * N
for i in range(N):
	(S, T, X) = (int(i) for i in input().split())
	L[2 * i] = (S - X, X, 1)
	L[2 * i + 1] = (T - X, X, 0)
L.sort(reverse=True)
Xs = set([])
XH = []
heapq.heapify(XH)
for i in range(Q):
	D = int(input())
	ans = 0
	while True:
		if L:
			(t, X, f) = L.pop()
			if t <= D:
				if f == 1:
					Xs.add(X)
					heapq.heappush(XH, X)
				else:
					Xs.remove(X)
			else:
				L.append((t, X, f))
				break
		else:
			break
	if Xs:
		while XH[0] not in Xs:
			X = heapq.heappop(XH)
		print(XH[0])
	else:
		print('-1')


import sys
input = sys.stdin.buffer.readline
(N, Q) = map(int, input().split())
List = []
dic = {}
for _ in range(N):
	(s, t, x) = map(int, input().split())
	List.append((s - 0.5 - x, 1, x))
	List.append((t - 0.5 - x, -1, x))
	dic[x] = False
import heapq
List.sort()
h = []
j = 0
for _ in range(Q):
	D = int(input())
	while j < 2 * N and List[j][0] < D:
		if List[j][1] == 1:
			heapq.heappush(h, List[j][2])
			dic[List[j][2]] = True
		else:
			dic[List[j][2]] = False
		j += 1
	while h:
		ans = h[0]
		if dic[ans]:
			print(ans)
			break
		else:
			heapq.heappop(h)
	if not h:
		print(-1)


import heapq
(N, Q) = map(int, input().split())
que = []
ans = [-1 for i in range(Q)]
D = [0 for i in range(N)]
heap = []
heapq.heapify(heap)
Set = set([])
for i in range(N):
	(s, t, x) = map(int, input().split())
	que.append((s - x, 0, i))
	que.append((t - x, 1, i))
	D[i] = x
for i in range(Q):
	d = int(input())
	que.append((d, 2, i))
que.sort(key=lambda x: x[0])
for x in que:
	demand = x[1]
	if demand == 0:
		heapq.heappush(heap, (D[x[2]], x[2]))
		Set.add(x[2])
	elif demand == 1:
		Set.remove(x[2])
	else:
		flag = True
		while heap and flag:
			(distance, index) = heapq.heappop(heap)
			if index in Set:
				ans[x[2]] = distance
				heapq.heappush(heap, (distance, index))
				flag = False
for i in range(Q):
	print(ans[i])


import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
q = []
STX = [[int(x) for x in input().split()] for _ in range(N)]
for (s, t, x) in STX:
	q.append((s - x, 1, x))
	q.append((t - x, 0, x))
for i in range(Q):
	d = int(input())
	q.append((d, 2, i))
answer = [-1] * Q
se = set()
q.sort()
min_se = 10 ** 18
flag = False
for (a, c, b) in q:
	if not c:
		se.remove(b)
		if min_se == b:
			flag = False
	elif c & 1:
		se.add(b)
		if b < min_se:
			min_se = b
			flag = True
	elif se:
		if not flag:
			min_se = min(se)
			flag = True
		answer[b] = min_se
print('\n'.join(map(str, answer)))


import sys
from heapq import heappush, heappop
I = sys.stdin.readlines()
(N, Q) = map(int, I[0].split())
P = []
for i in range(1, N + 1):
	(s, t, x) = map(int, I[i].split())
	P.append((s - x, t - 1 - x, x))
P.sort()
INF = float('inf')
P.append((INF, INF, INF))
q = []
cur = 0
(s, t, x) = P[cur]
for i in range(N + 1, N + Q + 1):
	d = int(I[i])
	while s <= d:
		heappush(q, (x, t))
		cur += 1
		(s, t, x) = P[cur]
	ans = -1
	while len(q) > 0:
		(x1, t1) = q[0]
		if d <= t1:
			ans = x1
			break
		else:
			heappop(q)
	print(ans)


import heapq

class BalancingTree:

	def __init__(self):
		self.p = []
		self.q = []

	def insert(self, x):
		heapq.heappush(self.p, x)

	def erase(self, x):
		heapq.heappush(self.q, x)

	def minimum(self):
		while self.q and self.p[0] == self.q[0]:
			heapq.heappop(self.p)
			heapq.heappop(self.q)
		return self.p[0] if self.p else -1
(n, q) = list(map(int, input().split()))
events = []
for _ in range(n):
	(s, t, x) = list(map(int, input().split()))
	events.append((s - x, 1, x))
	events.append((t - x, 0, x))
for _ in range(q):
	d = int(input())
	events.append((d, 2, 0))
events.sort()
bt = BalancingTree()
for (_, i, k) in events:
	if i == 1:
		bt.insert(k)
	elif i == 0:
		bt.erase(k)
	else:
		print(bt.minimum())


import sys
input = sys.stdin.readline
from heapq import heappop, heappush
(N, Q) = map(int, input().split())
event_list = []
for i in range(N):
	(s, t, x) = map(int, input().split())
	event_list.append([s - x, 1, x])
	event_list.append([t - x, -1, x])
for i in range(Q):
	event_list.append([int(input()), 2, 0])
ans = []
event_list.sort()
x_set = set()
x_list = []
for (time, event, x) in event_list:
	if event == 1:
		x_set.add(x)
		heappush(x_list, x)
	elif event == -1:
		x_set.remove(x)
	else:
		while x_list and x_list[0] not in x_set:
			heappop(x_list)
		if x_list:
			ans.append(x_list[0])
		else:
			ans.append(-1)
print(*ans, sep='\n')


import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
S = [None] * N
T = [None] * N
X = [None] * N
for i in range(N):
	(S[i], T[i], X[i]) = map(int, input().split())
D = [None] * Q
for i in range(Q):
	D[i] = int(input())
roadworks = [(x, s, t) for (x, s, t) in zip(X, S, T)]
roadworks = sorted(roadworks, key=lambda x: x[0])
walkers = D[:]
ans = [-1] * Q
skip = [-1] * Q
import bisect
for (x, s, t) in roadworks:
	left = bisect.bisect_left(walkers, s - x)
	right = bisect.bisect_left(walkers, t - x)
	i = left
	while i < right:
		if skip[i] == -1:
			ans[i] = x
			skip[i] = right
			i += 1
		else:
			i = skip[i]
for a in ans:
	print(a)


import sys, math, itertools, collections, bisect, heapq
input = lambda : sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf')
mod = 10 ** 9 + 7
mans = inf
ans = 0
count = 0
pro = 1
(n, q) = map(int, input().split())
STX = [tuple(map(int, input().split())) for i in range(n)]
D = [int(input()) for i in range(q)]
event = []
for (si, ti, xi) in STX:
	event.append((si - xi, 0, xi))
	event.append((ti - xi, -1, xi))
for di in D:
	event.append((di, 1, di))
event.sort()
hq = []
S = set()
ans = []
for (time, query, number) in event:
	if query == 0:
		heapq.heappush(hq, number)
		S.add(number)
	elif query == -1:
		S.remove(number)
	else:
		while hq and hq[0] not in S:
			heapq.heappop(hq)
		if not hq:
			ans.append(-1)
		else:
			ans.append(hq[0])
print(*ans, sep='\n')


import sys
input = sys.stdin.readline
(N, Q) = list(map(int, input().split()))
events = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for i in range(Q)]
ans = ['-1'] * Q
skip = [-1] * Q
events.sort(key=lambda x: x[2])
import bisect
for (S, T, X) in events:
	right = bisect.bisect_left(D, T - X)
	left = bisect.bisect_left(D, S - X)
	while left < right:
		if skip[left] == -1:
			ans[left] = str(X)
			skip[left] = right
			left += 1
		else:
			left = skip[left]
print('\n'.join(ans))


(n, q) = map(int, input().split())
import heapq
import sys
input = sys.stdin.readline
event = []
for _ in range(n):
	(s, t, x) = map(int, input().split())
	heapq.heappush(event, (s - x, t - x, x))
t = 0
now = []
for _ in range(q):
	d = int(input())
	if event:
		while event[0][0] <= d:
			tmp = heapq.heappop(event)
			heapq.heappush(now, (tmp[2], tmp[1]))
			if not event:
				break
	if now:
		while now[0][1] <= d:
			heapq.heappop(now)
			if not now:
				print(-1)
				break
		else:
			print(now[0][0])
	else:
		print(-1)


from bisect import bisect_left

def main():
	(N, Q, *I) = map(int, open(0).read().split())
	(STX, D) = (I[:3 * N], I[3 * N:])
	E = sorted(zip(*[iter(STX)] * 3), key=lambda x: x[2])
	R = [-1] * Q
	ans = [-1] * Q
	for (s, t, x) in E:
		l = bisect_left(D, s - x)
		r = bisect_left(D, t - x)
		while l < r:
			if R[l] == -1:
				ans[l] = x
				R[l] = r
				l += 1
			else:
				l = R[l]
	print(*ans, sep='\n')
main()


def main():
	from bisect import bisect_left

	def update(l, r, v):
		(L, R) = (l + N0, 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 = 10 ** 18
		while k + 1:
			if data[k] < s:
				s = data[k]
			k = ~-k // 2
		return s
	(n, *t) = open(0)
	(n, q) = map(int, n.split())
	d = [-10 ** 18] + list(map(int, t[n:])) + [10 ** 18]
	N0 = 2 ** (q + 1).bit_length()
	data = [10 ** 18] * 2 * N0
	for (x, t, s) in sorted((list(map(int, t.split()))[::-1] for t in t[:n]))[::-1]:
		l = bisect_left(d, s - x)
		r = bisect_left(d, t - x)
		update(l, r, x)
	for i in range(q):
		a = query(i + 1)
		print(-(a == 10 ** 18) or a)
main()


import sys
input = sys.stdin.readline
read = sys.stdin.read
import heapq
(n, q) = map(int, input().split())
STX = [list(map(int, input().split())) for _ in range(n)]
D = list(map(int, read().split()))
E = []
for (s, t, x) in STX:
	E.append((s - x, x, 1))
	E.append((t - x, x, 0))
E.sort(reverse=True)
que = []
stop = set()
que.append(10 ** 10)
stop.add(10 ** 10)
for d in D:
	while E and E[-1][0] <= d:
		(temp, x, f) = E.pop()
		if f:
			heapq.heappush(que, x)
			stop.add(x)
		else:
			stop.remove(x)
	while que[0] not in stop:
		heapq.heappop(que)
	if que[0] == 10 ** 10:
		print(-1)
	else:
		print(que[0])


import heapq
(n, q) = list(map(int, input().split()))
event = []
for _ in range(n):
	(s, t, x) = list(map(int, input().split()))
	event.append((s - x, 1, x))
	event.append((t - x, -1, x))
event.sort()
heap = []
xs = set([])
d = [int(input()) for _ in range(q)] + [10 ** 9 + 7]
ans = [-1] * q
index = 0
for (t, query, x) in event:
	while d[index] < t:
		if not xs:
			pass
		else:
			while heap:
				tmp = heapq.heappop(heap)
				if tmp in xs:
					heapq.heappush(heap, tmp)
					ans[index] = tmp
					break
		index += 1
	if query == 1:
		xs.add(x)
		heapq.heappush(heap, x)
	else:
		xs.remove(x)
while index < q:
	while heap:
		tmp = heapq.heappop(heap)
		if tmp in xs:
			heapq.heappush(heap, tmp)
			ans[index] = tmp
			break
	index += 1
print('\n'.join(map(str, ans)))


from heapq import heappush, heappop
import sys
readline = sys.stdin.readline
(N, Q) = map(int, readline().split())
ans = [None] * Q

def solve(readline=readline):
	qs = [0] * (N + 1)
	for i in range(N):
		(s, t, x) = map(int, readline().split())
		qs[i] = (s - x, t - x, x)
	qs[N] = (10 ** 10, 10 ** 10, 0)
	qs.sort()
	que = []
	D = [int(readline()) for i in range(Q)]
	j = 0
	it = iter(qs).__next__
	(s, t, x) = it()
	v = w = N
	for d in D:
		while j < N and s <= d:
			heappush(que, (x, t))
			(v, w) = que[0]
			(s, t, x) = it()
		while que and w <= d:
			heappop(que)
			if que:
				(v, w) = que[0]
		if que:
			yield ('%d\n' % v)
		else:
			yield '-1\n'
ans[:] = solve()
sys.stdout.writelines(ans)


import heapq
import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
event_list = []
for i in range(N):
	(S, T, X) = map(int, input().split())
	event_list.append((S - X - 0.5, 1, X))
	event_list.append((T - X - 0.5, -1, X))
dlist = []
for i in range(Q):
	D = int(input())
	event_list.append((D, 0, X))
	dlist.append(D)
event_list.sort()
answer_dic = {}
stop_set = set()
min_set = float('inf')
for (t, f, x) in event_list:
	if f == 1:
		stop_set.add(x)
		if x < min_set:
			min_set = x
	elif f == -1:
		stop_set.remove(x)
		if x == min_set:
			if len(stop_set) > 0:
				min_set = min(stop_set)
			else:
				min_set = float('inf')
	elif len(stop_set) > 0:
		answer_dic[t] = min_set
	else:
		answer_dic[t] = -1
for d in dlist:
	print(answer_dic[d])


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
event = []
for _ in range(n):
	(s, t, x) = map(int, input().split())
	event.append((s - x - 0.5, 1, x))
	event.append((t - x - 0.5, -1, x))
for i in range(q):
	event.append((int(input()), 0, i))
event.sort()
is_stop = False
stop = set()
minstop = float('inf')
ans = [-1] * q
for (t, e, x) in event:
	if e > 0:
		stop.add(x)
		if x < minstop:
			minstop = x
			is_stop = True
	elif e < 0:
		stop.remove(x)
		if minstop == x:
			is_stop = False
	elif len(stop) > 0:
		if not is_stop:
			minstop = min(stop)
			is_stop = True
		ans[x] = minstop
print('\n'.join(map(str, ans)))


import heapq
from collections import deque
(N, Q) = map(int, input().split())
H = [(0, 0, 0) for _ in range(N)]
for i in range(N):
	(s, t, x) = map(int, input().split())
	H[i] = (x - t + 1, x - s, x)
D = [(-int(input()), i) for i in range(Q)]
D.sort()
H.sort()
d = deque(H)
q = []
ANS = [0] * Q
for i in range(Q):
	(t, j) = D[i]
	while d:
		if d[0][0] <= t:
			(_, s, x) = d.popleft()
			heapq.heappush(q, (x, s))
		else:
			break
	while q:
		if q[0][1] >= t:
			break
		heapq.heappop(q)
	if not q:
		ANS[j] = -1
	else:
		ANS[j] = q[0][0]
for ans in ANS:
	print(ans)


import sys
input = sys.stdin.readline
import heapq
(n, q) = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]
L1 = []
for i in range(n):
	L1.append((l[i][0] - l[i][2], 1, l[i][2]))
	L1.append((l[i][1] - l[i][2], -1, l[i][2]))
for i in range(q):
	L1.append((int(input()), 2, 0))
L1.sort()
L2 = []
heapq.heapify(L2)
L3 = []
L3 = set(L3)
for i in range(len(L1)):
	if L1[i][1] == 1:
		heapq.heappush(L2, L1[i][2])
		L3.add(L1[i][2])
	elif L1[i][1] == -1:
		L3.remove(L1[i][2])
	else:
		while L2 and L2[0] not in L3:
			heapq.heappop(L2)
		if L2:
			print(L2[0])
		else:
			print(-1)


import sys
import heapq
from collections import defaultdict
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
(N, Q) = map(int, input().split())
task = []
for _ in range(N):
	(s, t, x) = map(int, input().split())
	start = t - x
	end = s - x
	task.append((start, -1, x))
	task.append((end, 1, x))
task.sort(reverse=True)
cand = []
discard = defaultdict(int)
ans = []
for _ in range(Q):
	d = int(input())
	while task and task[-1][0] <= d:
		(_, flag, x) = task.pop()
		if flag == 1:
			heapq.heappush(cand, x)
		else:
			discard[x] += 1
	while cand:
		x = cand[0]
		if discard[x] > 0:
			heapq.heappop(cand)
			discard[x] -= 1
		else:
			break
	if cand:
		ans.append(cand[0])
	else:
		ans.append(-1)
print(*ans, sep='\n')


import sys
input = sys.stdin.buffer.readline
from operator import itemgetter as get
from heapq import *

def main():
	(n, q) = map(int, input().split())
	event = []
	Xs = []
	for _ in range(n):
		(s, t, x) = map(int, input().split())
		event.append((-2, s - x, x))
		event.append((-1, t - x, x))
		Xs.append(x)
	for _ in range(q):
		d = int(input())
		event.append((0, d, None))
	event.sort(key=get(1))
	active = {x: 0 for x in Xs}
	candidate = []
	ans = []
	for (flg, time, x) in event:
		if flg == -2:
			active[x] = 1
			heappush(candidate, x)
		elif flg == -1:
			active[x] = 0
		else:
			res = -1
			while candidate:
				c = heappop(candidate)
				if active[c]:
					heappush(candidate, c)
					res = c
					break
			ans.append(res)
	print('\n'.join(map(str, ans)))
main()


from heapq import heapify, heappop, heappush
import sys
read = sys.stdin.readline

class mset:

	def __init__(self):
		(self.p, self.q) = ([], [])
		heapify(self.p)
		heapify(self.q)

	def add(self, a):
		heappush(self.p, a)

	def delete(self, a):
		heappush(self.q, a)

	def minimum(self):
		while self.q and self.p[0] == self.q[0]:
			heappop(self.p)
			heappop(self.q)
		return self.p[0] if self.p else None
(N, Q) = map(int, read().split())
event = []
for i in range(N):
	(S, T, X) = map(int, read().split())
	event.append((1, S - X, X))
	event.append((0, T - X, X))
s = mset()
now = 0
for i in range(Q):
	D = int(read())
	event.append((2, D, 0))
event.sort(key=lambda x: (x[1], x[0]))
for (c, t, w) in event:
	if c == 0:
		s.delete(w)
	elif c == 1:
		s.add(w)
	else:
		m = s.minimum()
		print(-1 if m == None else m)


import sys
from bisect import *
input = sys.stdin.readline

def f(n, q):
	xst = []
	for i in range(n):
		(s, t, x) = map(int, input().split())
		xst.append([x, s - x, t - x])
	xst.sort()
	ds = []
	for i in range(q):
		d = int(input())
		ds.append(d)
	ans = [-1] * q
	jump = [-1] * q
	for (x, s, t) in xst:
		i = bisect_left(ds, s)
		fi = bisect_left(ds, t)
		while i < fi:
			if jump[i] != -1:
				i = jump[i]
			else:
				ans[i] = x
				jump[i] = fi
				i += 1
	print(*ans, sep='\n')
(n, q) = map(int, input().split())
f(n, q)


import heapq as hq
from collections import defaultdict
(N, Q) = map(int, input().split())
event = []
for i in range(N):
	(si, ti, xi) = map(int, input().split())
	event.append([si - xi, ti - xi, xi])
Dlist = [int(input()) for i in range(Q)]
event.sort(key=lambda x: x[0])
h = []
tdic = defaultdict(int)
ind = 0
for Di in Dlist:
	while ind < N and event[ind][0] <= Di:
		hq.heappush(h, event[ind][2])
		tdic[event[ind][2]] = event[ind][1]
		ind += 1
	while h and Di >= tdic[h[0]]:
		hq.heappop(h)
	if h:
		print(h[0])
	else:
		print(-1)


from bisect import bisect_left as b
(n, q) = map(int, input().split())
w = sorted([list(map(int, input().split()))[::-1] for _ in [0] * n])
p = [int(input()) for _ in [0] * q]
a = [-1] * q
o = [-1] * q
for (x, t, s) in w:
	(l, r) = (b(p, s - x), b(p, t - x))
	while l < r:
		if o[l] + 1:
			l = o[l]
		else:
			(a[l], o[l]) = (x, r)
			l += 1
print(*a)


import sys, heapq
input = sys.stdin.buffer.readline

def main():
	(N, Q) = map(int, input().split())
	tl = []
	for _ in range(N):
		(S, T, X) = map(int, input().split())
		tl.append((S - X, 1, X))
		tl.append((T - X, 0, X))
	for _ in range(Q):
		D = int(input())
		tl.append((D, 2, 0))
	tl.sort()
	working = list()
	todelete = list()
	for (t, c, x) in tl:
		if c == 0:
			heapq.heappush(todelete, x)
		elif c == 1:
			heapq.heappush(working, x)
		else:
			while todelete and todelete[0] == working[0]:
				heapq.heappop(todelete)
				heapq.heappop(working)
			print(-1 if not working else working[0])
	return
main()


import sys
from heapq import heappop, heappush
input = sys.stdin.readline
(n, Q) = map(int, input().split())
stx = [list(map(int, input().split())) for i in range(n)]
dls = [int(input()) for i in range(Q)]
event = []
for i in range(n):
	(s, t, x) = stx[i]
	event.append((s - x, 1, x))
	event.append((t - x, -1, x))
for i in range(Q):
	d = dls[i]
	event.append((d, 2, i))
event.sort()
ans = [-1] * Q
s = set()
hq = []
for (t, q, x) in event:
	if q == 1:
		s.add(x)
		heappush(hq, x)
	elif q == -1:
		s.remove(x)
	elif q == 2:
		while hq and hq[0] not in s:
			heappop(hq)
		if hq:
			ans[x] = hq[0]
		else:
			ans[x] = -1
print(*ans, sep='\n')


from bisect import bisect, bisect_left
import sys
input = sys.stdin.readline

def main():
	(n, q) = map(int, input().split())
	xst = []
	for i in range(n):
		(s, t, x) = map(int, input().split())
		xst.append([x, s - x, t - x])
	xst.sort()
	d = [None] * q
	for i in range(q):
		d[i] = int(input())
	ans = [-1] * q
	skip = [-1] * q
	for u in xst:
		(x, left, right) = u
		a = bisect_left(d, left)
		b = bisect_left(d, right)
		while a < b:
			if skip[a] == -1:
				ans[a] = x
				skip[a] = b
				a += 1
			else:
				a = skip[a]
	for u in ans:
		print(u)
main()


(N, Q) = map(int, input().split())
import sys

def input():
	return sys.stdin.readline().strip()
STX = [list(map(int, input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]
X = []
for (s, t, x) in STX:
	X.append((s - x, 1, x))
	X.append((t - x, -1, x))
X.sort(key=lambda x: x[0])
a = 0
k = []
from heapq import heappop, heappush
kd = {}
for x in X:
	while a < Q and D[a] < x[0]:
		if len(k) > 0:
			print(k[0])
		else:
			print(-1)
		a += 1
	if x[1] == 1:
		heappush(k, x[2])
		if x[2] in kd:
			kd[x[2]] = 0
	else:
		kd[x[2]] = 1
		while len(k) > 0 and k[0] in kd and (kd[k[0]] == 1):
			heappop(k)
while a < Q:
	print(-1)
	a += 1


import sys
input = sys.stdin.readline
from collections import deque
from heapq import heappush, heappop
import re

def int_raw():
	return int(input())

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

def ints_raw():
	return tuple(map(int, ss_raw()))

def main():
	(N, Q) = ints_raw()
	origST = []
	for idx in range(N):
		(S, T, X) = ints_raw()
		origST.append([S - X, T - X, X])
	Ds = [int(input()) for _ in range(Q)]
	origST.sort()
	stidx = 0
	cur_set = []
	for q in Ds:
		while stidx < len(origST):
			st = origST[stidx]
			if st[0] > q:
				break
			heappush(cur_set, (st[2], st[1]))
			stidx += 1
		while cur_set and cur_set[0][1] <= q:
			heappop(cur_set)
		if len(cur_set) == 0:
			print(-1)
		else:
			print(cur_set[0][0])
main()


import sys
from heapq import heappop, heappush
(n, q) = map(int, input().split())
lines = sys.stdin.readlines()
events = []
kkk = []
for line in lines[:n]:
	(s, t, x) = map(int, line.split())
	events.append((s - x, 2, x))
	events.append((t - x, 1, x))
for line in lines[n:]:
	events.append((int(line), 3))
events.sort()
constructing = []
available = set()
buf = []
for ev in events:
	if ev[1] == 2:
		heappush(constructing, ev[2])
		available.add(ev[2])
	elif ev[1] == 1:
		available.remove(ev[2])
	elif not available:
		buf.append(-1)
	else:
		while constructing[0] not in available:
			heappop(constructing)
		buf.append(constructing[0])
print('\n'.join(map(str, buf)))


import sys
input = sys.stdin.readline
import heapq
(N, Q) = (int(i) for i in input().split())
L = [0] * (2 * N + Q)
for i in range(N):
	(S, T, X) = (int(i) for i in input().split())
	L[2 * i] = (S - X, 1, X)
	L[2 * i + 1] = (T - X, -1, X)
for i in range(Q):
	D = int(input())
	L[2 * N + i] = (D, 2, 0)
L.sort()
Xs = set([])
XH = []
heapq.heapify(XH)
for (t, f, X) in L:
	if f == 1:
		Xs.add(X)
		heapq.heappush(XH, X)
	elif f == -1:
		Xs.remove(X)
	elif Xs:
		while XH[0] not in Xs:
			X = heapq.heappop(XH)
		print(XH[0])
	else:
		print('-1')


from bisect import bisect_left
(n, q) = map(int, input().split())
stx = [list(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]
INF = 10 ** 9 + 1
stx.sort(key=lambda x: x[2])
nxt = [-1] * q
ans = [-1] * q
for (s, t, x) in stx:
	l = bisect_left(d, s - x)
	r = bisect_left(d, t - x)
	while l < r:
		if nxt[l] == -1:
			ans[l] = x
			nxt[l] = r
			l += 1
		else:
			l = nxt[l]
print(*ans, sep='\n')


from bisect import bisect_left, bisect_right
(n, q) = map(int, input().split())
w = [list(map(int, input().split()))[::-1] for _ in range(n)]
p = [int(input()) for _ in range(q)]
w.sort()
ans = [-1] * q
to = [-1] * q
for (x, t, s) in w:
	(l, r) = (bisect_left(p, s - x), bisect_left(p, t - x))
	while l < r:
		if to[l] == -1:
			ans[l] = x
			to[l] = r
			l += 1
		else:
			l = to[l]
print(*ans)


from heapq import heappop as hpp, heappush as hp
import sys
(N, Q) = map(int, input().split())
stx = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
stx = [(s - x, t - x, x) for (s, t, x) in stx]
stx.sort(reverse=True)
D = [int(sys.stdin.readline()) for _ in range(Q)]
H = []
ans = [None] * Q
for (i, d) in enumerate(D):
	while stx and stx[-1][0] <= d:
		hp(H, stx.pop()[1:][::-1])
	while H and H[0][1] <= d:
		hpp(H)
	if not H:
		ans[i] = -1
	else:
		ans[i] = H[0][0]
for a in ans:
	print(a)


def main():
	(N, Q) = map(int, input().split())
	tl = []
	for _ in range(N):
		(S, T, X) = map(int, input().split())
		tl.append((S - X, 1, X))
		tl.append((T - X, 0, X))
	for _ in range(Q):
		D = int(input())
		tl.append((D, 2, 0))
	tl.sort()
	working = set()
	wcur = 0
	curmin = -1
	flag = False
	for (t, c, x) in tl:
		if c == 0:
			wcur -= 1
			working.remove(x)
			if x <= curmin:
				curmin = x
				flag = True
		elif c == 1:
			wcur += 1
			working.add(x)
			if curmin < 0 or curmin >= x:
				curmin = x
				flag = False
		else:
			if wcur == 0:
				curmin = -1
				flag = False
			elif flag:
				curmin = min(working)
				flag = False
			print(curmin)
	return

def __starting_point():
	main()
__starting_point()


import sys
from heapq import *
input = sys.stdin.readline
(n, Q) = list(map(int, input().split()))
Y = []
for j in range(n):
	a = list(map(int, input().split()))
	Y.append([a[0] - a[2], a[1] - a[2], a[2]])
q = [int(input()) for i in range(Q)]
Y.sort()
X = []
p = 0
for d in q:
	while p < n and Y[p][0] <= d:
		heappush(X, (Y[p][2], Y[p][1]))
		p += 1
	while X and X[0][1] <= d:
		heappop(X)
	if X:
		print(X[0][0])
	else:
		print(-1)


import sys
import bisect
input = sys.stdin.readline
(n, q) = map(int, input().split())
cons = [list(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]
cons.sort(key=lambda x: x[2])
for i in range(n):
	cons[i][0] -= cons[i][2]
	cons[i][1] -= cons[i][2]
ans = [-1] * q
l = [-1] * q
for i in range(n):
	s = bisect.bisect_left(d, cons[i][0])
	t = bisect.bisect_left(d, cons[i][1])
	while s < t:
		if l[s] != -1:
			s = l[s]
		else:
			ans[s] = cons[i][2]
			l[s] = t
			s += 1
print(*ans, sep='\n')


from bisect import bisect_left
(n, Q) = list(map(int, input().split()))
stx = [list(map(int, input().split())) for i in range(n)]
q = [int(input()) for i in range(Q)]
stx.sort(key=lambda x: x[2])
ans = [-1 for i in range(Q)]
skip = [-1 for i in range(Q)]
for (s, t, x) in stx:
	begin = bisect_left(q, s - x)
	end = bisect_left(q, t - x)
	while begin < end:
		if skip[begin] == -1:
			ans[begin] = x
			skip[begin] = end
			begin += 1
		else:
			begin = skip[begin]
for e in ans:
	print(e)


def main():
	from bisect import bisect_left
	from collections import namedtuple
	from operator import attrgetter
	import sys
	input = sys.stdin.readline
	Event = namedtuple('Event', 'pos start end')
	(N, Q) = map(int, input().split())
	events = []
	for _ in range(N):
		(s, t, x) = map(int, input().split())
		e = Event(pos=x, start=s - x, end=t - x)
		events.append(e)
	events.sort(key=attrgetter('pos'))
	D = [int(input()) for _ in range(Q)]
	ans = [-1] * Q
	see = [-1] * Q
	for e in events:
		left = bisect_left(D, e.start)
		right = bisect_left(D, e.end)
		idx = left
		while idx < right:
			if ~ans[idx]:
				idx = see[idx]
				continue
			ans[idx] = e.pos
			see[idx] = right
			idx += 1
	print(*ans, sep='\n')

def __starting_point():
	main()
__starting_point()


import heapq
import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
event_list = []
for i in range(N):
	(S, T, X) = map(int, input().split())
	event_list.append((S - X - 0.5, 1, X))
	event_list.append((T - X - 0.5, -1, X))
dlist = []
for i in range(Q):
	D = int(input())
	event_list.append((D, 0, X))
	dlist.append(D)
event_list.sort()
answer_dic = {}
stop_set = set()
hq = []
for (t, f, x) in event_list:
	if f == 1:
		stop_set.add(x)
		heapq.heappush(hq, x)
	elif f == -1:
		stop_set.remove(x)
	elif len(stop_set) > 0:
		while True:
			if hq[0] in stop_set:
				answer_dic[t] = hq[0]
				break
			else:
				heapq.heappop(hq)
	else:
		answer_dic[t] = -1
for d in dlist:
	print(answer_dic[d])


from bisect import bisect_left
from sys import stdin
readl = stdin.readline
(N, Q) = map(int, readl().rstrip().split())
STX = [list(map(int, readl().rstrip().split())) for _ in range(N)]
Dn = [None for _ in range(Q + 1)]
for i in range(Q):
	Dn[i] = int(readl().rstrip())
Dn[Q] = 10 ** 10
ans = [-1] * (Q + 1)
skip = [-1] * (Q + 1)
for (s, t, x) in sorted(STX, key=lambda x: x[2]):
	l = bisect_left(Dn, s - x)
	r = bisect_left(Dn, t - x)
	while l < r:
		if skip[l] < 0:
			ans[l] = x
			skip[l] = r
			l += 1
		else:
			l = skip[l]
for d in ans[:-1]:
	print(d)


import sys
input = sys.stdin.readline
from bisect import bisect_left
inf = float('inf')
(N, Q) = map(int, input().split())
STX = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]
res = 1
while res < Q:
	res <<= 1
N0 = res
data = [inf for _ in range(2 * N0 - 1)]

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

def value(k):
	k += N0
	res = data[k]
	while k != 0:
		k >>= 1
		res = min(res, data[k])
	return res
for (S, T, X) in STX:
	l = bisect_left(D, S - X)
	r = bisect_left(D, T - X)
	update(l, r, X)
for k in range(Q):
	ans = value(k)
	if ans == inf:
		ans = -1
	print(ans)


import bisect
(n, q) = list(map(int, input().split()))
rws = [list(map(int, input().split())) for _ in range(n)]
ds = [int(input()) for _ in range(q)]
rws.sort(key=lambda x: x[2])
ans = [-1 for _ in range(q)]
nxt = [-1 for _ in range(q)]
for rw in rws:
	st = bisect.bisect_left(ds, rw[0] - rw[2])
	en = bisect.bisect_left(ds, rw[1] - rw[2])
	while st < en:
		if nxt[st] == -1:
			ans[st] = rw[2]
			nxt[st] = en
			st += 1
		else:
			st = nxt[st]
for a in ans:
	print(a)


(N, Q) = map(int, input().split())
STX = [tuple(map(int, input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]
starts = []
ends = []
for (i, (s, t, x)) in enumerate(STX):
	starts.append((s - x, i))
	ends.append((t - x, i))
starts.sort(key=lambda x: x[0], reverse=True)
ends.sort(key=lambda x: x[0], reverse=True)
import heapq
hq = []
heapq.heapify(hq)
delset = set()
ans = []
for d in D:
	while starts and starts[-1][0] <= d:
		(_, i) = starts.pop()
		x = STX[i][2]
		heapq.heappush(hq, x * N + i)
	while ends and ends[-1][0] <= d:
		(_, i) = ends.pop()
		delset.add(i)
	while hq:
		i = hq[0] % N
		if i in delset:
			heapq.heappop(hq)
		else:
			break
	if len(hq) == 0:
		ans.append(-1)
	else:
		ans.append(hq[0] // N)
print(*ans, sep='\n')


import sys
from heapq import *
input = sys.stdin.readline

def main():
	(n, q) = map(int, input().split())
	key = []
	for i in range(n):
		(s, t, x) = map(int, input().split())
		(l, r) = (max(0, s - x), max(0, t - x))
		key.append((l, -1, x))
		key.append((r, 1, x))
	key.sort()
	judge = []
	already = dict()
	search = []
	for i in range(n * 2):
		(s, j, x) = key[i]
		if j == -1:
			heappush(judge, x)
		elif x in already:
			already[x] += 1
		else:
			already[x] = 1
		if i == n * 2 - 1 or key[i][0] != key[i + 1][0]:
			while judge:
				if judge[0] in already and already[judge[0]] > 0:
					already[judge[0]] -= 1
					heappop(judge)
				else:
					break
			if judge:
				search.append((s, judge[0]))
			else:
				search.append((s, -1))
	size = len(search)
	index = 0
	answer = []
	for i in range(q):
		d = int(input())
		while index < size - 1:
			if search[index + 1][0] <= d:
				index += 1
			else:
				break
		print(search[index][1])

def __starting_point():
	main()
__starting_point()


import sys
import bisect
from heapq import heappop, heappush, heapify
input = sys.stdin.readline
from itertools import chain
sys.setrecursionlimit(10 ** 9)
(N, Q) = map(int, input().split())
STX = [list(map(int, input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]
inf = 10 ** 15
TEMP = [[(s - x, True, x), (t - x, False, x)] for (s, t, x) in STX] + [[(-inf, True, inf), (inf, False, inf)]]
PFX = sorted(list(chain(*TEMP)))
addq = [inf]
delq = [inf + 1]
D.append(inf)
iterD = iter(D)
d = next(iterD)
for (p, f, x) in PFX:
	while d < p:
		ans = addq[0] if not addq[0] == inf else -1
		print(ans)
		d = next(iterD)
		if d == inf:
			exit()
	if f:
		heappush(addq, x)
	else:
		heappush(delq, x)
	while addq[0] == delq[0]:
		heappop(addq)
		heappop(delq)


import sys
from bisect import bisect_left
(n, q) = map(int, input().split())
lines = sys.stdin.readlines()
c = []
for line in lines[:n]:
	(s, t, x) = map(int, line.split())
	c.append((x, s, t))
c.sort()
d = list(map(int, lines[n:]))
ans = [-1] * q
skip = [-1] * q
for (x, s, t) in c:
	ss = bisect_left(d, s - x)
	tt = bisect_left(d, t - x)
	while ss < tt:
		if skip[ss] == -1:
			ans[ss] = x
			skip[ss] = tt
			ss += 1
		else:
			ss = skip[ss]
print(*ans, sep='\n')


import sys
input = sys.stdin.readline
read = sys.stdin.read
import heapq

def main():
	(n, q) = map(int, input().split())
	event = []
	stop = set()
	minque = []
	for _ in range(n):
		(s, t, x) = map(int, input().split())
		event.append((s - x, 1, x))
		event.append((t - x, -1, x))
	event.sort()
	event.append((float('inf'), 0, 0))
	D = list(map(int, read().split()))
	now = 0
	for (t, b, x) in event:
		while minque and minque[0] not in stop:
			heapq.heappop(minque)
		m = minque[0] if minque else -1
		while t > D[now]:
			print(m)
			now += 1
			if now == q:
				exit()
		if b == 1:
			stop.add(x)
			heapq.heappush(minque, x)
		else:
			stop.remove(x)
main()