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 = lambda : sys.stdin.readline().rstrip()

def segfun(x, y):
    return min(x, y)
ide_ele = float("inf")


class SegmentTree:
    def __init__(self, n, ele, segfun):
        self.ide_ele = ele
        self.segfun = segfun
        self.n = n
        self.N0 = 1 << n.bit_length()
        self.data = [self.ide_ele] * (self.N0 * 2)
 
    def update(self, l, r, val):
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1:
                self.data[l] = self.segfun(self.data[l], val)
                l += 1
            if r & 1:
                self.data[r - 1] = self.segfun(self.data[r - 1], val)
                r -= 1
            l //= 2
            r //= 2
 
    def query(self, i):
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0:
            i //= 2
            ret = self.segfun(ret, self.data[i])
        return ret


n, q = map(int, input().split())
stx = []
for _ in range(n):
    s, t, x = map(int, input().split())
    stx.append([x, s - x, t - x])

d = [int(input()) for _ in range(q)]

import bisect

seg = SegmentTree(q, ide_ele, segfun)

for x, start, last in stx:
    l = bisect.bisect_left(d, start)
    r = bisect.bisect_left(d, last)
    seg.update(l, r, x)

for i, j in enumerate(d):
    res = seg.query(i)
    if res == float("inf"):
        print(-1)
    else:
        print(res)

Solution (Python):
def main():
    import sys
    input = lambda : sys.stdin.readline().rstrip()

    n, q = map(int, input().split())
    stx = []
    for _ in range(n):
        s, t, x = map(int, input().split())
        stx.append([x, s - x, t - x])
    stx.sort(reverse=True)
    d = [int(input()) for _ in range(q)]

    N = q
    N0 = 2**(N-1).bit_length()
    data = [None]*(2*N0)
    INF = (-1, 10**9 + 1)
    def update(l, r, v):
        L = l + N0; R = r + N0
        while L < R:
            if R & 1:
                R -= 1
                data[R-1] = v

            if L & 1:
                data[L-1] = v
                L += 1
            L >>= 1; R >>= 1
    def _query(k):
        k += N0-1
        s = INF
        while k >= 0:
            if data[k]:
                s = max(s, data[k])
            k = (k - 1) // 2
        return s
    def query(k):
        return _query(k)[1]



    import bisect

    for i, (x, start, last) in enumerate(stx):
        l = bisect.bisect_left(d, start)
        r = bisect.bisect_left(d, last)
        update(l, r, (i, x))

    for i in range(q):
        res = query(i)
        if res == 10**9 + 1:
            print(-1)
        else:
            print(res)
if __name__ == '__main__':
    main()

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

n, q = map(int, input().split())
stx = []
for _ in range(n):
    s, t, x = map(int, input().split())
    stx.append([x, s - x, t - x])
stx.sort(reverse=True)
d = [int(input()) for _ in range(q)]

N = q
N0 = 2**(N-1).bit_length()
data = [None]*(2*N0)
INF = (-1, 10**9 + 1)
def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
def query(k):
    return _query(k)[1]



import bisect

for i, (x, start, last) in enumerate(stx):
    l = bisect.bisect_left(d, start)
    r = bisect.bisect_left(d, last)
    update(l, r, (i, x))

for i in range(q):
    res = query(i)
    if res == 10**9 + 1:
        print(-1)
    else:
        print(res)

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

n, q = map(int, input().split())
stx = []
for _ in range(n):
    s, t, x = map(int, input().split())
    stx.append([x, s - x, t - x])
stx.sort(reverse=True)
d = [int(input()) for _ in range(q)]

N = q
N0 = 2**(N-1).bit_length()
data = [None]*(2*N0)
INF = (-1, 10**9 + 1)
def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
def query(k):
    return _query(k)[1]



import bisect

for i, (x, start, last) in enumerate(stx):
    l = bisect.bisect_left(d, start)
    r = bisect.bisect_left(d, last)
    update(l, r, (i, x))

for i, j in enumerate(d):
    res = query(i)
    if res == 10**9 + 1:
        print(-1)
    else:
        print(res)

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

class SegmentTree:
    def __init__(self, n, ele, segfun):
        self.ide_ele = ele
        self.segfun = segfun
        self.n = n
        self.N0 = 1 << n.bit_length()
        self.data = [self.ide_ele] * (self.N0 * 2)
 
    def update(self, l, r, val):
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1:
                self.data[l] = self.segfun(self.data[l], val)
                l += 1
            if r & 1:
                self.data[r - 1] = self.segfun(self.data[r - 1], val)
                r -= 1
            l //= 2
            r //= 2
 
    def query(self, i):
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0:
            i //= 2
            ret = self.segfun(ret, self.data[i])
        return ret

n, q = map(int, input().split())
stx = []
for _ in range(n):
    s, t, x = map(int, input().split())
    stx.append([x, s - x, t - x])

d = [int(input()) for _ in range(q)]

import bisect

seg = SegmentTree(q, 10**9 + 1, lambda a, b : min(a, b))

for x, start, last in stx:
    l = bisect.bisect_left(d, start)
    r = bisect.bisect_left(d, last)
    seg.update(l, r, x)

for i, j in enumerate(d):
    res = seg.query(i)
    if res == 10**9 + 1:
        print(-1)
    else:
        print(res)

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

class SegmentTree:
    def __init__(self, n, ele, segfun):
        self.ide_ele = ele
        self.segfun = segfun
        self.n = n
        self.N0 = 1 << n.bit_length()
        self.data = [self.ide_ele] * (self.N0 * 2)
 
    def update(self, l, r, val):
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1:
                self.data[l] = self.segfun(self.data[l], val)
                l += 1
            if r & 1:
                self.data[r - 1] = self.segfun(self.data[r - 1], val)
                r -= 1
            l //= 2
            r //= 2
 
    def query(self, i):
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0:
            i //= 2
            ret = self.segfun(ret, self.data[i])
        return ret

n, q = map(int, input().split())
stx = []
for _ in range(n):
    s, t, x = map(int, input().split())
    stx.append([x, s - x, t - x])
stx.sort(reverse=True)
d = [int(input()) for _ in range(q)]

import bisect

seg = SegmentTree(q, 10**9 + 1, lambda a, b : min(a, b))

for x, start, last in stx:
    l = bisect.bisect_left(d, start)
    r = bisect.bisect_left(d, last)
    seg.update(l, r, x)

for i, j in enumerate(d):
    res = seg.query(i)
    if res == 10**9 + 1:
        print(-1)
    else:
        print(res)

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

def main():
    N, Q = map(int, input().split())
    tl = [] 
    for _ in range(N):
        S, T, X = map(int, input().split())
        tl.append((S-X, 1, X)) 
        tl.append((T-X, 0, X)) 
    for _ in range(Q):
        D = int(input())
        tl.append((D, 2, 0)) 
    tl.sort()
    working = set() 
    wcur = 0 
    curmin = -1
    flag = False
    for t, c, x in tl:
        if c == 0: 
            wcur -= 1
            working.remove(x)
            if x <= curmin:
                curmin = x
                flag = True
        elif c == 1: 
            wcur += 1
            working.add(x)
            if curmin < 0 or curmin >= x:
                curmin = x
                flag = False
        else: 
            if wcur == 0:
                curmin = -1
                flag = False
            elif flag:
                curmin = min(working)
                flag = False
            print(curmin)
    return
    
if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import sys
    input = lambda : sys.stdin.readline().rstrip()

    from heapq import heappush, heappop 

    running = []
    events = []
    delete = set()

    n, q = map(int, input().split())
    for _ in range(n):
        s, t, x = map(int, input().split())
        events.append((s - x, x, 1)) 
        events.append((t - x, x, 0)) 
    for _ in range(q):
        d = int(input())
        events.append((d, 10**10, 2))
    events.sort()
    for i in range(len(events)):
        temp = events[i]
        if temp[-1] == 1:
            heappush(running, temp[1])
            delete.discard(temp[1])
        elif temp[-1] == 0:
            delete.add(temp[1])
        else:
            flag = 1
            while running:
                p = heappop(running)
                if p not in delete:
                    flag = 0
                    heappush(running, p)
                    print(p)
                    break
            if flag:
                print(-1)
if __name__ == '__main__':
    main()

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

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

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

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

n,q = map(int,input().split())
chk = []
for i in range(n):
  s,t,x = map(int,input().split())
  chk.append((s-x,t-x,x))
  
d = [int(input()) for i in range(q)]
seg = SegmentTree(q,10**9+1,lambda a, b: min(a,b))

for a,b,x in chk:
  L = bisect_left(d,a)
  R = bisect_left(d,b)
  seg.update(L,R,x)
  
for i in range(q):
  m = seg.query(i)
  if m == 10**9+1:
    print(-1)
  else:
    print(m)

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

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

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

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

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

n,q = map(int,input().split())
chk = []
for i in range(n):
  s,t,x = map(int,input().split())
  chk.append((s-x,t-x,x))
d = [int(input()) for i in range(q)]
seg = SegmentTree(q,10**9+1,lambda a, b: min(a,b))

for a,b,x in chk:
  L = bisect_left(d,a)
  R = bisect_left(d,b)
  seg.update(L,R,x)
  
for i in range(q):
  m = seg.query(i)
  if m == 10**9+1:
    print(-1)
  else:
    print(m)

Solution (Python):
def main():
    import sys
    input = lambda : sys.stdin.readline().rstrip()

    from heapq import heappush, heappop 

    running = []
    events = []
    delete = set()

    n, q = map(int, input().split())
    for _ in range(n):
        s, t, x = map(int, input().split())
        time = max(s - x, 0)
        if t - x < 0:
            continue
        events.append((s - x, x, 1)) 
        events.append((t - x, x, 0)) 
    events.sort()
    ans = []
    idx = -1
    for _ in range(q):
        d = int(input())
        if d >= events[-1][0]:
            print(-1)
            continue
        while events[idx + 1][0] <= d:
            idx += 1
            if events[idx][2] == 1:
                heappush(running, events[idx][1])
                delete.discard(events[idx][1])
            else:
                delete.add(events[idx][1])
        flag = 1
        while running:
            x = heappop(running)
            if x not in delete:
                heappush(running, x)
                print(x)
                flag = 0
                break
        if flag:
            print(-1)
if __name__ == '__main__':
    main()

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

from heapq import heappush, heappop 

running = []
events = []
delete = set()

n, q = map(int, input().split())
for _ in range(n):
    s, t, x = map(int, input().split())
    time = max(s - x, 0)
    if t - x < 0:
        continue
    events.append((s - x, x, 1)) 
    events.append((t - x, x, 0)) 
events.sort()
ans = []
idx = -1
for _ in range(q):
    d = int(input())
    if d >= events[-1][0]:
        print(-1)
        
        continue
    while events[idx + 1][0] <= d:
        idx += 1
        if events[idx][2] == 1:
            heappush(running, events[idx][1])
            delete.discard(events[idx][1])
        else:
            delete.add(events[idx][1])
    flag = 1
    while running:
        x = heappop(running)
        if x not in delete:
            heappush(running, x)
            print(x)
            
            flag = 0
            break
    if flag:
        print(-1)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

input = sys.stdin.readline

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, Q, STX, D):
    E = []
    for i, (s, t, x) in enumerate(STX):
        E.append((s-x, 1, x, i))
        E.append((t-x, -1, x, i))
    E.sort(reverse=True)

    q = []
    done = set()
    ans = [-1] * Q
    for j, d in enumerate(D):
        while E and E[-1][0] <= d:
            t, e, x, i = E.pop()
            if e == 1:
                heapq.heappush(q, (x, i))
            else:
                done.add((x, i))

        while q and q[0] in done:
            done.remove(heapq.heappop(q))

        if q:
            ans[j] = q[0][0]

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


def main():
    N, Q = read_int_n()
    STX = list(read_int_n() for _ in range(N))
    D = list(read_int() for _ in range(Q))
    (slv(N, Q, STX, D))


if __name__ == '__main__':
    main()

Solution (Python):
def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1

def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s

def query(k):
    return _query(k)[1]

from bisect import bisect_left
from sys import stdin

if __name__ == '__main__':
    n, q = map(int, stdin.readline().rstrip().split())
    stx = [list(map(int, stdin.readline().rstrip().split())) for _ in range(n)]
    l = [int(stdin.readline().rstrip()) for _ in range(q)]

    INF = (-1, 2**31-1)
    N = len(l)
    N0 = 2**(N-1).bit_length()
    data = [None]*(2*N0)

    stx.sort(key=lambda x:x[2], reverse=True)
    for i, (s, t, x) in enumerate(stx):
        i1 = bisect_left(l, s - 0.5 - x)
        i2 = bisect_left(l, t - 0.5 - x)
        update(i1, i2, (i, x))

    for i in range(q):
        tmp = query(i)
        if tmp == INF[1]:
            print(-1)
        else:
            print(tmp)

Solution (Python):
from heapq import heapify,heappop,heappush
import sys
read=sys.stdin.readline
class mset:
    def __init__(self):
        self.p,self.q=[],[]
        heapify(self.p);heapify(self.q)
    def add(self,a):
        heappush(self.p,a)
    def delete(self,a):
            heappush(self.q,a)
    def minimum(self):
        while self.q and self.p[0]==self.q[0]:
            heappop(self.p);heappop(self.q)
        return self.p[0] if self.p else None

N,Q=map(int,read().split())
event=[]
for i in range(N):
    S,T,X=map(int,read().split())
    event.append((1,S-X,X))
    event.append((0,T-X,X))

s=mset()
now=0
for i in range(Q):
    D=int(read())
    event.append((2,D,0))
event.sort(key=lambda x:(x[1],x[0]))

for c,t,w in event:
    if c==0:
        s.delete(w)
    elif c==1:
        s.add(w)
    else:
        m=s.minimum()
        print(-1 if m==None else m)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from bisect import bisect_left 
from operator import itemgetter
def main():
    n, q = map(int, readline().split())
    STX = []
    for _ in range(n):
        s, t, x = map(int, readline().split())
        STX.append((s, t, x))
    D = []
    for _ in range(q):
        d = int(readline())
        D.append(d)

    STX.sort(key=itemgetter(2))

    ans = [-1 for _ in range(q)]
    skipTo = [-1 for _ in range(q)]
    for s, t, x in STX:
        
        
        
        left = bisect_left(D, s-x)
        right = bisect_left(D, t-x)

        
        
        
        while left < right: 
            if skipTo[left] == -1:
                
                
                
                skipTo[left] = right
                ans[left] = x
                left += 1
            else:
                
                left = skipTo[left] 
    for i in ans:
        print(i)
if __name__ == '__main__':
    main()

Solution (Python):

from bisect import bisect_left
from operator import itemgetter


def main():
    N, Q, *STXD = map(int, open(0).read().split())
    STX, D = sorted(zip(*[iter(STXD[: 3 * N])] * 3), key=itemgetter(2)), STXD[3 * N :]
    ans = [-1] * Q
    road = [-1] * Q  
    for s, t, x in STX:
        l, r = bisect_left(D, s - x), bisect_left(D, t - x)
        while l < r:
            if road[l] == -1:
                ans[l] = x
                road[l] = r
                l += 1
            else:
                l = road[l]
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Solution (Python):

from bisect import bisect_left
from operator import itemgetter


def main():
    N, Q, *STXD = map(int, open(0).read().split())
    D = STXD[3 * N :]
    ans = [-1] * Q
    road = [-1] * Q  
    for s, t, x in sorted(zip(*[iter(STXD[: 3 * N])] * 3), key=itemgetter(2)):
        l, r = bisect_left(D, s - x), bisect_left(D, t - x)
        while l < r:
            if road[l] == -1:
                ans[l] = x
                road[l] = r
                l += 1
            else:
                l = road[l]
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Solution (Python):

from bisect import bisect_left
from operator import itemgetter


def main():
    N, Q, *STXD = map(int, open(0).read().split())
    STX, D = sorted(zip(*[iter(STXD[: 3 * N])] * 3), key=itemgetter(2)), STXD[3 * N :]
    ans = [-1] * Q
    road = [-1] * Q  
    for s, t, x in STX:
        l, r = bisect_left(D, s - x), bisect_left(D, t - x)
        while l < r:
            if road[l] == -1:
                ans[l] = x
                road[l] = r
                l += 1
            else:
                l = road[l]
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

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

def main():
    N, Q = map(int, input().split())
    tl = [] 
    for _ in range(N):
        S, T, X = map(int, input().split())
        tl.append((S-X, 1, X)) 
        tl.append((T-X, 0, X)) 
    for _ in range(Q):
        D = int(input())
        tl.append((D, 2, 0)) 
    tl.sort()
    working = set() 
    wcur = 0 
    curmin = -1
    flag = False
    for t, c, x in tl:
        if c == 0: 
            wcur -= 1
            working.remove(x)
            if x <= curmin:
                curmin = x
                flag = True
        elif c == 1: 
            wcur += 1
            working.add(x)
            if curmin < 0 or curmin >= x:
                curmin = x
                flag = False
        else: 
            if wcur == 0:
                curmin = -1
                flag = False
            elif flag:
                curmin = min(working)
                flag = False
            print(curmin)
    return
    
if __name__ == "__main__":
    main()

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

def main():
    N, Q = map(int, input().split())
    tl = [] 
    for _ in range(N):
        S, T, X = map(int, input().split())
        tl.append((S-X, 1, X)) 
        tl.append((T-X, 0, X)) 
    for _ in range(Q):
        D = int(input())
        tl.append((D, 2, 0)) 
    tl.sort()
    working = list() 
    todelete = list() 
    for t, c, x in tl:
        if c == 0: 
            heapq.heappush(todelete, x)
        elif c == 1: 
            heapq.heappush(working, x)
        else: 
            while todelete and todelete[0] == working[0]:
                heapq.heappop(todelete)
                heapq.heappop(working)
            print(-1 if not working else working[0])
    return
    
if __name__ == "__main__":
    main()

Solution (Python):
def main():
    N, Q = map(int, input().split())
    tl = [] 
    for _ in range(N):
        S, T, X = map(int, input().split())
        tl.append((S-X, 1, X)) 
        tl.append((T-X, 0, X)) 
    for _ in range(Q):
        D = int(input())
        tl.append((D, 2, 0)) 
    tl.sort()
    working = set() 
    wcur = 0 
    curmin = -1
    flag = False
    for t, c, x in tl:
        if c == 0: 
            wcur -= 1
            working.remove(x)
            if x <= curmin:
                curmin = x
                flag = True
        elif c == 1: 
            wcur += 1
            working.add(x)
            if curmin < 0 or curmin >= x:
                curmin = x
                flag = False
        else: 
            if wcur == 0:
                curmin = -1
                flag = False
            elif flag:
                curmin = min(working)
                flag = False
            print(curmin)
    return
    
if __name__ == "__main__":
    main()

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

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

    stx = []
    tmp = set([])

    for _ in range(n):
        s,t,x = map(int, input().split())
        stx.append((s,t,x))
        tmp.add(x-t)
        tmp.add(x-s)

    d = {}
    for i in range(q):
        di = -int(input())
        tmp.add(di)
        d[di] = i

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

    v2i = {}

    for i, v in enumerate(sorted(tmp)):
        v2i[v] = i

    l = [1] * (len(tmp) + 1)

    for di in d:
        l[v2i[di]] = di
            

    
    ide_ele_min = 1

    
    N = len(l)

    num_min =2**(N-1).bit_length()
    seg_min=[ide_ele_min]*2*num_min

    def init_min(init_min_val):
        
        for i in range(N):
            seg_min[i+num_min-1]=init_min_val[i]    
        
        for i in range(num_min-2,-1,-1) :
            seg_min[i]=min(seg_min[2*i+1],seg_min[2*i+2]) 
    
    def update_min(k,x):
        k += num_min-1
        seg_min[k] = x
        while k:
            k = (k-1)//2
            seg_min[k] = min(seg_min[k*2+1],seg_min[k*2+2])
        
    def query_min(p,q):
        if q<=p:
            return ide_ele_min
        p += num_min-1
        q += num_min-2
        res=ide_ele_min
        while q-p>1:
            if p&1 == 0:
                res = min(res,seg_min[p])
            if q&1 == 1:
                res = min(res,seg_min[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = min(res,seg_min[p])
        else:
            res = min(min(res,seg_min[p]),seg_min[q])
        return res



    init_min(l)
    ans = [-1] * q

    for s, t, x in stx:
        l = v2i[x-t] + 1
        r = v2i[x-s] + 1
        v = query_min(l, r)
        while v != 1:
            i_d = d[v]
            i_sg = v2i[v]
            ans[i_d] = x
            update_min(i_sg, 1)
            v = query_min(l, r)

    for ansi in ans:
        print(ansi)
            
if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect_left
import sys
input = sys.stdin.readline
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def same(self, x, y):
        return self.find(x) == self.find(y)
def main():
    N, Q = map(int, input().split())
    kouji = [list(map(int, input().split())) for _ in range(N)]
    D = [int(input()) for _ in range(Q)]
    ans = [-1]*Q
    nxt = [i+1 for i in range(Q)]
    uf = UnionFind(Q)
    kouji.sort(key=lambda x: x[2])
    for i in range(N):
        S, T, X = kouji[i]
        L = S-X
        R = T-X-1
        L_idx = bisect_left(D, L)
        R_idx = bisect_left(D, R+1)
        p = L_idx
        while p < R_idx:
            if ans[p] == -1:
                ans[p] = X
                uf.union(L_idx, p)
                nxt[p] = R_idx
                p += 1
            else:
                par = uf.find(p)
                p = nxt[par]
                uf.union(L_idx, par)
                par = uf.find(par)
                if nxt[par] < R_idx:
                    nxt[par] = R_idx
                if nxt[par] < p:
                    nxt[par] = p
    for i in range(Q):
        print(ans[i])

if __name__ == "__main__":
    main()

Solution (Python):
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
data = []
n,q = map(int,input().split())
for i in range(n):
    s, t, x = map(int, input().split())
    data.append([s-x,t-x,x])
data.sort(key=lambda x:x[0])
d_index = 0
candidate_x = []
inf = float("inf")
data += [[inf,inf,inf]]
for i in range(q):
    d = int(input())
    while d >= data[d_index][0]:
        heappush(candidate_x, (data[d_index][2], data[d_index][1]))
        d_index += 1
    if len(candidate_x) == 0:
        print(-1)
    else:
        while candidate_x:
            x,finish_t = heappop(candidate_x)
            if finish_t > d:
                heappush(candidate_x, (x, finish_t))
                print(x)
                break
        else:
            print(-1)

Solution (Python):
import sys
input = sys.stdin.readline
INF = 1<<31
from bisect import bisect_left

def main():
    N,Q = map(int,input().split())
    roadwork = [tuple(map(int,input().split())) for _ in range(N)]
    roadwork.sort(key = lambda x:x[2])
    D = [int(input()) for _ in range(Q)]
    ans = [-1] * Q
    skip = [-1] * Q
    for s,t,x in roadwork:
        L = bisect_left(D,s - x)
        R = bisect_left(D,t - x)
        while L < R:
            if skip[L] == -1:
                ans[L] = x
                skip[L] = R
                L += 1
            else:
                L = skip[L]
    print('\n'.join(map(str,ans)))
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
INF = 1<<31
from heapq import heapify,heappop,heappush
from collections import defaultdict

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,0,x))
for i in range(Q):
    d = int(input())
    event.append((d,1,i))

q = []
ans = [-1] * Q
event.sort()
push = defaultdict(int)
pop = defaultdict(int)
for i in range(2*N + Q):
    t,typ,x = event[i]
    if typ == -1:
        heappush(q,x)
        push[x] += 1
    elif typ == 0:
        pop[x] += 1
    else:
        p = -1
        if q:
            p = q[0]
        while p != -1 and push[p] - pop[p] == 0:
            heappop(q)
            if q:
                p = q[0]
            else:
                p = -1
                break
        ans[x] = p
print('\n'.join(map(str,ans)))