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):
def main():
    import os
    import sys
    from io import BytesIO, IOBase
    
    BUFSIZE = 8192
    
    
    class FastIO(IOBase):
        newlines = 0
    
        def __init__(self, file):
            self._fd = file.fileno()
            self.buffer = BytesIO()
            self.writable = "x" in file.mode or "r" not in file.mode
            self.write = self.buffer.write if self.writable else None
    
        def read(self):
            while True:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                if not b:
                    break
                ptr = self.buffer.tell()
                self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
            self.newlines = 0
            return self.buffer.read()
    
        def readline(self):
            while self.newlines == 0:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                self.newlines = b.count(b"\n") + (not b)
                ptr = self.buffer.tell()
                self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
            self.newlines -= 1
            return self.buffer.readline()
    
        def flush(self):
            if self.writable:
                os.write(self._fd, self.buffer.getvalue())
                self.buffer.truncate(0), self.buffer.seek(0)
    
    
    class IOWrapper(IOBase):
        def __init__(self, file):
            self.buffer = FastIO(file)
            self.flush = self.buffer.flush
            self.writable = self.buffer.writable
            self.write = lambda s: self.buffer.write(s.encode("ascii"))
            self.read = lambda: self.buffer.read().decode("ascii")
            self.readline = lambda: self.buffer.readline().decode("ascii")
    
    
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
    input = lambda: sys.stdin.readline().rstrip("\r\n")
    mod = 10**9 + 7

    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)

main()

Solution (Python):

import os
import sys
from io import BytesIO, IOBase
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
sys.setrecursionlimit(10 ** 7)
mod = 10**9 + 7

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
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import heapq

n,q = readints()

a = []
for i in range(n):
    s,t,x = readints()
    a.append((s-x,0,x))
    a.append((t-x,1,x))
for i in range(q):
    d = readint()
    a.append((d,2,0))
a.sort()

ans = []

stop = []
deleted = []

for t,j,x in a:
    if j==0:
        heapq.heappush(stop,x)
    elif j==1:
        heapq.heappush(deleted,x)
    else:
        while deleted and stop[0] == deleted[0]:
            heapq.heappop(stop)
            heapq.heappop(deleted)
        if stop:
            ans.append(stop[0])
        else:
            ans.append(-1)

printrows(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


class AVL_like_BIT:  
    def __init__(self,n):  
        self.n = n
        self.tree = [0]*(self.n+1)
        self.depth = n.bit_length()

    def add(self,k):  
        while k<=self.n:
            self.tree[k]+=1
            k += k&-k
    
    def delete(self,k): 
        while k<=self.n:
            self.tree[k]-=1
            k += k&-k

    def sum(self,k):  
        ans = 0
        while k>0:
            ans += self.tree[k]
            k -= k&-k
        return ans
    
    def lower_bound(self,k):  
        x = self.sum(k-1)
        if x == self.sum(self.n):  
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  
            q = p+v
            if q <= self.n and self.tree[q] <= x:
                x -= self.tree[q]
                p += v
            v>>=1
        return p+1

    def upper_bound(self,k):  
        x = self.sum(k)
        if x == 0:  
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  
            q = p+v
            if q <= self.n and self.tree[q] < x:
                x -= self.tree[q]
                p += v
            v>>=1
        return p+1

    def query(self,k):  
        if k > self.sum(self.n):  
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  
            q = p+v
            if q <= self.n and self.tree[q] < k:
                k -= self.tree[q]
                p += v
            v>>=1
        return p+1

def compress(a):
    b = sorted(set(a))
    d = {x:i+1 for i,x in enumerate(b)}
    return b,d


import heapq

n,q = readints()

X = []

block = []
free = []
for i in range(n):
    s,t,x = readints()
    X.append(x)
    block.append([s-x,x])
    free.append([t-x,x])

b,d = compress(X)
block = [(x[0],d[x[1]]) for x in block]
free = [(x[0],d[x[1]]) for x in free]
heapq.heapify(block)
heapq.heapify(free)

ans = []
avl = AVL_like_BIT(len(d))
for i in range(q):
    D = readint()
    while block and block[0][0]<=D:
        a = heapq.heappop(block)
        avl.add(a[1])
    while free and free[0][0]<=D:
        a = heapq.heappop(free)
        avl.delete(a[1])
    ans.append(avl.lower_bound(0))

ans = [b[x-1] if x >=0 else -1 for x in ans]
printrows(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


def compress(a):
    b = sorted(set(a))
    d = {x:i+1 for i,x in enumerate(b)}
    return b,d


import heapq

n,q = readints()

X = []

block = []
free = []
for i in range(n):
    s,t,x = readints()
    X.append(x)
    block.append([s-x,x])
    free.append([t-x,x])

b,d = compress(X)
block = [(x[0],d[x[1]]) for x in block]
free = [(x[0],d[x[1]]) for x in free]
heapq.heapify(block)
heapq.heapify(free)

ans = []

stop = []
heapq.heapify(stop)
deleted = []
heapq.heapify(deleted)

for i in range(q):
    D = readint()
    while block:
        if block[0][0]<=D:
            a = heapq.heappop(block)
            heapq.heappush(stop,a[1])
        else:
            break
    while free:
        if free[0][0]<=D:
            a = heapq.heappop(free)
            heapq.heappush(deleted,a[1])
        else:
            break
    while deleted:
        if stop[0] == deleted[0]:
            heapq.heappop(stop)
            heapq.heappop(deleted)
        else:
            break
    if stop:
        ans.append(stop[0])
    else:
        ans.append(-1)

ans = [b[x-1] if x >=0 else -1 for x in ans]
printrows(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


class AVL_like_BIT:  
    def __init__(self,n):  
        self.n = n
        self.tree = [0]*(self.n+1)
        self.depth = n.bit_length()

    def add(self,k):  
        while k<=self.n:
            self.tree[k]+=1
            k += k&-k
    
    def delete(self,k): 
        while k<=self.n:
            self.tree[k]-=1
            k += k&-k

    def sum(self,k):  
        ans = 0
        while k>0:
            ans += self.tree[k]
            k -= k&-k
        return ans
    
    def lower_bound(self,k):  
        x = self.sum(k-1)
        if x == self.sum(self.n):  
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  
            q = p+v
            if q <= self.n and self.tree[q] <= x:
                x -= self.tree[q]
                p += v
            v>>=1
        return p+1

    def upper_bound(self,k):  
        x = self.sum(k)
        if x == 0:  
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  
            q = p+v
            if q <= self.n and self.tree[q] < x:
                x -= self.tree[q]
                p += v
            v>>=1
        return p+1

    def query(self,k):  
        if k > self.sum(self.n):  
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  
            q = p+v
            if q <= self.n and self.tree[q] < k:
                k -= self.tree[q]
                p += v
            v>>=1
        return p+1

def compress(a):
    b = sorted(set(a))
    d = {x:i+1 for i,x in enumerate(b)}
    return b,d


import heapq

n,q = readints()

X = []

block = []
free = []
for i in range(n):
    s,t,x = readints()
    X.append(x)
    block.append([s-x,x])
    free.append([t-x,x])

b,d = compress(X)
block = [(x[0],d[x[1]]) for x in block]
free = [(x[0],d[x[1]]) for x in free]
heapq.heapify(block)
heapq.heapify(free)

ans = []
avl = AVL_like_BIT(len(d))
for i in range(q):
    D = readint()
    while block:
        if block[0][0]<=D:
            a = heapq.heappop(block)
            avl.add(a[1])
        else:
            break
    while free:
        if free[0][0]<=D:
            a = heapq.heappop(free)
            avl.delete(a[1])
        else:
            break        
    ans.append(avl.lower_bound(0))

ans = [b[x-1] if x >=0 else -1 for x in ans]
printrows(ans)

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

def main():
    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):
        a = int(input())
        event.append((a,2,i))
    
    event.sort()
    ans = [-1]*Q
    use = set()
    stop = []
    
    for a,b,c in event:
        if b == 1:
            use.add(c)
            heapq.heappush(stop,c)
        elif b == 0:
            use.remove(c)
        else:
            while stop and stop[0] not in use:
                heapq.heappop(stop)
            ans[c] = -1 if len(stop) == 0 else stop[0]
    
    for num in ans:
        print(num)

if __name__ == "__main__":
    main()

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

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
sys.setrecursionlimit(300000)
from bisect import bisect_left

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')



class SegmentTree(object):

    def __init__(self, A, e, fn):
        self.fn = fn
        self.length = 2 ** (len(A) - 1).bit_length()
        self.data = [e] * (self.length * 2)
        for i in range(len(A)):
            self.data[i + self.length - 1] = A[i]
        for i in reversed(range(self.length - 1)):
            self.data[i] = self.fn(self.data[2 * i + 1], self.data[2 * i + 2])

    
    def update(self, l, r, x):  
        l += self.length
        r += self.length
        while l < r:
            if l & 1:
                self.data[l] = self.fn(self.data[l], x)
                l += 1
            if r & 1:
                self.data[r - 1] = self.fn(self.data[r - 1], x)
                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.fn(ret, self.data[i])
        return ret

N, Q = MI()
STX = [tuple(MI()) for _ in range(N)]
D = [I() for _ in range(Q)]

seg = SegmentTree([INF] * Q, INF, min)
for S, T, X in STX:
    
    l = bisect_left(D, S - X)
    r = bisect_left(D, T - X)
    seg.update(l, r, X)

for i in range(Q):
    ans = seg.query(i)
    if ans == INF:
        print(-1)
    else:
        print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(300000)
from bisect import bisect_left

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')



class SegmentTree(object):

    def __init__(self, A, e, fn):
        self.fn = fn
        self.length = 1 << len(A).bit_length()
        self.data = [e] * (self.length * 2)
        for i in range(len(A)):
            self.data[i + self.length - 1] = A[i]
        for i in reversed(range(self.length - 1)):
            self.data[i] = self.fn(self.data[2 * i + 1], self.data[2 * i + 2])

    
    def update(self, l, r, x):  
        l += self.length
        r += self.length
        while l < r:
            if l & 1:
                self.data[l] = self.fn(self.data[l], x)
                l += 1
            if r & 1:
                self.data[r - 1] = self.fn(self.data[r - 1], x)
                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.fn(ret, self.data[i])
        return ret

N, Q = MI()
STX = [tuple(MI()) for _ in range(N)]
D = [I() for _ in range(Q)]

seg = SegmentTree([INF] * Q, INF, min)
for S, T, X in STX:
    
    l = bisect_left(D, S - X)
    r = bisect_left(D, T - X)
    seg.update(l, r, X)

for i in range(Q):
    ans = seg.query(i)
    if ans == INF:
        print(-1)
    else:
        print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(300000)
from bisect import bisect_left

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')



class SegmentTree(object):

    def __init__(self, n, e, fn):
        self.fn = fn
        self.length = 1 << n.bit_length()
        self.data = [e] * (self.length * 2)

    
    def update(self, l, r, x):  
        l += self.length
        r += self.length
        while l < r:
            if l & 1:
                self.data[l] = self.fn(self.data[l], x)
                l += 1
            if r & 1:
                self.data[r - 1] = self.fn(self.data[r - 1], x)
                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.fn(ret, self.data[i])
        return ret

N, Q = MI()
STX = [tuple(MI()) for _ in range(N)]
D = [I() for _ in range(Q)]

seg = SegmentTree(Q, INF, min)
for S, T, X in STX:
    
    l = bisect_left(D, S - X)
    r = bisect_left(D, T - X)
    seg.update(l, r, X)

for i in range(Q):
    ans = seg.query(i)
    if ans == INF:
        print(-1)
    else:
        print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(300000)
from bisect import bisect_left

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')



class SegmentTree(object):

    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 = MI()
STX = [tuple(MI()) for _ in range(N)]
D = [I() for _ in range(Q)]

seg = SegmentTree(Q, INF, min)
for S, T, X in STX:
    
    l = bisect_left(D, S - X)
    r = bisect_left(D, T - X)
    seg.update(l, r, X)

for i in range(Q):
    ans = seg.query(i)
    if ans == INF:
        print(-1)
    else:
        print(ans)

Solution (Python):
from heapq import heappop, heappush

import sys
input = sys.stdin.buffer.readline


def main():

    n, q = map(int, input().split())
    stx = [map(int, input().split()) for _ in range(n)]
    ds = [int(input()) for _ in range(q)]
    INF = 10 ** 9 + 1
    CHECK = 2
    START = 1
    END = 0
    NULL = 0

    tfdi = []
    for i, (s, t, x) in enumerate(stx):
        t_start = max(0, s - x)
        t_end = max(0, t - x)

        tfdi.append((t_start, START, x, i))
        tfdi.append((t_end, END, x, i))

    for d in ds:
        tfdi.append((d, CHECK, NULL, NULL))
    tfdi.append((INF, START, INF, -1))
    tfdi.sort()

    hp = [(INF, -1)]
    ans = []
    passed = set()
    for t, f, d, i in tfdi:
        if f == CHECK:
            while hp[0][1] in passed:
                heappop(hp)
            if hp[0][0] == INF:
                tmp = -1
            else:
                tmp = hp[0][0]
            ans.append(tmp)

        elif f == START:
            heappush(hp, (d, i))
        else:
            passed.add(i)

    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
sys.setrecursionlimit(10 ** 7)
mod = 10**9 + 7

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



from heapq import heappop, heappush
from collections import defaultdict

n, q = map(int,input().split())
task = []
for _ in range(n): 
  s, t, x = map(int, input().split())
  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 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)
    answer[c] = se_hp[0] if se_hp else -1

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,q = LI()
    stx = [LI() for _ in range(n)]
    da = [I() for _ in range(q)]

    q = []
    for s,t,x in stx:
        sx = s - x
        tx = t - x - 1
        heapq.heappush(q, (sx, x, tx))

    t = []
    cx = inf
    ctx = inf
    c = 0
    while len(q):
        sx, x, tx = heapq.heappop(q)
        
        
        
        if sx > ctx:
            t.append((sx-1, cx))
            cx = x
            ctx = tx
        elif cx > x:
            if ctx > tx:
                heapq.heappush(q, (tx+1, cx, ctx))
            t.append((sx-1, cx))
            cx = x
            ctx = tx
        elif tx > ctx:
            heapq.heappush(q, (ctx+1, x, tx))

    t.append((inf, inf))
    

    r = []
    for d in da:
        i = bisect.bisect_right(t, (d, -1))
        
        u = t[i][1]
        if u == inf:
            r.append(-1)
        else:
            r.append(u)

    return JA(r, "\n")

print(main())

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

    from heapq import heappush, heappop 

    running = [] 
    events = [] 
    finished = 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])
            finished.discard(temp[1])
        elif temp[-1] == 0:
            finished.add(temp[1])
        else:
            flag = 1
            while running:
                p = heappop(running)
                if p not in finished:
                    flag = 0
                    heappush(running, p)
                    print(p)
                    break
            if flag:
                print(-1)
if __name__ == '__main__':
    main()

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

def segfun(x, y):
    return min(x, y)
ide_ele = 10**9 + 1


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 == ide_ele:
        print(-1)
    else:
        print(res)