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.



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

Submission status: Time Limit Exceeded

Solution code:
import heapq
N,Q = map(int, input().split())

S,T,X = [],[],[]

Ev = []
for _ in range(N):
  s,t,x = map(int, input().split())
  Ev.append((s-x,True,x))
  Ev.append((t-x,False,x))
"""
2 5 6
5 -1
4 2
3 3
2 4
1 5
0 -1
"""
Ev.sort()
#print(Ev)
# C++のSetはminもO(logN)で取れるが、Pythonは無理。
# setとheapqを併用すると計算量が実現できる。
h = []
closed = set()
eidx = 0
for i in range(Q):
  # dはsortedでinputされる。
  d = int(input())
  #Query.append(d)
  while eidx < 2*N and Ev[eidx][0] <= d:
    #pop
    t,e,x = Ev[eidx]
    eidx += 1
    if e:
      heapq.heappush(h, x)
      closed.add(x)
    else:
      closed.remove(x)
      
  # heqpqの最小値がsetに含まれている間、捨て続ければ、setの要素とheapqの要素が一致する
  while h and h[0] not in closed:
    heapq.heappop(h)
    
  # assert( len(h) == len(set) )
  if h:
    print(h[0])
  else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
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))
"""
2 5 6
5 -1
4 2
3 3
2 4
1 5
0 -1
"""
Ev.sort()
#print(Ev)
# C++のSetはminもO(logN)で取れるが、Pythonは無理。
# setとheapqを併用すると計算量が実現できる。
h = []
closed = set()
eidx = 0
for i in range(Q):
  # dはsortedでinputされる。
  d = int(input())
  #Query.append(d)
  while eidx < 2*N and Ev[eidx][0] <= d:
    #pop
    t,e,x = Ev[eidx]
    eidx += 1
    if e:
      heapq.heappush(h, x)
      closed.add(x)
    else:
      closed.remove(x)
      
  # heqpqの最小値がsetに含まれている間、捨て続ければ、setの要素とheapqの要素が一致する
  while h and h[0] not in closed:
    heapq.heappop(h)
    
  # assert( len(h) == len(set) )
  if h:
    print(h[0])
  else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
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 = []
    now = set()
    already = dict()
    
    index = 0
    ans = -1
    for i in range(q):
        d = int(input())
        for i in range(index, 2*n):
            s, j, x = key[i]
            if s > d:
                index = i
                break
            if j == 1:
                heappush(judge, x)
                now = now.union({x})
            else:
                now.discard(x)
                if x in already:
                    already[x] += 1
                else:
                    already[x] = 1
                    
                    
        while judge:
            if judge[0] in already and already[judge[0]] > 0:
                already[judge[0]] -= 1
                heappop(judge)
            else:
                break
        if judge:
            ans = judge[0]
        else:
            ans = -1      
            
        print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
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 = []
    now = set()
    already = dict()
    
    index = 0
    ans = -1
    for i in range(q):
        d = int(input())
        for i in range(index, 2*n):
            s, j, x = key[i]
            if s > d:
                index = i
                break
            if j == 1:
                heappush(judge, x)
                now = now.union({x})
            else:
                now.discard(x)
                if x in already:
                    already[x] += 1
                else:
                    already[x] = 1
                    
                    
        while judge:
            if judge[0] in already and already[judge[0]] > 0:
                already[judge[0]] -= 1
                heappop(judge)
            else:
                break
        if judge:
            ans = judge[0]
        else:
            ans = -1      
            
        print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
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 = []
    now = set()
    already = dict()
    search = []
    
    for i in range(n*2):
        s, j, x = key[i]
        
        if j == 1:
            heappush(judge, x)
            now = now.union({x})
        else:
            now.discard(x)
            if 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])

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

inf = 10**15
PFX = [[(s-x,True,x),(t-x,False,x)] for s,t,x in STX]
PFX.append([(-inf,True,inf),(inf,False,inf)])
PFX = sorted(sum(PFX, []))

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)

Submission status: Time Limit Exceeded

Solution code:
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)
  # 出発時刻が[l,r)の人の進む距離が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()
ans=[-1]*q
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])

#print(dct)

Submission status: Time Limit Exceeded

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

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

#T-X, S-X, X
current_block = [(INF, INF, INF)] #sentinel
current_min_pair = (INF, INF, INF)

for D in Ds:
    while future_block[0][0] <= D:
        s_x, t_x, x = heappop(future_block)
        if current_min_pair[2] > x:
            current_min_pair = (t_x, s_x, x)
        heappush(current_block, (t_x, s_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[2])

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

Submission status: Time Limit Exceeded

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

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

#T-X, S-X, X
current_block = [(INF, INF, INF)] #sentinel
current_min_pair = (INF, INF, INF)

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

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from operator import itemgetter
import sys
input = sys.stdin.readline
#参考
#https://atcoder.jp/contests/abc128/submissions/15199101
class PseudoSet():
    def __init__(self):
        self.s = []  # set
        self.e = []  # erase candidate

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def sl_insert(vals:list, new_val):
    index = sl_indexof(vals, new_val)
    if index < 0:
        index = -index
    vals.insert(index, new_val)   
    return
def sl_remove(vals:list, new_val):
    index = sl_indexof(vals, new_val)
    if index < 0:
        return
    del vals[index]
    return

def sl_indexof(vals:list, new_val):
    l = 0
    r = len(vals)
    while l < r:
        m = (l + r) // 2
        if vals[m] == new_val:
            return m
        elif vals[m] < new_val:
            l = m + 1
        else:
            r = m
    return -l

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 = []
for t, kind, x in events:
    if kind == 0:
        sl_remove(working, x)
    elif kind == 1:
        sl_insert(working, x)
    elif any(working):
        dist[x] = working[0]
    else:
        walker.append(x)

for d in dist:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
def sl_insert(vals:list, new_val):
    l = 0
    r = len(vals)
    while l < r:
        m = (l + r) // 2
        if vals[m] == new_val:
            vals.insert(m, new_val)
            return
        elif vals[m] < new_val:
            l = m + 1
        else:
            r = m
    vals.insert(l, new_val)
    return

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 = []
for t, kind, x in events:
    if kind == 0:
        working.remove(x)
    elif kind == 1:
        sl_insert(working, x)
    elif any(working):
        dist[x] = working[0]
    else:
        walker.append(x)

for d in dist:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
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()
for t, kind, x in events:
    if kind == 0:
        working.remove(x)
    elif kind == 1:
        working.add(x)
    elif any(working):
        dist[x] = min(working)
    else:
        walker.append(x)

for d in dist:
    print(str(d))

Submission status: Time Limit Exceeded

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

D_list=[int(input()) for _ in range(Q)]


event.sort()
for d in D_list:
    stop_set=set()
    for e in event:
        if e[0]>d:
            break
        else :
            if e[1]==1:
                stop_set=stop_set|{e[2]}
            elif e[1]==-1:
                stop_set=stop_set-{e[2]}
    if stop_set==set():
        stop_set=stop_set|{-1}
    print(min(stop_set))

Submission status: Time Limit Exceeded

Solution code:
#abc128
N,Q=map(int,input().split())
stop_list=[list(map(int,input().split())) for _ in range(N)]
D_list=[int(input()) for _ in range(Q)]

N_line=dict()

for i in stop_list:
    N_line[i[2]]=[]

for i in stop_list:
    N_line[i[2]].append([i[0]-0.5,i[1]-0.5])

N_line=sorted(N_line.items(), key=lambda x:x[0])
D_achieve=[]


for d in D_list:
    judge=False
    for N in N_line:
        c_number=N[0]
        #N[0]は座標、N[1]は時間のリスト
        for time in N[1]:
            if time[0]<c_number+d<time[1]:
                D_achieve.append(c_number)
                judge=True
            if judge:
                break
        if judge:
            break
    if judge==False:
        D_achieve.append(-1)

        
        
for i in D_achieve:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class VanEmdeBoasTree:
    def __init__(self, size):
        self.universe_size = 1 << size.bit_length()
        self.minimum = -1
        self.maximum = -1
        self.summary = None
        self.cluster = {}
    
    def __high(self, x):
        return x // ceil(self.universe_size ** 0.5)
    
    def __low(self, x):
        return x % ceil(self.universe_size ** 0.5)
    
    def __generate_index(self, x, y):
        return x * ceil(self.universe_size ** 0.5) + y
    
    def __empinsert(self, key):
        self.minimum = self.maximum = key
    
    def insert(self, key):
        if self.minimum == -1:
            self.minimum = self.maximum = key
        else:
            if key < self.minimum:
                self.minimum, key = key, self.minimum
            if 2 < self.universe_size:
                if self.__high(key) not in self.cluster:
                    self.cluster[self.__high(key)] = VanEmdeBoasTree(ceil(self.universe_size ** 0.5))
                    if self.summary is None:
                        self.summary = VanEmdeBoasTree(ceil(self.universe_size ** 0.5))
                    self.summary.insert(self.__high(key))
                    self.cluster[self.__high(key)].__empinsert(self.__low(key))
                else:
                    self.cluster[self.__high(key)].insert(self.__low(key))
            if self.maximum < key:
                self.maximum = key
    
    def is_member(self, key):
        if self.minimum == key or self.maximum == key:
            return True
        elif self.universe_size == 2:
            return False
        else:
            if self.__high(key) in self.cluster:
                return self.cluster[self.__high(key)].is_member(self.__low(key))
            else:
                return False
    
    def successor(self, key):
        # バグらせてるっぽい
        if self.universe_size == 2:
            if key == 0 and self.maximum == 1:
                return 1
            else:
                return -1
        elif self.minimum != -1 and key < self.minimum:
            return self.minimum
        else:
            max_incluster = -1
            if self.__high(key) in self.cluster:
                max_incluster = self.cluster[self.__high(key)].maximum
            if max_incluster != -1 and self.__low(key) < max_incluster:
                offset = self.cluster[self.__high(key)].successor(self.__low(key))
                return self.__generate_index(self.__high(key), offset)
            else:
                succ_cluster = -1
                if self.summary.successor is not None:
                    succ_cluster = self.summary.successor(self.__high(key))
                if succ_cluster == -1:
                    return -1
                else:
                    offset = self.cluster[succ_cluster].minimum
                    return self.__generate_index(succ_cluster, offset)
    
    def predecessor(self, key):
        if self.universe_size == 2:
            if key == 1 and self.minimum == 0:
                return 0
            else:
                return -1
        elif self.maximum != -1 and self.maximum < key:
            return self.maximum
        else:
            min_incluster = -1
            if self.__high(key) in self.cluster:
                min_incluster = self.cluster[self.__high(key)].minimum
            if min_incluster != -1 and min_incluster < self.__low(key):
                offset = self.cluster[self.__high(key)].predecessor(self.__low(key))
                return self.__generate_index(self.__high(key), offset)
            else:
                pred_cluster = -1
                if self.summary is not None:
                    pred_cluster = self.summary.predecessor(self.__high(key))
                if pred_cluster == -1:
                    if self.minimum != -1 and self.minimum < key:
                        return self.minimum
                    else:
                        return -1
                else:
                    offset = self.cluster[pred_cluster].maximum
                    return self.__generate_index(pred_cluster, offset)
    
    def delete(self, key):
        if self.minimum == self.maximum:
            self.minimum = self.maximum = -1
            return True
        elif self.universe_size == 2:
            if key == 0:
                self.minimum = 1
            else:
                self.minimum = 0
            self.maximum = self.minimum
            return False
        else:
            if key == self.minimum:
                first_cluster = self.summary.minimum
                key = self.__generate_index(first_cluster, self.cluster[first_cluster].minimum)
                self.minimum = key
            flg0 = self.cluster[self.__high(key)].delete(self.__low(key))
            if flg0:
                del self.cluster[self.__high(key)]
                flg1 = self.summary.delete(self.__high(key))
                if key == self.maximum:
                    if flg1:
                        self.maximum = self.minimum
                    else:
                        max_insummary = self.summary.maximum
                        self.maximum = self.__generate_index(max_insummary, self.cluster[max_insummary].maximum)
            elif key == self.maximum:
                self.maximum = self.__generate_index(self.__high(key), self.cluster[self.__high(key)].maximum)


def solve():
    N, Q = map(int, rl().split())
    events = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        events.append((t - x, 0, x))
        events.append((s - x, 1, x))
    for _ in range(Q):
        events.append((int(rl()), 2, -1))
    events.sort(key=itemgetter(0, 1))
    
    ans = []
    veb = VanEmdeBoasTree(10 ** 9)
    for _, com, pos in events:
        if com == 0:
            veb.delete(pos)
        elif com == 1:
            veb.insert(pos)
        else:
            ans.append(veb.minimum)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class VanEmdeBoasTree:
    def __init__(self, size):
        self.universe_size = 1
        while self.universe_size < size:
            self.universe_size <<= 1
        self.minimum = -1
        self.maximum = -1
        self.summary = None
        self.cluster = {}
    
    def __high(self, x):
        return x // ceil(self.universe_size ** 0.5)
    
    def __low(self, x):
        return x % ceil(self.universe_size ** 0.5)
    
    def __generate_index(self, x, y):
        return x * ceil(self.universe_size ** 0.5) + y
    
    def min(self):
        return self.minimum
    
    def max(self):
        return self.maximum
    
    def __empinsert(self, key):
        self.minimum = self.maximum = key
    
    def insert(self, key):
        if self.minimum == -1:
            self.minimum = self.maximum = key
        else:
            if key < self.minimum:
                self.minimum, key = key, self.minimum
            if 2 < self.universe_size:
                if self.__high(key) not in self.cluster:
                    self.cluster[self.__high(key)] = VanEmdeBoasTree(ceil(self.universe_size ** 0.5))
                    if self.summary is None:
                        self.summary = VanEmdeBoasTree(ceil(self.universe_size ** 0.5))
                    self.summary.insert(self.__high(key))
                    self.cluster[self.__high(key)].__empinsert(self.__low(key))
                else:
                    self.cluster[self.__high(key)].insert(self.__low(key))
            if self.maximum < key:
                self.maximum = key
    
    def is_member(self, key):
        if self.minimum == key or self.maximum == key:
            return True
        elif self.universe_size == 2:
            return False
        else:
            if self.__high(key) in self.cluster:
                return self.cluster[self.__high(key)].is_member(self.__low(key))
            else:
                return False
    
    def successor(self, key):
        # バグらせてるっぽい
        if self.universe_size == 2:
            if key == 0 and self.maximum == 1:
                return 1
            else:
                return -1
        elif self.minimum != -1 and key < self.minimum:
            return self.minimum
        else:
            max_incluster = -1
            if self.__high(key) in self.cluster:
                max_incluster = self.cluster[self.__high(key)].max()
            if max_incluster != -1 and self.__low(key) < max_incluster:
                offset = self.cluster[self.__high(key)].successor(self.__low(key))
                return self.__generate_index(self.__high(key), offset)
            else:
                succ_cluster = -1
                if self.summary.successor is not None:
                    succ_cluster = self.summary.successor(self.__high(key))
                if succ_cluster == -1:
                    return -1
                else:
                    offset = self.cluster[succ_cluster].min()
                    return self.__generate_index(succ_cluster, offset)
    
    def predecessor(self, key):
        if self.universe_size == 2:
            if key == 1 and self.minimum == 0:
                return 0
            else:
                return -1
        elif self.maximum != -1 and self.maximum < key:
            return self.maximum
        else:
            min_incluster = -1
            if self.__high(key) in self.cluster:
                min_incluster = self.cluster[self.__high(key)].min()
            if min_incluster != -1 and min_incluster < self.__low(key):
                offset = self.cluster[self.__high(key)].predecessor(self.__low(key))
                return self.__generate_index(self.__high(key), offset)
            else:
                pred_cluster = -1
                if self.summary is not None:
                    pred_cluster = self.summary.predecessor(self.__high(key))
                if pred_cluster == -1:
                    if self.minimum != -1 and self.minimum < key:
                        return self.minimum
                    else:
                        return -1
                else:
                    offset = self.cluster[pred_cluster].max()
                    return self.__generate_index(pred_cluster, offset)
    
    def delete(self, key):
        if self.minimum == self.maximum:
            self.minimum = self.maximum = -1
            return True
        elif self.universe_size == 2:
            if key == 0:
                self.minimum = 1
            else:
                self.minimum = 0
            self.maximum = self.minimum
            return False
        else:
            if key == self.minimum:
                first_cluster = self.summary.min()
                key = self.__generate_index(first_cluster, self.cluster[first_cluster].min())
                self.minimum = key
            flg0 = self.cluster[self.__high(key)].delete(self.__low(key))
            if flg0:
                del self.cluster[self.__high(key)]
                flg1 = self.summary.delete(self.__high(key))
                if key == self.maximum:
                    if flg1:
                        self.maximum = self.minimum
                    else:
                        max_insummary = self.summary.max()
                        self.maximum = self.__generate_index(max_insummary, self.cluster[max_insummary].max())
            elif key == self.maximum:
                self.maximum = self.__generate_index(self.__high(key), self.cluster[self.__high(key)].max())


def solve():
    N, Q = map(int, rl().split())
    events = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        events.append((t - x, 0, x))
        events.append((s - x, 1, x))
    for _ in range(Q):
        d = int(rl())
        events.append((d, 2, -1))
    events.sort(key=itemgetter(0, 1))
    
    ans = []
    veb = VanEmdeBoasTree(10 ** 9)
    for _, com, pos in events:
        if com == 0:
            veb.delete(pos)
        elif com == 1:
            veb.insert(pos)
        else:
            ans.append(veb.min())
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()