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

N, Q = map(int, input().split())
events = []
for iR in range(N):
    S, T, X = map(int, input().split())
    events.append((S-X, T-X, X))
events.sort()

iE = 0
anss = []
PQ = []
for _ in range(Q):
    D = int(input())
    while iE < N and events[iE][0] <= D:
        tmSt, tmEn, x = events[iE]
        heappush(PQ, (x, tmEn))
        iE += 1

    xMin = -1
    while PQ:
        x, tmEn = heappop(PQ)
        if tmEn > D:
            xMin = x
            heappush(PQ, (x, tmEn))
            break
    anss.append(xMin)

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

Solution (Python):
from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)


n,q = list(map(int,input().split()))
lines = sys.stdin.readlines()
stx = []
for line in lines[:n]:
    s,t,x = map(int,line.split())
    stx.append((x,s,t))
stx.sort()
D = list(map(int,lines[n:]))
ans = [-1]*q
skip = [-1]*q
for x,s,t in stx:
    ss = bisect_left(D,s-x)
    tt = bisect_left(D,t-x)
    while ss < tt:
        if skip[ss] == -1:
            ans[ss]=x
            skip[ss]=tt
            ss += 1
        else:
            ss = skip[ss]
print('\n'.join(map(str,ans)))

Solution (Python):
import sys
input=sys.stdin.readline
from bisect import bisect_left
class SegmentTree():
    def __init__(self,size,func,default):
        self.leaf=2**(size-1).bit_length()
        self.data=[default]*(2*self.leaf-1)
        self.f=func; self.d=default
    def rangeupdate(self,l,r,x):
        l+=self.leaf-1; r+=self.leaf-1
        while l<r:
            if not l&1:
                self.data[l]=self.f(self.data[l],x)
                l+=1
            if not r&1:
                r-=1
                self.data[r]=self.f(self.data[r],x)
            l>>=1; r>>=1
    def getvalue(self,i):
        k=i+self.leaf-1
        ret=self.d
        while k>=0:
            ret=self.f(ret,self.data[k])
            k=(k-1)>>1
        return ret

n,q=map(int,input().split())
seg=SegmentTree(q,min,float('inf'))
STX=[list(map(int,input().split())) for _ in range(n)]
D=[int(input()) for _ in range(q)]
for s,t,x in STX:
    seg.rangeupdate(bisect_left(D,s-x),bisect_left(D,t-x),x)
for i in range(q):
    print(-1 if seg.getvalue(i)==float('inf') else seg.getvalue(i))

Solution (Python):
def main():
    import sys,heapq
    from collections import defaultdict
    input = sys.stdin.readline

    n,q = map(int,input().split())
    
    used = defaultdict(int)
    tank = []

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

    cnt = 0
    for i in range(q):
        d = int(input())
        while cnt<=len(p)-1 and p[cnt][0] <= d:
            w = p[cnt][1]
            if w>=0:
                used[w] += 1
                heapq.heappush(tank,w)
            else:
                used[-w] -= 1
            cnt += 1
        while True:
            if len(tank) == 0:
                print(-1)
                break
            kouho = tank[0]
            if used[kouho] > 0:
                print(kouho)
                break
            else:
                heapq.heappop(tank)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
from bisect import bisect_left

n, q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:n]:
    s, t, x = map(int, line.split())
    kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[n:]))

ans = [-1] * q
skip = [-1] * q
for x, s, t in kkk:
    ss = bisect_left(ddd, s - x)
    tt = bisect_left(ddd, t - x)
    while ss < tt:
        sk = skip[ss]
        if sk == -1:
            ans[ss] = x
            skip[ss] = tt
            ss += 1
        else:
            ss = sk
print('\n'.join(map(str, ans)))

Solution (Python):
import sys
from bisect import bisect_left

n, q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:n]:
    s, t, x = map(int, line.split())
    kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[n:]))

ans = [-1] * q
skip = [-1] * q
for x, s, t in kkk:
    ss = bisect_left(ddd, s - x)
    tt = bisect_left(ddd, t - x)
    while ss < tt:
        sk = skip[ss]
        if sk == -1:
            ans[ss] = x
            skip[ss] = tt
            ss += 1
        else:
            skip[ss] = max(sk, tt)
            ss = sk
print('\n'.join(map(str, ans)))

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

n, q = map(int, input().split())
lines = sys.stdin.readlines()
events = []
kkk = []
for line in lines[:n]:
    s, t, x = map(int, line.split())
    events.append((s - x, 2, x))
    events.append((t - x, 1, x))
for line in lines[n:]:
    events.append((int(line), 3))
events.sort()

constructing = []
available = set()
buf = []
for ev in events:
    if ev[1] == 2:
        heappush(constructing, ev[2])
        available.add(ev[2])
    elif ev[1] == 1:
        available.remove(ev[2])
    else:
        if not available:
            buf.append(-1)
        else:
            while constructing[0] not in available:
                heappop(constructing)
            buf.append(constructing[0])
print('\n'.join(map(str, buf)))

Solution (Python):
N, Q = map(int, input().split())

work = []
for i in range(N):
    start, end, pos = map(int, input().split())
    work.append((start - pos - 0.5, end - pos - 0.5, pos))
work.sort(key=lambda x: x[0])
depart_time = [int(input()) for _ in range(Q)]
heap = []
end_time = {}
import heapq
i = 0
for depart in depart_time:
    while i < len(work) and work[i][0] < depart:
        start, end, pos = work[i]
        heapq.heappush(heap, pos)
        end_time[pos] = end
        i += 1
    while heap and end_time[heap[0]] < depart:
        heapq.heappop(heap)
    if heap: print(heap[0])
    else: print(-1)

Solution (Python):
import bisect

n, q = list(map(int, input().split()))
rws = [list(map(int, input().split())) for _ in range(n)]
ds = [int(input()) for _ in range(q)]

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

ans = [-1 for _ in range(q)]
nxt = [-1 for _ in range(q)]
for rw in rws:
	st = bisect.bisect_left(ds, rw[0] - rw[2])
	en = bisect.bisect_left(ds, rw[1] - rw[2])
	while st < en:
		if nxt[st] == -1:
			ans[st] = rw[2]
			nxt[st] = en
			st += 1
		else:
			st = nxt[st]

for a in ans:
	print(a)

Solution (Python):

import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from collections import defaultdict

N,Q = map(int,input().split())
task = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  task.append((t-x,0,x)) 
  task.append((s-x,1,x)) 

for i in range(Q):
  d = int(input())
  task.append((d,2,i)) 
answer = [-1]*Q

task.sort()


se = set()
se_hp = [] 


for a,b,c in task:
  if not b: 
    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)
    answer[c] = se_hp[0] if se_hp else -1

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

Solution (Python):

import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from collections import defaultdict

N,Q = map(int,input().split())
task = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  task.append((t-x,0,x)) 
  task.append((s-x,1,x)) 

for i in range(Q):
  d = int(input())
  task.append((d,2,i)) 
answer = [-1]*Q

task.sort()


se = set()
se_hp = [] 


for a,b,c in task:
  if not b: 
    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)
    answer[c] = se_hp[0] if se_hp else -1

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

Solution (Python):

import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from collections import defaultdict

N,Q = map(int,input().split())
task = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  task.append((t-x,0,x)) 
  task.append((s-x,1,x)) 

for i in range(Q):
  d = int(input())
  task.append((d,2,i)) 
answer = [-1]*Q

task.sort()


se = [] 
added = defaultdict(int) 


for a,b,c in task:
  if not b: 
    added[c] -= 1
  elif b&1: 
    heappush(se,c)
    added[c] += 1
  else: 
    while se and added[se[0]] == 0:
      heappop(se)
    answer[c] = se[0] if se else -1

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

Solution (Python):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

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

D = []
for i in range(Q):
    d = int(input())
    D.append(d)

E = sorted(E)

que = []

s, t, x = E[0]
j = 1
y, e = N, N
ans = [-1] * Q
for i, d in enumerate(D):
    while j < N + 1 and s <= d:
        heappush(que, (x, t))
        y, e = que[0]
        if j < N:
            s, t, x = E[j]
        j += 1
    while que and e <= d:
        heappop(que)
        if que:
            y, e = que[0]

    if que:
        ans[i] = y

for i in ans:
    print(i)

Solution (Python):
import sys
from heapq import heappush, heappop
input = sys.stdin.readline

num, person = map(int, input().split())
arr = []

for i in range(num):
    s, t, x = map(int, input().split())
    arr.append((s - x - 0.5, 1, x, i))
    arr.append((t - x - 0.5, 0, x, i))

for i in range(person):
    d = int(input())
    arr.append((d,))

arr.sort()

heap = []
done = set()

for elem in arr:
    if len(elem) == 1:
        while heap and heap[0][1] in done:
            heappop(heap)
        if heap:
            print(heap[0][0])
        else:
            print(-1)
        continue

    time, kind, x, i = elem
    if kind:
        heappush(heap, (x, i))
    else:
        done.add(i)

Solution (Python):
import sys
from heapq import heappush, heappop
from collections import defaultdict
input = sys.stdin.readline

num, person = map(int, input().split())
arr = []

for i in range(num):
    s, t, x = map(int, input().split())
    arr.append((s - x - 0.5, 1, x, i))
    arr.append((t - x - 0.5, -1, x, i))

for i in range(person):
    d = int(input())
    arr.append((d,))

arr.sort()

heap = []
done = set()

for elem in arr:
    if len(elem) == 1:
        d = elem[0]
        while heap and heap[0][1] in done:
            heappop(heap)
        if heap:
            print(heap[0][0])
        else:
            print(-1)
        continue

    time, kind, x, i = elem
    if kind == 1:
        heappush(heap, (x, i))
    elif kind == -1:
        done.add(i)

Solution (Python):
import sys
from heapq import heappush, heappop
from collections import defaultdict
input = sys.stdin.readline

num, person = map(int, input().split())
arr = []

for i in range(num):
    s, t, x = map(int, input().split())
    arr.append((s - x - 0.5, 1, x, i))
    arr.append((t - x - 0.5, -1, x, i))

for i in range(person):
    d = int(input())
    arr.append((d,))

arr.sort()

heap = []
done = defaultdict(int)

for elem in arr:
    if len(elem) == 1:
        d = elem[0]
        while heap and done[heap[0][1]] and d > done[heap[0][1]]:
            heappop(heap)
        if heap:
            print(heap[0][0])
        else:
            print(-1)
        continue

    time, kind, x, i = elem
    if kind == 1:
        heappush(heap, (x, i))
    elif kind == -1:
        done[i] = time

Solution (Python):
def main():
    from bisect import bisect_left
    def update(l,r,v):
        L,R=l+N0,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=10**18
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        return s
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-10**18]+list(map(int,t[n:]))+[10**18]
    N0=2**(q+1).bit_length()
    data=[10**18]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        update(l,r,x)
    for i in range(q):
        a=query(i+1)
        print(-(a==10**18)or a)
if __name__=='__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LLI(): return [int(x) for x in sys.stdin.readlines()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        XST.append([x, s, t])
    XST.sort()
    D = LLI()
    ans = [-1] * Q
    nexts = [-1] * Q
    for x, s, t in XST:
        i = bisect_left(D, s - x)
        end = bisect_left(D, t - x)
        to = end
        while to < Q and nexts[to] != -1:
            to = nexts[to]
        while i < end:
            if nexts[i] == -1:
                ans[i] = x
                nexts[i] = to
                i += 1
            else:
                i = nexts[i]
    for y in ans:
        print(y)
    return

main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LLI(): return [int(x) for x in sys.stdin.readlines()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        XST.append([x, s, t])
    XST.sort()
    D = LLI()
    ans = [-1] * Q
    nexts = [-1] * Q
    for x, s, t in XST:
        i = bisect_left(D, s - x)
        end = bisect_left(D, t - x)
        while i < end:
            if nexts[i] == -1:
                ans[i] = x
                nexts[i] = end
                i += 1
            else:
                p = i
                i = nexts[i]
                nexts[p] = max(nexts[p], end)
    for y in ans:
        print(y)
    return

main()

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

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 tuple(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 = tuple(read_int_n() for _ in range(N))
    D = tuple(read_int() for _ in range(Q))
    (slv(N, Q, STX, D))


if __name__ == '__main__':
    main()

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 tuple(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:
            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 = tuple(read_int_n() for _ in range(N))
    D = tuple(read_int() for _ in range(Q))
    (slv(N, Q, STX, D))


if __name__ == '__main__':
    main()

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 tuple(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()
    D = [(i, d) for i, d in enumerate(D)]
    D.sort(reverse=True)
    ans = [-1] * Q
    while D:
        while E and E[-1][0] <= D[-1][1]:
            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:
            heapq.heappop(q)

        i, d = D.pop()
        if q:
            ans[i] = q[0][0]

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


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


if __name__ == '__main__':
    main()

Solution (Python):

import sys
input = sys.stdin.readline

N,Q = map(int,input().split())
q = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  q.append((s-x,1,x)) 
  q.append((t-x,0,x)) 

for i in range(Q):
  d = int(input())
  q.append((d,2,i))
answer = [-1]*Q

se = set() 

q.sort()

min_se = 10**18
flag = False 

for a,c,b in q:
  if not c:
    se.remove(b)
    if min_se == b:
      flag = False
  elif c&1:
    se.add(b)
    if b < min_se:
      min_se = b
      flag = True
  else:
    if se:
      if not flag:
        min_se = min(se)
        flag = True
      answer[b] = min_se

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

Solution (Python):
import sys
from heapq import *
input = sys.stdin.readline
n,Q = list(map(int, input().split()))
Y=[]
for j in range(n):
    a=list(map(int, input().split()))
    Y.append([a[0]-a[2],a[1]-a[2],a[2]])
q = [int(input()) for i in range(Q)]
Y.sort()
X=[]
p=0
for d in q:
    while p<n and Y[p][0]<=d:
        heappush(X,(Y[p][2],Y[p][1]))
        p+=1
    while X and X[0][1] <= d:
        heappop(X)
    if X:
        print(X[0][0])
    else:
        print(-1)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LLI(): return [int(x) for x in sys.stdin.readlines()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        XST.append([x, s, t])
    XST.sort()
    D = LLI()
    ans = [-1] * Q
    nexts = [-1] * Q
    for x, s, t in XST:
        i = bisect_left(D, s - x)
        end = bisect_left(D, t - x)
        while i < end:
            if nexts[i] == -1:
                ans[i] = x
                nexts[i] = end
                i += 1
            else:
                i = nexts[i]
    for y in ans:
        print(y)
    return

main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        XST.append([x, s, t])
    D = []
    for _ in range(Q):
        D.append(II())
    ans = [-1] * Q
    nexts = [-1] * Q
    XST.sort()
    for x, s, t in XST:
        i = bisect_left(D, s - x)
        end = bisect_left(D, t - x)
        while i < end:
            if nexts[i] == -1:
                ans[i] = x
                nexts[i] = end
                i += 1
            else:
                i = nexts[i]
    for y in ans:
        print(y)
    return

main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        XST.append([x, s, t])
    D = []
    for _ in range(Q):
        D.append(II())
    ans = [-1] * Q
    nexts = [-1] * Q
    XST.sort()
    for x, s, t in XST:
        i = bisect_left(D, s)
        end = bisect_left(D, t)
        while i < end:
            if nexts[i] == -1:
                ans[i] = x
                nexts[i] = end
                i += 1
            else:
                i = nexts[i]
    for y in ans:
        print(y)
    return

main()

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

readline = sys.stdin.readline
N, Q = map(int, readline().split())
ans = [None]*Q
def solve(readline=readline):
    qs = [0]*(N+1)
    for i in range(N):
        s, t, x = map(int, readline().split())
        qs[i] = (s-x, t-x, x)
    qs[N] = (10**10, 10**10, 0)
    qs.sort()

    que = []
    D = [int(readline()) for i in range(Q)]
    j = 0
    it = iter(qs).__next__
    s, t, x = it()
    v = w = N
    for d in D:
        while j < N and s <= d:
            heappush(que, (x, t))
            v, w = que[0]
            s, t, x = it()
        while que and w <= d:
            heappop(que)
            if que:
                v, w = que[0]
        if que:
            yield "%d\n" % v
        else:
            yield "-1\n"
ans[:] = solve()
sys.stdout.writelines(ans)