Problem:
 Score : 500 points    Problem Statement 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 1 4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8      Sample Output 1 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 .

Solution (Python):
def examA():
    def calc_L(x1,y1,x2,y2):
        return ((x2-x1)**2 + (y2-y1)**2)**0.5
    N = I()
    X = [LI()for _ in range(N)]
    ans = 0
    for x in itertools.permutations(X):
        cur = 0
        for i in range(1,N):
            cur += calc_L(x[i-1][0],x[i-1][1],x[i][0],x[i][1])
        
        ans += cur
    for i in range(1,N+1):
        ans /= i
    print(ans)
    return

def examB():
    def judge(n):
        sn = 0
        for i in n:
            sn += int(i)
        if int(n)%sn==0:
            return "Yes"
        return "No"
    N = SI()
    ans = judge(N)
    print(ans)
    return

def examC():
    N, K = LI()
    P = LI()
    ans = 0
    S = [0]*(N+1)
    for i in range(N):
        S[i+1] = S[i]+(P[i]+1)/2
    for i in range(N-K+1):
        cur = S[i+K] - S[i]
        if cur>ans:
            ans = cur
    print(ans)
    return

def examD():
    def bfs(n,V,s,W):
        visited = [False]*n
        que = deque()
        que.append(s)
        while(que):
            now = que.pop()
            visited[now] = True
            for ne in V[now]:
                if visited[ne]:
                    continue
                W[ne] += W[now]
                que.append(ne)
        return W
    N, Q = LI()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    W = [0] * N
    for _ in range(Q):
        p, x = LI()
        W[p-1] += x
    ans = bfs(N,V,0,W)
    print(" ".join(map(str,ans)))
    return

def examE():
    def bfs(n,edges,s):
        L = [inf]*n
        que = deque()
        que.append(s)
        L[s] = 0
        while(que):
            now = que.popleft()
            for ne in edges[now]:
                if L[ne]>L[now]+1:
                    L[ne] = L[now]+1
                    que.append(ne)
        return L
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    F = bfs(N,V,0)
    S = bfs(N,V,N-1)
    f = 0; s = 0
    for i in range(N):
        if F[i]>S[i]:
            s += 1
        else:
            f += 1
    if f>s:
        print("Fennec")
    else:
        print("Snuke")
    return

def examF():
    
    class SegmentTree:
        def __init__(self, n, ele, segfun):
            
            self.ide_ele = ele
            self.segfun = segfun
            
            self.n = n
            self.N0 = 1 << n.bit_length()
            self.data = [self.ide_ele] * (self.N0 * 2)

        def update_add(self, l, r, val):
            l += self.N0
            r += self.N0
            while l < r:
                if l & 1:
                    self.data[l] += val
                    l += 1
                if r & 1:
                    self.data[r - 1] += val
                    r -= 1
                l //= 2
                r //= 2

        def update(self, l, r, val):
            l += self.N0
            r += self.N0
            while l < r:
                if l & 1:
                    self.data[l] = self.segfun(self.data[l], val)
                    l += 1
                if r & 1:
                    self.data[r - 1] = self.segfun(self.data[r - 1], val)
                    r -= 1
                l //= 2
                r //= 2

        def query(self, i):
            i += len(self.data) // 2
            ret = self.data[i]
            while i > 0:
                i //= 2
                ret = self.segfun(ret, self.data[i])
            return ret

    N, Q = LI()
    X = []
    for _ in range(N):
        s,t,x = LI()
        l = max(0,s-x)
        r = t-x
        X.append([x,l,r])
    D = [I()for _ in range(Q)]
    seg_min = SegmentTree(Q,inf,lambda a,b:min(a,b))
    for x,l,r in X:
        L = bisect.bisect_left(D,l)
        R = bisect.bisect_left(D,r)
        seg_min.update(L,R,x)
    ans = []
    for i in range(Q):
        cur = seg_min.query(i)
        if cur==inf:
            ans.append(-1)
        else:
            ans.append(cur)
    for v in ans:
        print(v)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examF()

"""

"""

Solution (Python):
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')

Solution (Python):
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")

Solution (Python):
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])

Solution (Python):
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)
if __name__ == "__main__":
    main()

Solution (Python):
import bisect
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)

Solution (Python):
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])

if __name__ == '__main__':
    main()

Solution (Python):
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.discard(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])

if __name__ == '__main__':
    main()

Solution (Python):

from heapq import *
def main():
    import sys;input=sys.stdin.readline
    N, Q = map(int, input().split())
    X = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        X.append((2*s-2*x-1, 0, x))
        X.append((2*t-2*x-1, 1, x))
    inf = 10**18
    X.append((-inf, 0, inf))
    X.append((inf, 1, inf))
    X.sort(key=lambda x: x[0])

    j = 0
    ll = []
    vs = set()
    d = dict()
    for _ in range(Q):
        q = int(input())
        while 1:
            u, f, x = X[j]
            if u > 2*q:
                break
            if f:
                if x not in d:
                    d[x] = 0
                d[x] += 1
            else:
                heappush(ll, x)
            j += 1
        while 1:
            x = heappop(ll)
            if x in d and d[x] > 0:
                d[x] -= 1
                continue
            heappush(ll, x)
            if x == inf:
                print(-1)
            else:
                print(x)
            break

if __name__ == '__main__':
    main()

Solution (Python):
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")

Solution (Python):
def 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=[]
    stop=set()
    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(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)

if __name__ == "__main__":
    main()

Solution (Python):
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)

Solution (Python):
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, 0, x))

for i in range(Q):
    d = int(readline())
    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)))

Solution (Python):
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()

Solution (Python):
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")

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,Q = LI()
    q = LIR(n)
    q.sort(key = lambda x:x[2])
    d = IR(Q)
    ans = [-1]*(Q+1)
    f = [0]*Q
    for s,t,x in q:
        l = bisect.bisect_left(d,s-x)
        r = bisect.bisect_left(d,t-x)
        while l < r:
            while ans[l] != -1:
                l = f[l]
            if r <= l:
                break
            ans[l] = x
            f[l] = r
            l += 1
    for i in ans[:-1]:
        print(i)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
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, 0, x))

for i in range(Q):
    d = int(readline())
    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)))

Solution (Python):
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)))

Solution (Python):

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

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)))

Solution (Python):
import sys
from operator import itemgetter
from heapq import heapify, heappush, heappop

read = sys.stdin.read

N, Q, *STXD = 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
    else:
        if stop != -1:
            if stop <= x:
                heappush(heap, (x, n))
            else:
                heappush(heap, (stop, construction))
                stop, construction = x, n
        else:
            stop, construction = x, n

Solution (Python):
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")

Solution (Python):
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)
    else:
        if Xs:
            while XH[0] not in Xs:
                X = heapq.heappop(XH)
            print(XH[0])
        else:
            print("-1")

Solution (Python):
class SegmentTreeDual():
    def __init__(self,arr,op=lambda x,y:y if y != -1 else x,ie=-1):
        self.h = (len(arr)-1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.op = op
        self.val = [ie for _ in range(self.n)]
        self.laz = [ie for _ in range(2*self.n)]
        for i in range(len(arr)):
            self.val[i] = arr[i]

    def propagate(self,k):
        if self.laz[k] == self.ie: return
        if self.n <= k:
            self.val[k-self.n] = self.op(self.val[k-self.n],self.laz[k])
            self.laz[k] = self.ie
        else:
            self.laz[2*k] = self.op(self.laz[2*k],self.laz[k])
            self.laz[2*k+1] = self.op(self.laz[2*k+1],self.laz[k])
            self.laz[k] = self.ie

    def update(self,left,right,x):
        left += self.n
        right += self.n
        
        for i in range(self.h)[::-1]:
            self.propagate(left>>i)
            self.propagate(right>>i)
        
        while right-left>0:
            if right & 1:
                right -= 1
                self.laz[right] = self.op(self.laz[right],x)
            if left & 1:
                self.laz[left] = self.op(self.laz[left],x)
                left += 1
            left >>= 1
            right >>= 1
    def get(self,index):
        res = self.val[index]
        index += self.n
        while index>0:
            res = self.op(res,self.laz[index])
            index //= 2
        return res


from bisect import bisect_left,bisect_right
import sys
input = sys.stdin.readline
INF = 10**18

N,Q = map(int,input().split())
P = [-INF,INF]
R = []

for i in range(N):
    s,t,x = map(int,input().split())
    R.append((s-x,t-x,x))
    P.append(s-x)
    P.append(t-x)
D = []
for i in range(Q):
    d = int(input())
    D.append(d)
    P.append(d)

R = sorted(R,key=lambda x:x[2],reverse=True)
P = sorted(set(P))
S = dict()
for i in range(len(P)):
    S[P[i]] = i

st = SegmentTreeDual(
                    arr = [-1 for _ in range(len(P))],
                    op = lambda x,y:y if y != -1 else x,
                    ie = -1
                    )
for i in range(N):
    st.update(S[R[i][0]],S[R[i][1]],R[i][2])

ans = []

for i in range(Q):
    ans.append(st.get(S[D[i]]))

print('\n'.join(map(str,ans)))

Solution (Python):
import sys
from heapq import heappop, heappush

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, 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')

Solution (Python):
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')

Solution (Python):
import sys
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)]


import bisect
inf = 10**9 + 100

def init(n,init_num=0):
    num = len(str(bin(n-1))) + 1
    seg = [init_num] * (2**num)
    seg[0] = 2**(num-1)
    return(seg)

def update(head, tail, x):
    
    head += seg[0]
    tail += seg[0]
    points = []
    while(head <= tail):
        if(head == tail):
            points.append(head)
            break

        if(head % 2 ==1):
            points.append(head)
            head += 1
        head = head//2

        if(tail % 2 == 0):
            points.append(tail)
            tail -= 1
        tail = (tail-1)//2

    for point in points:
        seg[point] = min(seg[point], x)

def execute(p):
    p += seg[0]
    tmp = seg[p]
    while(p > 0):
        p = p//2
        tmp = min(tmp, sep[p])
    return(tmp)

def execute_all():
    for i in range(2,len(seg)):
        seg[i] = min(seg[i], seg[i//2])


seg = init(q, init_num = inf)

for i in range(n):
    left = bisect.bisect_left(d, stx[i][0] -stx[i][2])
    right = bisect.bisect_right(d, stx[i][1] - stx[i][2] -1) -1
    update(left, right, stx[i][2])
    

execute_all()

for i in seg[seg[0]: seg[0] + q]:
    if(i == inf):
        print(-1)
    else:
        print(i)

Solution (Python):
import sys
input = sys.stdin.readline

n,q = map(int, input().split())

stx = [0]*n
for i in range(n):
    stx[i] = tuple(map(int, input().split()))

d = [0]*q
for i in range(q):
    d[i] = int(input())


import bisect
inf = 10**9 + 100


b_left = bisect.bisect_left
b_right = bisect.bisect_right

def init(n,init_num=0):
    num = len(str(bin(n-1))) + 1
    seg = [init_num] * (2**num)
    
    seg0 = 2**(num-1)
    return(seg,seg0)

def update(head, tail, x):
    
    head += seg0
    tail += seg0
    points = []
    while(head <= tail):
        if(head == tail):
            points.append(head)
            break

        if(head % 2 ==1):
            points.append(head)
            head += 1
        head = head//2

        if(tail % 2 == 0):
            points.append(tail)
            tail -= 1
        tail = (tail-1)//2

    for point in points:
        seg[point] = min(seg[point], x)

def execute_all():
    for i in range(2,len(seg)):
        seg[i] = min(seg[i], seg[i//2])


seg,seg0 = init(q, init_num = inf)

for i in range(n):
    left = b_left(d, stx[i][0] -stx[i][2])
    right = b_right(d, stx[i][1] - stx[i][2] -1) -1
    update(left, right, stx[i][2])
    

execute_all()

for i in seg[seg0: seg0 + q]:
    if(i == inf):
        print(-1)
    else:
        print(i)

Solution (Python):
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()

Solution (Python):
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()