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):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    """
    とりあえず，S,TはXだけ左にずらして，0秒の時にどの時間ならXで止まるかにする．
    そのあと，グラフ(x-tグラフ)を書いて，縦棒を左から動かしていく（イベントソート）
    通行止めとなるXを複数持っておく必要があり，追加，参照，削除の機能が欲しい
    """

    
    from bisect import bisect_left, bisect_right, insort_right
    class SquareSkipList:
        
        

        def __init__(self, values=None, sorted_=False, square=1000, seed=42):
            
            
            
            
            

            self.cnt=0
            inf = float("inf")
            self.square = square
            if values is None:
                self.rand_y = seed
                self.layer1 = [inf]
                self.layer0 = [[]]
            else:
                self.layer1 = layer1 = []
                self.layer0 = layer0 = []
                if not sorted_:
                    values.sort()
                y = seed
                l0 = []
                for v in values:
                    y ^= (y & 0x7ffff) << 13
                    y ^= y >> 17
                    y ^= (y & 0x7ffffff) << 5
                    if y % square == 0:
                        layer0.append(l0)
                        l0 = []
                        layer1.append(v)
                    else:
                        l0.append(v)
                layer1.append(inf)
                layer0.append(l0)
                self.rand_y = y

        def add(self, x):  
            
            y = self.rand_y
            y ^= (y & 0x7ffff) << 13
            y ^= y >> 17
            y ^= (y & 0x7ffffff) << 5
            self.rand_y = y

            if y % self.square == 0:
                layer1, layer0 = self.layer1, self.layer0
                idx1 = bisect_right(layer1, x)
                layer1.insert(idx1, x)
                layer0_idx1 = layer0[idx1]
                idx0 = bisect_right(layer0_idx1, x)
                layer0.insert(idx1+1, layer0_idx1[idx0:])  
                del layer0_idx1[idx0:]
            else:
                idx1 = bisect_right(self.layer1, x)
                insort_right(self.layer0[idx1], x)

            self.cnt+=1

        def remove(self, x):  
            
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                del self.layer1[idx1]
                self.layer0[idx1] += self.layer0.pop(idx1+1)
            else:
                del layer0_idx1[idx0]

            self.cnt-=1

        def search_higher_equal(self, x):  
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_higher(self, x):  
            idx1 = bisect_right(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_lower(self, x):  
            
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == 0:  
                return self.layer1[idx1-1]
            return layer0_idx1[idx0-1]

        def pop(self, idx):
            
            
            
            self.cnt-=1
            layer0 = self.layer0
            s = -1
            for i, l0 in enumerate(layer0):
                s += len(l0) + 1
                if s >= idx:
                    break
            if s==idx:
                layer0[i] += layer0.pop(i+1)
                return self.layer1.pop(i)
            else:
                return layer0[i].pop(idx-s)


        def all(self):
            print(self.layer1)
            print(self.layer0)

        def len(self):
            return self.cnt

    


    N,Q=MI()
    L=[]
    for _ in range(N):
        s,t,x=MI()
        s-=x
        t-=x
        L.append([s,0,x])
        L.append([t,1,x])
        
    
    for _ in range(Q):
        d=I()
        L.append([d,2,0])
        
    L.sort()
    anss=[]
    inf=10**10
    ssl = SquareSkipList(square=2000)
    ssl.add(inf)
    
    for t,q,x in L:
        if q==0:
            ssl.add(x)
        elif q==2:
            temp=ssl.search_higher_equal(-1)
            if temp==inf:
                ans=-1
            else:
                ans=temp
            anss.append(ans)
        else:
            ssl.remove(x)
            
    for i in range(Q):
        print(anss[i])
                
            
        
        
    
    
main()

Solution (Python):
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 = 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()
bt = BalancingTree()
for _, i, k in events:
    if i == 1:
        bt.insert(k)
    elif i == 0:
        bt.erase(k)
    else:
        print(bt.minimum())

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7














N,Q = getNM()





task = []

STX = [getList() 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 = getN()
    task.append((d, 2, i)) 
answer = [-1] * Q

task.sort()


se = set()
se_hp = [] 
heapq.heapify(se_hp)



for a, b, c in task:
    
    if b == 0:
        
        se.remove(c)
    
    elif b == 1:
        
        se.add(c)
        
        heapq.heappush(se_hp, c)
    
    else:
        
        
        while se_hp and se_hp[0] not in se:
            heapq.heappop(se_hp)
        if se_hp:
            answer[c] = se_hp[0]
        else:
            answer[c] = -1
    
    
    
    
    
    
    
    
    
    

for i in answer:
    print(i)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7














N,Q = getNM()





task = []

STX = [getList() 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 = getN()
    task.append((d, 2, i)) 
answer = [-1] * Q

task.sort()


se = set()
se_hp = [] 
heapq.heapify(se_hp)


for a, b, c in task:
    
    if b == 0:
        
        se.remove(c)
    
    elif b == 1:
        se.add(c)
        heapq.heappush(se_hp, c)
    
    else:
        
        while se_hp and se_hp[0] not in se:
            heapq.heappop(se_hp)
        if se_hp:
            answer[c] = se_hp[0]
        else:
            answer[c] = -1

for i in answer:
    print(i)

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

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    class BIT:
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
            self.depth=n.bit_length()
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s
        
        def lower_bound(self,x):
            sum_=0
            pos=0
            for i in range(self.depth,-1,-1):
                k=pos+(1<<i)
                if k<=self.num and sum_+self.dat[k]<x:
                    sum_+=self.dat[k]
                    pos+=1<<i
            return pos, sum_
    
    N,Q=map(int,input().split())
    S,T,X=[0]*N,[0]*N,[0]*N
    for i in range(N):
        S[i],T[i],X[i]=map(int,input().split())
    unique_X=sorted(list(set(X)))
    d={unique_X[i]:i for i,x in enumerate(unique_X)}
    l=[0]*(N*2+Q)
    for i in range(N):
        l[i*2]=((S[i]-X[i])<<40)+(1<<20)+d[X[i]]
        l[i*2+1]=((T[i]-X[i])<<40)+d[X[i]]
    for i in range(N*2,N*2+Q):
        l[i]=(int(input())<<40)+(2<<20)
    l.sort()
    mask=(1<<20)-1
    b=BIT(len(unique_X))
    for tqx in l:
        x=tqx&mask
        q=(tqx>>20)&mask
        t=(tqx>>40)&mask
        if q==0:
            b.add(x,-1)
        elif q==1:
            b.add(x,1)
        else:
            res,_=b.lower_bound(1)
            print(unique_X[res] if res<len(unique_X) else -1)
        


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import bisect
from heapq import heappop, heappush, heapify
input = sys.stdin.readline
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)]

'''
import random
N = 2*10**5
Q = 2*10**5
STX = []
for i in range(N):
    S,T = sorted([random.randint(0,10**9-1) for i in range(2)])
    if S == T:
        T += 1
    X = random.randint(1,10**9)
    STX.append([S,T,X])
D = sorted([random.randint(0,10*9) for i in range(Q)])
'''

inf = 10**15
PFXS = [(s-x,True,x) for s,t,x in STX]
PFXT = [(t-x,False,x) for s,t,x in STX]
PFX = PFXS + PFXT
PFX.append((-inf,True,inf))
PFX.append((inf,False,inf))
PFX.sort()

addq = [inf]
delq = [inf+1]
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)
        try:
            d = next(iterD)
        except:
            exit()
    if f:
        heappush(addq, x)
    else:
        heappush(delq, x)
    while addq[0] == delq[0]:
        heappop(addq)
        heappop(delq)

Solution (Python):
n,q=map(int,input().split())
stx=[list(map(int,input().split())) for _ in range(n)]
d=[int(input()) for _ in range(q)]
inf=float('inf')

import heapq
class pqheap:
  def __init__(self,key=None):
    self.p = list()
    self.q = list()

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

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

  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 len(self.p)>0 else -1
memopush={}
memopop={}
from bisect import bisect_left,bisect_right
for s,t,x in stx:
  l,r=max(0,s-x),max(0,t-x)
  
  if l in memopush:
    memopush[l].append(x)
  else:
    memopush[l]=[x]
  if r in memopop:
    memopop[r].append(x)
  else:
    memopop[r]=[x]
keys=list(set(memopush.keys()).union(set(memopop.keys())))
keys.sort()
pq=pqheap()
dct=[[-1,-1]]
for k in keys:
  if k in memopush:
    for v in memopush[k]:
      pq.insert(v)
  if k in memopop:
    for v in memopop[k]:
      pq.erase(v)
  dct.append([k,pq.minimum()])
i=0
for x in d:
  while i+1<len(dct) and dct[i+1][0]<=x:
    i+=1
  if i>=len(dct):
    print(-1)
  else:
    print(dct[i][1])

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

INF = 1001001001

N, Q = map(int, input().split())
STXs = [tuple(map(int, input().split())) for _ in range(N)]
Ds = [int(input()) for _ in range(Q)]


future_block = [(S - X, T - X, X) for S, T, X in STXs]
future_block.append((INF, INF, INF)) 
heapify(future_block)


current_block = [(INF, INF)] 
current_min_pair = (INF, INF)

for D in Ds:
    while future_block[0][0] <= D:
        s_x, t_x, x = heappop(future_block)
        if current_min_pair[1] > x:
            current_min_pair = (t_x, x)
        heappush(current_block, (t_x, x))
    
    search_min_flg = False
    while current_block[0][0] <= D:
        if current_min_pair == heappop(current_block):
            search_min_flg = True
    if search_min_flg:
        current_min_pair = min(current_block, key = lambda t: t[1])

    print(-1 if current_min_pair[1] == INF else current_min_pair[1])

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

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

def main():
    n,q=map(int, input().split())
    event = []
    end = []
    for i 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,2,i])
    event.sort(key = itemgetter(0,1))
    res = [-1]*q
    ps = PseudoSet()
    for time,type,x in event:
        if(type==1):
            ps.insert(x)
        elif(type==0):
            ps.erase(x)
        else:
            k = ps.get_min()
            if k is not None:
                res[x]=k
    print(*res,sep="\n")

if __name__ == '__main__':
    main()

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

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

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

for d in dist:
    print(d)

Solution (Python):
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'
    
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase

read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()









show_flg=False


ans=0

a=[]
n,q=LI()
for i in range(n):
    s,t,x=LI()
    a+=(x,(s-x,t-x)),
a.sort(key=lambda x:-x[1][0])

d=NI(q)

p=[]
g=[]
for i in range(q):
    c=d[i]
    while a and a[-1][1][0]<=c:
        x,(l,r)=a.pop()
        heappush(p,(x,(l,r)))
    
    while p and p[0][1][1]<=c:
        x,(l,r)=heappop(p)

    if p:
        ans=p[0][0]
    else:
        ans=-1
    g+=ans,

for i in g:
    print(i)

Solution (Python):
from heapq import heappop,heappush

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


event=[]
q=[]
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])

stop_set=set()
event.sort()
q=[]

for pos,m,x in event:
    if m==-1:
        stop_set.remove(x)
        
    elif m==1:
        
        heappush(q,x)
        stop_set.add(x)
    
    else:
        
        
        while q:
            
            if q[0] not in stop_set:
                heappop(q)
            
            else:
                break

        if q:
            print(q[0])
        else:
            print(-1)

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

Solution (Python):
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())
stx = []
events = []
for i in range(n):
    s, t, x = map(int, input().split())
    stx.append((s, t, x))
    events.append((s - x, +1, i))
    events.append((t - x, -1, i))
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, i in events:
    if t == 1:
        ps.insert(stx[i][2])
    elif t == -1:
        ps.erase(stx[i][2])
    else:
        
        m = ps.get_min()
        if m is not None:
            ans[i] = m

print(*ans, sep='\n')

Solution (Python):

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

Solution (Python):

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

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
import bisect

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

STX = []
vals = set()
for _ in range(N):
    s,t,x = map(int,input().split())
    STX.append((max(0,s-x), max(0,t-x), x))
    vals.add(max(0,s-x))
    vals.add(max(0,t-x))
D = [int(input()) for _ in range(Q)]
for d in D:
    vals.add(d)
vals = list(vals)
vals.sort()
L = len(vals)
mapping = [-1]*(L+1)
imos = [[] for _ in range(L+1)]
STX.sort(key=lambda x:x[2])
priority = 0 
for s,t,x in STX:
    s1 = bisect.bisect_left(vals, s)
    t1 = bisect.bisect_left(vals, t)
    imos[s1].append([1, priority, x])
    imos[t1].append([0, priority, x])
    priority += 1

import heapq
cur = -1
cur_priority = 10**9
que = [(cur_priority, cur)]
valid_priority = [True]*(N+1)
for i in range(L+1):
    for f,p,x in  imos[i]:
        if f:
            heapq.heappush(que, (p, x))
        else:
            valid_priority[p] = False
    
    while que[0][1]!=-1 and valid_priority[que[0][0]]==False:
        heapq.heappop(que)
    mapping[i] = que[0][1]

for d in D:
    d1 = bisect.bisect_left(vals, d)
    print(mapping[d1])