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

from heapq import heappop, heappush
from collections import defaultdict

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

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

for i in range(Q):
    l_append((int(input()), 2, i))

lst.sort()
ans = [-1] * Q


se = set()
se_hp = [] 




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

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

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

from heapq import heappop, heappush
from collections import defaultdict

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

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

for i in range(Q):
    l_append((int(input()), 2, i))

lst.sort()
ans = [-1] * Q


se = set()
se_hp = [] 


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

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

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

from heapq import heappop, heappush
from collections import defaultdict

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

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

for i in range(Q):
    lst.append((int(input()), 2, i))

lst.sort()
ans = [-1] * Q


se = set()
se_hp = [] 


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

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

Solution (Python):
from bisect import bisect_left

N, Q = map(int, input().split())
R = [tuple(map(int, input().split())) for i in range(N)]
R.sort(key=lambda r: r[2])
q = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * (Q + 1)

for s, t, x in R:
    l = bisect_left(q, s - x)
    r = bisect_left(q, t - x)
    while l < r:
        if skip[l] == -1:
            skip[l] = r
            ans[l] = x
            l += 1
        else:
            l = skip[l]
for i in range(Q):
    print(ans[i])

Solution (Python):
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 - 0.25, 1, position)
        event_list[2 * i + 1] = (fin - position - 0.75, 0, position)
    event_list.sort(key=lambda x: x[0])

    ans = 10 ** 9 + 1
    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)
                ans = min(ans, position)
            else:
                now_kouji.remove(position)
                if len(now_kouji) == 0:
                    ans = 10 ** 9 + 1
                elif ans == position:
                    ans = min(now_kouji)

            now_ind += 1
        if ans == 10 ** 9 + 1:
            print(-1)
        else:
            print(ans)





if __name__ == '__main__':
    main()

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

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


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


if __name__ == '__main__':
  main()

Solution (Python):
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())

S = [None] * N
T = [None] * N
X = [None] * N
for i in range(N):
    S[i], T[i], X[i] = map(int, input().split())

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
    

roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks, key=lambda x: x[0])



walkers = D[:]
ans = [-1] * Q
skip = [-1] * Q

import bisect
for x, s, t in roadworks:
    left = bisect.bisect_left(walkers, s - x)
    right = bisect.bisect_left(walkers, t - x)
    
    i = left
    while i < right:
        if skip[i] == -1:
            ans[i] = x
            skip[i] = right
            i += 1
        else:
            i = skip[i]

    

for a in ans:
    print(a)

Solution (Python):
from bisect import bisect_left

def solve(n, q, s, t, x, d):
    v = sorted(list(zip(s, t, x)), key=lambda _:_[2])
    res = [-1] * q
    jump = [-1] * q
    for s, t, x in v:
        l = bisect_left(d, s - x)
        r = bisect_left(d, t - x)
        while l < r:
            s = jump[l]
            if s == -1:
                res[l] = x
                jump[l] = r
                l += 1
            else:
                l = s
    return res

n, q = map(int, input().split())
s = [-1] * n
t = [-1] * n
x = [-1] * n
for i in range(n):
    s[i], t[i], x[i] = map(int, input().split())
d = [int(input()) for i in range(q)]

print(*solve(n, q, s, t, x , d), sep="\n")

Solution (Python):
import bisect
import heapq
import sys
N,Q = [int(x) for x in sys.stdin.readline().split()]

hitos = []
ans = [-1 for _ in range(Q)]
queries =[]
jump = ans[::]



queries = [[int(x) for x in sys.stdin.readline().split()] for i in range(N)]
hitos = [int(sys.stdin.readline()) for i in range(Q)]



    
    
    
    


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





for l,r,x in queries:
     lind  = bisect.bisect_left(hitos,l-x - 0.5)
     rind  = bisect.bisect_left(hitos,r -x - 0.5)
     while lind < rind:
         if ans[lind] == -1:
            ans[lind] = x
            jump[lind] = rind
            lind += 1
         else:

             lind = jump[lind]

for i  in ans:
    print(i)

Solution (Python):
import bisect
import heapq
import sys
N,Q = [int(x) for x in sys.stdin.readline().split()]

hitos = []
ans = [-1 for _ in range(Q)]
queries =[]
jump = ans[::]



queries = [[int(x) for x in sys.stdin.readline().split()] for i in range(N)]
hitos = [int(sys.stdin.readline()) for i in range(Q)]



    
    
    
    


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





for l,r,x in queries:
     lind  = bisect.bisect_left(hitos,l-x - 0.5)
     rind  = bisect.bisect_left(hitos,r -x - 0.5)
     while lind < rind:
         if ans[lind] == -1:
            ans[lind] = x
            jump[lind] = rind
            lind += 1
         else:
             temp = jump[lind]
             jump[lind] = rind
             lind = temp

for i  in ans:
    print(i)

Solution (Python):
import bisect
import heapq
import sys
N,Q = [int(x) for x in sys.stdin.readline().split()]

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



queries = [[int(x) for x in sys.stdin.readline().split()] for i in range(N)]
hitos = [int(sys.stdin.readline()) for i in range(Q)]



    
    
    
    


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





for l,r,x in queries:
     lind  = bisect.bisect_left(hitos,l-x - 0.5)
     rind  = bisect.bisect_left(hitos,r -x - 0.5)
     while lind < rind:
         if ans[lind] == -1:
            ans[lind] = x
            jump[lind] = rind
            lind += 1
         else:
             temp = jump[lind]
             jump[lind] = rind
             lind = temp

for i  in ans:
    print(i)

Solution (Python):

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


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


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


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


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


def E():
    n,q = LI()
    a = LIR(n)
    a.sort(key = lambda x : x[2])
    d = IR(q)
    ans = [-1]*(q+1)
    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[:-1], sep = "\n")
    return


def F():
    n = I()

    return


if __name__ == "__main__":
    E()

Solution (Python):

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


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


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


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


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


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-0.1,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


def F():
    n = I()

    return


if __name__ == "__main__":
    E()

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

N,Q=map(int,input().split())
H=[]
for i in range(N):
    s,t,x=map(int,input().split())
    H.append([s-x,t-x,x])
H.sort()

P=0
q=[]
heapq.heapify(q)
for i in range(Q):
    n=int(input())
    
    if P<N:
        while H[P][0]<=n:
            heapq.heappush(q,[H[P][2],H[P][0],H[P][1]])
            P+=1
            if P==N:
                break
    
    if len(q)>0:
        while q[0][2]<=n:
            heapq.heappop(q)
            if len(q)==0:
                break
    if len(q)==0:
        print(-1)
    else:
        print(q[0][0])

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

Solution (Python):
import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    S, T, X = list(map(int, input().split()))
    STX.append((X, S, T))
STX = sorted(STX, key=lambda x: x[0])

for i in range(Q):
    D.append(int(input()))

skip = [-1]*Q

dist = [-1]*Q

for X, S, T in STX:
    s = S - X
    t = T - X - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    
    j = a
    while j < b:
        if skip[j] == -1:
            skip[j] = b
            dist[j] = X
            j+=1
        else:
            j=skip[j]


for i in range(Q):
    print(dist[i])

Solution (Python):
import sys
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))


"""
from bisect import bisect_left, bisect_right  
def main():
    N, Q = i2nn()
    STX = ii2nnn(N) 
    D = ii2nn(Q)    
    E = [-1] * Q
    STX.sort(key=lambda v: v[2])
    for s, t, x in STX:
        a = bisect_left(D, s-x)
        b = bisect_left(D, t-x)
        for i in range(a, b):
            if E[i] == -1:
                E[i] = x
    for e in E:
        print(e)
"""

def main():
    N, Q = i2nn()
    STX = ii2nnn(N) 
    D = ii2nn(Q)    

    events = []
    for s, t, x in STX:
        events.append(('S', s-x-0.25, x))
        events.append(('T', t-x-0.75, x))  
    for i, d in enumerate(D):
        events.append(('D', d, i))
    
    ans = [-1] * Q
    events.sort(key=lambda v: v[1])
    xset = set()
    xmin = 1e+10
    for event, time, xi in events:
        if event == 'S':
            xset.add(xi)
            if xmin > xi:
                xmin = xi
        elif event == 'T':
            xset.remove(xi)
            if xmin == xi:
                if xset:
                    xmin = min(xset)
                else:
                    xmin = 1e+10
        elif event == 'D' and xset:
            ans[xi] = xmin

    for n in ans:
        print(n)

main()

Solution (Python):
import sys
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))


"""
from bisect import bisect_left, bisect_right  
def main():
    N, Q = i2nn()
    STX = ii2nnn(N) 
    D = ii2nn(Q)    
    E = [-1] * Q
    STX.sort(key=lambda v: v[2])
    for s, t, x in STX:
        a = bisect_left(D, s-x)
        b = bisect_left(D, t-x)
        for i in range(a, b):
            if E[i] == -1:
                E[i] = x
    for e in E:
        print(e)
"""

def main():
    N, Q = i2nn()
    STX = ii2nnn(N) 
    D = ii2nn(Q)    

    events = []
    for s, t, x in STX:
        events.append(('S', s-x-0.25, x))
        events.append(('T', t-x-0.75, x))  
    for i, d in enumerate(D):
        events.append(('D', d, i))
    
    ans = [-1] * Q
    events.sort(key=lambda v: v[1])
    xset = set()
    
    xmin = 1e+10
    xb = False
    for event, time, xi in events:
        if event == 'S':
            xset.add(xi)
            
            if xmin > xi:
                xmin = xi
                xb = True
        elif event == 'T':
            xset.remove(xi)
            if xmin == xi:
                
                xb = False
        elif event == 'D' and xset:
            
            if not xb:
                xmin = min(xset)
                xb = True
            ans[xi] = xmin

    for n in ans:
        print(n)

main()

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

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

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

Solution (Python):
from operator import itemgetter
import sys

input = sys.stdin.readline
inf = float('inf')

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

e = []
for _ in range(n):
    s, t, x = map(int, input().split())
    
    e.append((s - x, x, 0))  
    e.append((t - x - 0.5, x, 1))  
e.sort(key=itemgetter(0))

stop_set = set()
stop_at = inf
cur = 0
for _ in range(q):
    changed = False
    d = int(input())
    while cur < n * 2:
        exec_time, pos, typ = e[cur]
        if exec_time <= d:
            if typ == 0:
                stop_set.add(pos)
                if (not changed) and (pos < stop_at):
                    stop_at = pos
            else:
                stop_set.remove(pos)
                if (not changed) and (pos == stop_at):
                    changed = True
            cur += 1
        else:
            break

    if changed:
        if stop_set:
            stop_at = min(stop_set)
        else:
            stop_at = inf

    print(stop_at if stop_at != inf else -1)

Solution (Python):

import sys
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right

N,Q=map(int, sys.stdin.readline().split())

S=[]
event=[]	
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	heappush( event, (x, max(0,s-x) , max(0,t-1-x)) )


D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]
D.sort()
ans=[ float("inf") for _ in range(Q) ]

Next=[ i+1 for i in range(Q) ]	


while event:
	x,s,t=heappop(event)
	start=bisect_left(D,s)
	end=bisect_right(D,t)

	i=start
	while i<end:
		ans[i]=min(ans[i],x)
		next=Next[i]
		Next[i]=end
		i=next

for x in ans:
	if x==float("inf"):
		print -1
	else:
		print x

Solution (Python):
from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import bisect

input = sys.stdin.readline

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

STX = [list(map(int, input().split())) for _ in range(N)]

STX = sorted(STX, key=lambda x: x[2])

D = [int(input()) for _ in range(Q)]
ans = [-1] * Q
index = [-1] * Q
for s, t, x in STX:
    left = bisect.bisect_left(D, s - x - 0.5)
    right = bisect.bisect_left(D, t - x - 0.5)
    now = left
    while now < right:
        if index[now] == -1:  
            ans[now] = x
            index[now] = right
            now += 1
        else:
            now = index[now]
            

for a in ans:
    print(a)

Solution (Python):
import sys
import bisect

sys.setrecursionlimit(10**8)

class SegmentTree(object):  
    def __init__(self, size, value):
        self.len = 1 << size.bit_length()
        self.default = value
        
        self.array = [value] * (2 * self.len)

    def get(self, i):
        i += self.len
        ans = self.default
        while i > 0:
            ans = min(self.array[i], ans)
            i >>= 1
        return ans

    def query(self, l, r, v, i, a, b):
        if self.array[i] != self.default:
            return 0
        if l == a and r == b:
            self.array[i] = v
            return 0
        center = (a + b) // 2
        if center >= r:
            return self.query(l, r, v, i * 2, a, center)
        elif center <= l:
            return self.query(l, r, v, i * 2 + 1, center, b) 
        else:
            return min(
                self.query(l, center, v, i * 2, a, center),
                self.query(center, r, v, i * 2 + 1, center, b))

    def update(self, l, r, v):
        return self.query(l, r, v, 1, 0, self.len)


input = sys.stdin.readline

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

STX_array = [list(map(int, input().split())) for _ in range(N)]

STX_array = sorted(STX_array, key=lambda x: x[2])

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

index_array = [i for i in range(Q)]

INF = 10**9 + 7

seg_tree = SegmentTree(Q, INF)

for STX in STX_array:
    s, t, x = STX
    index_left = bisect.bisect_left(Q_array, s - 0.5 - x)
    index_right = bisect.bisect_left(Q_array, t - 0.5 - x)
    if index_left != index_right:
        seg_tree.update(index_left, index_right, x)

for i in range(Q):
    ans = seg_tree.get(i)
    print(ans) if ans != INF else print(-1)

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

Solution (Python):
import sys
import bisect

input = sys.stdin.readline

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

STX_array = [list(map(int, input().split())) for _ in range(N)]

STX_array = sorted(STX_array, key=lambda x: x[2])

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

index_array = [i for i in range(Q)]

ans_array = [-1] * Q
for STX in STX_array:
    s, t, x = STX
    index_left = bisect.bisect_left(Q_array, s - 0.5 - x)
    index_right = bisect.bisect_left(Q_array, t - 0.5 - x)
    if index_left != index_right:
        now_index = index_left
        while now_index < index_right:
            if index_array[now_index] == now_index:
                ans_array[now_index] = x
                index_array[now_index] = index_right
                now_index += 1
            else:
                old_index = now_index
                now_index = index_array[now_index]
                index_array[old_index] = now_index




for ans in ans_array:
    print(ans)