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: Runtime Error

Solution code:
import std.algorithm;
import std.container;
import std.conv;
import std.functional;
import std.math;
import std.meta;
import std.random;
import std.range;
import std.stdio;
import std.string;
import std.traits;
import std.typecons;

alias Event = Tuple!(long, "t", long, "id", string, "type", long, "value");
alias Cand = Tuple!(long, "value", long, "id");

auto solve(long N, long Q, long[] S, long[] T, long[] X, long[] D) {
    auto events = make!(RedBlackTree!Event);
    foreach (s, t, x, n; zip(S, T, X, iota(N))) {
        events.insert(Event(s - x, n, "add", x));
        events.insert(Event(t - x, n, "dispose", x));
    }

    auto cands = make!(RedBlackTree!Cand);
    auto disposed = make!(RedBlackTree!long);
    foreach (d; D) {
        while (!events.empty && events.front.t <= d) {
            auto e = events.front;
            events.removeFront;

            if (e.type == "add")
                cands.insert(Cand(e.value, e.id));
            else
                disposed.insert(e.id);
        }

        while (!cands.empty && cands.front.id in disposed)
            cands.removeFront;

        if (cands.empty)
            writeln(-1);
        else
            writeln(cands.front.value);
    }
}

void main() {
    auto input = stdin.byLine.map!split.joiner;

    long N;
    N = input.front.to!long;
    input.popFront;

    long Q;
    Q = input.front.to!long;
    input.popFront;

    long[] S = new long[](cast(size_t) (N));
    long[] T = new long[](cast(size_t) (N));
    long[] X = new long[](cast(size_t) (N));
    foreach (i; 0 .. cast(size_t) (N)) {
        S[i] = input.front.to!long;
        input.popFront;
        T[i] = input.front.to!long;
        input.popFront;
        X[i] = input.front.to!long;
        input.popFront;
    }

    long[] D = new long[](cast(size_t) (Q));
    foreach (i; 0 .. cast(size_t) (Q)) {
        D[i] = input.front.to!long;
        input.popFront;
    }

    static if (is(ReturnType!solve == void))
        solve(N, Q, S, T, X, D);
    else
        solve(N, Q, S, T, X, D).writeln;
}

Submission status: Runtime Error

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math

def main():
    kouji_num, person_num = map(int, input().split())
    koji_data = [list(map(int, input().split())) for i in range(kouji_num)]
    person_data = [int(input()) for i in range(person_num)]

    event_list = [0 for i in range(kouji_num * 2)]
    now_kouji = set()

    for i in range(kouji_num):
        start, fin, position = koji_data[i]
        event_list[2 * i] = (start - position, 1, position)
        event_list[2 * i + 1] = (fin - position, 0, position)
    event_list.sort(key=lambda x: x[0])

    now_ind = 0
    for i in range(person_num):
        person_start = person_data[i]
        while now_ind < kouji_num * 2:
            time_data, flg, position = event_list[now_ind]
            if time_data > person_start:
                break
            if flg:
                now_kouji.add(position)
            else:
                now_kouji.remove(position)
            now_ind += 1
        if len(now_kouji) == 0:
            ans = -1
        else:
            ans = min(now_kouji)
        print(ans)





if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# coding: utf-8
from operator import itemgetter

N,Q = map(int, input().split())
events = [ [0,0,0] for i in range(N)]
S = [0]*N
T = [0]*N
X = [0]*N
for i in range(N):
	s, t, x = list(map(int, input().split()))
	events[i] = [s-x, t-x,x]
	
	S[i] = s-x
	T[i] = t-x
	X[i] = x
#events.sort(key=itemgetter(0,1))
d = [ int(input()) for i in range(Q)]

print("---------------")
#--------------------------------------------
import bisect
#A = [1, 2, 3, 3, 3, 4, 4, 6, 6, 6, 6]
#index = bisect.bisect_left(A, 5) # 2 最も左(前)の挿入箇所が返ってきている
#print(index)
#print(A)
#A.insert(index, 3)
#print(A)
#--------------------------------------------
SX = [0]*N
TX = [0]*N
for i in range(N):
	SX[i] = [S[i],X[i]]
	TX[i] = [T[i]-1,X[i]]
SX.sort()
TX.sort()
#print("SX:",*SX,sep="\n")
#print("TX:",*TX,sep="\n")
SX.append([999,-1])
TX.append([999,-1])

s = [row[0] for row in SX]
t = [row[0] for row in TX]

#print("d:",d)

#print("i","d","L", "","R","SX", "TX",sep="\t")
for i in range(Q):
	L = bisect.bisect_right(s, d[i])
	R = bisect.bisect_left(t, d[i])
	a = ">" if L > R else "-"
#	print(i,d[i],L, a, R,SX[L][1], TX[R][1],sep="\t")
	print(min(SX[L][1], TX[R][1]))

Submission status: Runtime Error

Solution code:
import sys,builtins,io 
def input(): 
    r = sys.stdin.readline().rstrip() 
    if not r: 
        r = builtins.input() 
        return r

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])
#print(roadworks)
 
# Dは入力時点でソート済み
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]
 
    
#print(walkers)
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
# このコメントを外さないとTLE
# import sys
# input = sys.stdin.readline

import sys,builtins,io 
def input(): 
    r = sys.stdin.readline() 
    if not r: 
        r = builtins.input() 
        return r
x = input()

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])
#print(roadworks)
 
# Dは入力時点でソート済み
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]
 
    
#print(walkers)
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
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())
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())
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks, reverse=True)
#print(roadworks)

from collections import defaultdict
stops = defaultdict(lambda: -1)
for x, s, t in roadworks:
    for i in range(s, t+1):
        i = max(0, i-x)
        stops[i] = x
#print(stops)
for d in D:
    print(stops[d+1])

Submission status: Runtime Error

Solution code:
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())
    
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks, key=lambda x: x[0])
#print(roadworks)

# Dは入力時点でソート済み
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]

    
#print(walkers)
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
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())
    
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks, reverse=True)
#print(roadworks)

from collections import defaultdict
stops = [-1]*(10**5)
for x, s, t in roadworks:
    tmp = [x] * ((t+1-x)-max(0, s-x))
    stops = stops[:max(0, s-x)]+tmp+stops[(t+1-x):]
#print(stops)
for d in D:
    print(stops[d+1])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Aug  9 00:23:59 2019

@author: miz18
"""

import sys
input = sys.stdin.readline

def main(): 
    N,Q = list(map(int,input().split()))
     
    road = []
    r_append = road.append
    x_list = []
    x_append = x_list.append
    for i in range(N):
        s,t,x = list(map(int,input().split()))
        r_append(("s",s-x,x,0))
        r_append(("t",t-x,x,0))
        x_append.append(x)
     
    for i in range(Q):
        d = int(input())
        r_append(("m",d,i,1))
     
    road.sort(lambda x:x[3])
    road.sort(lambda x:x[1])
     
    x_list = list(set(x_list))
    x_list.sort()
     
    x2i_dict = {}
    for i,x in enumerate(x_list):
        x2i_dict[x]=i
     
     
    class BIT:
                
        def __init__(self, L):
            self.N = len(L)
            self.bit = [0]*self.N
            for i,l in enumerate(L):
                self.add(i,l)
     
        def add(self, a, w):
            x = a + 1
            for i in range(1000):
                self.bit[x-1] += w
                x += x & -x
                if x > self.N:
                    break
     
        def sum(self, a):
            x = a+1
            ret = 0
            for i in range(1000):
                ret += self.bit[x-1]
                x -= x & -x
                if x <= 0:
                    break        
            return ret
     
    def bisectR(l,r,bit):
        while r-l>1:
            if bit.sum((l+r)//2)>0:
                r = (l+r)//2
            else:
                l = (l+r)//2
        return r
     
    
     
    bit = BIT([0]*len(x_list))
    b_add = bit.add
    
    ans = [0]*Q
    for r in road:
        if r[0]=="s":
            b_add(x2i_dict[r[2]],1)
        elif r[0]=="t":
            b_add(x2i_dict[r[2]],-1)
        else:
            if bit.sum(len(x_list)-1)==0:
                ans[r[2]]=-1
            elif bit.sum(0)>0:
                ans[r[2]]=x_list[0]
            else:
                i = bisectR(0,len(x_list)-1,bit)
                ans[r[2]] = x_list[i]
     
    for a in ans:
        print(a)
        
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:

import sys
input = sys.stdin.readline

def main():
    N,Q = list(map(int,input().split()))

    road = []
    x_list = []
    for i in range(N):
        s,t,x = list(map(int,input().split()))
        road.append((s-x,x,0))
        road.append((t-x,x,1))
        x_list.append(x)

    for i in range(Q):
        d = int(input())
        road.append((d,i,2))

    road.sort(lambda x:x[2])
    road.sort(lambda x:x[0])

    x_list = list(set(x_list))
    x_list.sort()

    x2i_dict = {}
    for i,x in enumerate(x_list):
        x2i_dict[x]=i


    class BIT:
            
        def __init__(self, L):
            self.N = len(L)
            self.bit = [0]*self.N
            for i,l in enumerate(L):
                self.add(i,l)

        def add(self, a, w):
            x = a + 1
            for i in range(1000):
                self.bit[x-1] += w
                 x += x & -x
                if x > self.N:
                    break

        def sum(self, a):
            x = a+1
            ret = 0
            for i in range(1000):
                ret += self.bit[x-1]
                x -= x & -x
                if x <= 0:
                    break        
           return ret


    bit = BIT([0]*xn)
    bitadd = bit.add
    bitsum = bit.sum
    def bisectR(l,r,bit):
        while r-l>1:
            if bitsum((l+r)//2)>0:
                r = (l+r)//2
            else:
                l = (l+r)//2
        return r

    xn=len(x_list)

    ans = [0]*Q
    for r in road:
        if r[2]==0:
             bitadd(x2i_dict[r[1]],1)
        elif r[2]==1:
            bitadd(x2i_dict[r[1]],-1)
        else:
            if bitsum(xn-1)==0:
               ans[r[1]]=-1
            elif bitsum(0)>0:
                ans[r[1]]=x_list[0]
            else:
                i = bisectR(0,xn-1)
                ans[r[1]] = x_list[r]
    for a in ans:
        print(a)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

import sys
input = sys.stdin.readline

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

road = []
x_list = []
for i in range(N):
    s,t,x = list(map(int,input().split()))
    road.append((s-x,x,0))
    road.append((t-x,x,1))
    x_list.append(x)

for i in range(Q):
    d = int(input())
    road.append((d,i,2))

road.sort(lambda x:x[2])
road.sort(lambda x:x[0])

x_list = list(set(x_list))
x_list.sort()

x2i_dict = {}
for i,x in enumerate(x_list):
    x2i_dict[x]=i


class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)

    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break

    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret


bit = BIT([0]*xn)

def bisectR(l,r,bit):
    while r-l>1:
        if bit.sum((l+r)//2)>0:
            r = (l+r)//2
        else:
            l = (l+r)//2
    return r

xn=len(x_list)

ans = [0]*Q
for r in road:
    if r[2]==0:
        bit.add(x2i_dict[r[1]],1)
    elif r[2]==1:
        bit.add(x2i_dict[r[1]],-1)
    else:
        if bit.sum(xn-1)==0:
            ans[r[1]]=-1
        elif bit.sum(0)>0:
            ans[r[1]]=x_list[0]
        else:
            i = bisectR(0,xn-1)
            ans[r[1]] = x_list[r]
for a in ans:
    print(a)

Submission status: Runtime Error

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

hitos = []
ans = [-1] * Q
queries =[]
jump = [-1] * Q


for i in range(N):
    S,T,X =list(map(int,input().split(" ")))
    lt = S -X -0.5
    rt = T -X -0.5
    queries.append((lt,rt,X)) #-1 → 挿入クエリ lが時間、-1がクエリの種類、Xが場所


queries.sort(key=lambda x:x[2])



for i in range(Q):
    t = int(input())
    hitos.append(t)
for l,r,x in queries:
     lind  = bisect.bisect_left(hitos,l)
     rind  = bisect.bisect_left(hitos,r)
     while lind < rind:
         if ans[lind] == -1:
            ans[lind] = x
            jump[lind] = rind
            lind += 1
         else:
             temp = jump[lind]
             jump[lind] = rind
             lind = tmp
ans = list(map(str,ans))
print("\n".join( ans))

Submission status: Runtime Error

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

hitos = []
ans = [-1] * Q
queries =[]
jump = [-1] * Q


for i in range(N):
    S,T,X =list(map(int,input().split(" ")))
    lt = S -X -0.5
    rt = T -X -0.5
    queries.append((lt,rt,X)) #-1 → 挿入クエリ lが時間、-1がクエリの種類、Xが場所


queries.sort(key=lambda x:x[2])



for i in range(Q):
    t = int(input())
    hitos.append(t)
for l,r,x in queries:
     lind  = bisect.bisect_left(hitos,l)
     rind  = bisect.bisect_left(hitos,r)
     while lind < rind:
         if ans[lind] == -1:
            ans[lind] = x
            jump[lind] = rind
            lind += 1
         else:
             lind = jump[lind]
print("\n".join(ans))

Submission status: Runtime Error

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

hitos = []
ans = [-1] * Q
queries =[]
heapq.heapify(queries)
events = set()
heapq.heapify(events)

for i in range(N):
    S,T,X =list(map(int,input().split(" ")))
    lt = S -X -0.5
    rt = T -X -0.5
    queries.append((lt,-1,X)) #-1 → 挿入クエリ lが時間、-1がクエリの種類、Xが場所
    queries.append((rt,1,X)) # 1 → 削除クエリ



for i in range(Q):
    t = int(input())
    queries.append((t,0,-99)) # 0 → チェッククエリ
queries.sort(key = lambda x:x[0])
for t,kind,x in queries:
    if kind == 0:
        if len(events) > 0:
            print(events[0])
        else:
            print(-1)
    if kind == -1:
        events.append(x)
    if kind == 1:
        if x in events:
            events.remove(x)

Submission status: Runtime Error

Solution code:
import bisect
N,Q = list(map(int,input().split(" ")))

hitos = []
ans = [-1] * Q
queries = []
events = set()
for i in range(N):
    S,T,X =list(map(int,input().split(" ")))
    lt = S -X -0.5
    rt = T -X -0.5
    queries.append((lt,-1,X)) #-1 → 挿入クエリ lが時間、-1がクエリの種類、Xが場所
    queries.append((rt,1,X)) # 1 → 削除クエリ


queries.sort(key = lambda x:x[2])

for i in range(Q):
    t = int(input())
    queries.append((t,0,-99)) # 0 → チェッククエリ
queries.sort(key = lambda x:x[0])
for t,kind,x in queries:
    if kind == 0:
        if len(events) > 0:
            print(min(events))
        else:
            print(-1)
    if kind == -1:
        events.add(x)
    if kind == 1:
        events.remove(x)

Submission status: Runtime Error

Solution code:
import bisect


N, Q = map(int, input().split())
works = [[0] * 2 for i in range(N)]

for i in range(N):
    works[i] = list(map(int, input().split()))

on_work = [[]*3 for _ in range(N*2)]
# works = sorted(works, key=lambda x: x[2])  # 2番目の要素(工事現場の座標)でソート

t_set = set()
for i in range(N):
    t_set = t_set | {works[i][0]-works[i][2], works[i][1]-works[i][2]}
    # ある座標で工事が始まったことを示す
    on_work[2*i] = ([works[i][0]-works[i][2], 1, works[i][2]])
    # ある座標で工事が終わったことを示す
    on_work[2*i+1] = ([works[i][1]-works[i][2], -1, works[i][2]])

people = [0 for i in range(Q)]
for i in range(Q):
    people[i] = int(input())

on_work = sorted(on_work, key=lambda x: x[0])  # 1番目の要素(時間)でソート
# print(on_work)
t_list = sorted(list(t_set))
state = {}
closed = set("")
index = 0
for t in t_list:

    while (on_work[index][0] == t):
        # print(on_work[index])

        if on_work[index][1] == 1:
            closed.add(on_work[index][2])
        else:
            closed.discard(on_work[index][2])
        # print(closed)
        index += 1
        if index == 2 * N:
            break
    state[t] = sorted(list(closed))


# print(state)


# # print(works)
# # print(people)

for start_time in people:
    temp = bisect.bisect_left(t_list, start_time)  # start_time以前で最新のindexを探す
    # print(temp)
    if temp >= t_list[-1]:
        temp -= 1
    target_time = t_list[temp]
    if state[target_time]:
        print(state[target_time][0])
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,p = LI()
    print((a*3+p)//2)
    return

#B
def B():
    n = I()
    s = [None for i in range(n)]
    for i in range(n):
        l = input().split()
        s[i] = l+[i]
    s.sort(key = lambda x:(x[0],-int(x[1])))
    for i,a,b in s:
        print(b+1)
    return

#C
def C():
    def dfs(d,k):
        if d == n:
            l.append(k)
        else:
            dfs(d+1,k+[0])
            dfs(d+1,k+[1])
    n,m = LI()
    l = []
    dfs(0,[])
    qu = LIR(m)
    p = LI()
    ans = 0
    for k in l:
        s = 0
        for q in range(m):
            num = qu[q][0]
            lis = list(map(lambda x:x-1, qu[q][1:]))
            su = 0
            for i in lis:
                su ^= k[i]
            if su == p[q]:
                s += 1
        if s == m:
            ans += 1
    print(ans)
    return

#D
def D():
    n,k = LI()
    v = LI()
    ans = -float("inf")
    for l in range(min(k,n)+1):
        for r in range(min(k,n)-l+1):
            m = 0
            q = v[:l]+v[n-r:]
            q.sort()
            res = max(0,k-r-l)
            for i in range(len(q)):
                if q[i] < 0 and res > 0:
                    res -= 1
                else:
                    m += q[i]
            if m > ans:
                ans = m
    print(ans)
    return

#E
def E():
    n,q = LI()
    a = LIR(n)
    a.sort(key = lambda x : x[2])
    d = IR(q)
    ans = [-1]*q
    right = [0]*q
    for s,t,x in a:
        l = bisect.bisect_left(d,s-x)
        r = bisect.bisect_left(d,t-x)
        while l < r:
            while ans[l] != -1:
                l = right[l]
            if r <= l:
                break
            ans[l] = x
            right[l] = r
            l += 1
    print(*ans, sep = "\n")
    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,p = LI()
    print((a*3+p)//2)
    return

#B
def B():
    n = I()
    s = [None for i in range(n)]
    for i in range(n):
        l = input().split()
        s[i] = l+[i]
    s.sort(key = lambda x:(x[0],-int(x[1])))
    for i,a,b in s:
        print(b+1)
    return

#C
def C():
    def dfs(d,k):
        if d == n:
            l.append(k)
        else:
            dfs(d+1,k+[0])
            dfs(d+1,k+[1])
    n,m = LI()
    l = []
    dfs(0,[])
    qu = LIR(m)
    p = LI()
    ans = 0
    for k in l:
        s = 0
        for q in range(m):
            num = qu[q][0]
            lis = list(map(lambda x:x-1, qu[q][1:]))
            su = 0
            for i in lis:
                su ^= k[i]
            if su == p[q]:
                s += 1
        if s == m:
            ans += 1
    print(ans)
    return

#D
def D():
    n,k = LI()
    v = LI()
    ans = -float("inf")
    for l in range(min(k,n)+1):
        for r in range(min(k,n)-l+1):
            m = 0
            q = v[:l]+v[n-r:]
            q.sort()
            res = max(0,k-r-l)
            for i in range(len(q)):
                if q[i] < 0 and res > 0:
                    res -= 1
                else:
                    m += q[i]
            if m > ans:
                ans = m
    print(ans)
    return

#E
def E():
    n,q = LI()
    a = LIR(n)
    a.sort(key = lambda x : x[2])
    d = IR(q)
    ans = [-1]*q
    right = [0]*q
    for s,t,x in a:
        print(s,t,x)
        l = bisect.bisect_left(d,s-x)
        r = bisect.bisect_left(d,t-x)
        while l < r:
            while ans[l] != -1:
                l = right[l]
            if r <= l:
                break
            ans[l] = x
            right[l] = r
            l += 1
    print(*ans, sep = "\n")
    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,p = LI()
    print((a*3+p)//2)
    return

#B
def B():
    n = I()
    s = [None for i in range(n)]
    for i in range(n):
        l = input().split()
        s[i] = l+[i]
    s.sort(key = lambda x:(x[0],-int(x[1])))
    for i,a,b in s:
        print(b+1)
    return

#C
def C():
    def dfs(d,k):
        if d == n:
            l.append(k)
        else:
            dfs(d+1,k+[0])
            dfs(d+1,k+[1])
    n,m = LI()
    l = []
    dfs(0,[])
    qu = LIR(m)
    p = LI()
    ans = 0
    for k in l:
        s = 0
        for q in range(m):
            num = qu[q][0]
            lis = list(map(lambda x:x-1, qu[q][1:]))
            su = 0
            for i in lis:
                su ^= k[i]
            if su == p[q]:
                s += 1
        if s == m:
            ans += 1
    print(ans)
    return

#D
def D():
    n,k = LI()
    v = LI()
    ans = -float("inf")
    for l in range(min(k,n)+1):
        for r in range(min(k,n)-l+1):
            m = 0
            q = v[:l]+v[n-r:]
            q.sort()
            res = max(0,k-r-l)
            for i in range(len(q)):
                if q[i] < 0 and res > 0:
                    res -= 1
                else:
                    m += q[i]
            if m > ans:
                ans = m
    print(ans)
    return

#E
def E():
    n,Q = LI()
    e = []
    for i in range(n):
        s,t,x = LI()
        e.append((s-x,x,1))
        e.append((t-x,x,0))
    e.sort(key = lambda x : x[0])
    m = 2*n
    q = set()
    j = 0
    ans = float("inf")
    for i in range(Q):
        d = I()
        while j < m:
            t,x,k = e[j]
            if d < t:
                break
            if k:
                q.add(x)
                if x < ans:
                    ans = x
            else:
                q.remove(x)
                if ans == x:
                    if q:
                        ans = min(q)
                    else:
                        ans = float("inf")
            j += 1
        print(-1 if ans == float("inf") else ans)
    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    E()