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):
N,Q = list(map(int, input().split()))
STX = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

L = [(s-x-0.5, t-x-0.5,x) for s,t,x in STX] + [(d,) for d in D]
L.sort()

import heapq
hp = [] 
memo = {} 

for l in L:
  if len(l)==1:
    while hp and l[0] > memo[hp[0]]:
      heapq.heappop(hp)
    if hp:
      print(hp[0])
    else:
      print(-1)
  else:
    heapq.heappush(hp, l[2])
    memo[l[2]]=l[1]

Solution (Python):
import collections


def main():
    from sys import stdin, stdout

    read = iter(stdin.read().splitlines()).next
    
    

    def read_array(sep=None, maxsplit=-1):
        return read().split(sep, maxsplit)

    def read_int():
        return int(read())

    def read_int_array(sep=None, maxsplit=-1):
        return [int(a) for a in read_array(sep, maxsplit)]

    def write(*args, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in args) + end)

    def write_array(array, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in array) + end)

    N, Q = read_int_array()
    updates1 = []
    updates2 = []
    for i in range(N):
        S, T, X = read_int_array()
        updates1.append((S - X, X))
        updates2.append((T - X, X))

    active = []
    to_delete = collections.defaultdict(int)
    import heapq
    heapq.heapify(updates1)
    heapq.heapify(updates2)
    for _ in range(Q):
        x = read_int()
        while updates1 and updates1[0][0] <= x:
            coord, val = heapq.heappop(updates1)
            heapq.heappush(active, val)

        while updates2 and updates2[0][0] <= x:
            coord, val = heapq.heappop(updates2)
            to_delete[val] += 1

        while active and to_delete[active[0]] > 0:
            to_delete[active[0]] -= 1
            heapq.heappop(active)
        write(active[0] if active else -1)

main()

Solution (Python):
import sys
from collections import deque
from collections import defaultdict
import math
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
 
n,q = map(int,input().split())
x = []
for i in range(n):
        x.append(list(map(int,input().split())))
x.sort(key = lambda x : x[2])
dd = []
zaa = []
for i in range(q):
        a = int(input())
        dd.append(a)
        zaa.append(a)
y = []
 
for i in range(n):
        a = x[i][0]-x[i][2]
        b = x[i][1]-1-x[i][2]
        y.append([a,b])
        zaa.append(a)
        zaa.append(b)
import bisect
ans = [-1]*q
tobi = [-1]*q

for i in range(n):
        xx = bisect.bisect_left(dd,y[i][0])
        yy = bisect.bisect_left(dd,y[i][1]+1)
        j = xx
 
 
        while j < yy:
                if ans[j] == -1:
                        ans[j] = x[i][2]
                        tobi[j] = yy
                        j += 1
                        
                else:
                        tmp = tobi[j]
                        tobi[j] = yy
                        j = tmp
for i in ans:
        print(i)

Solution (Python):

"""<https://github.com/cheran-senthil/PyRival>"""
from __future__ import division, print_function

import collections
import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
else:
    _str = str
    str = lambda x=b"": x if type(x) is bytes else _str(x).encode()


def main():
    N, Q = map(int, input().split())
    updates = []
    for i in range(N):
        S, T, X = map(int, input().split())
        updates.append((S - X, 1, X))
        updates.append((T - X, -1, X))

    active = []
    to_delete = collections.defaultdict(int)
    import heapq
    updates.sort(reverse=True)
    for _ in range(Q):
        x = int(input())
        while updates and updates[-1][0] <= x:
            coord, tp, val = updates.pop()

            if tp == -1:
                to_delete[val] += 1
            else:
                heapq.heappush(active, val)

            while active and to_delete[active[0]] > 0:
                to_delete[active[0]] -= 1
                heapq.heappop(active)
        print(active[0] if active else -1)




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._buffer = BytesIO()
        self._fd = file.fileno()
        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):
        if self._buffer.tell():
            return self._buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    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)


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", b" "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", b"\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip(b"\r\n")



if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from bisect import bisect_left as bl
class segtree:
    def __init__(self, nn):
        self.NN = nn
        self.XX = [0] * (2**(nn+1)-1)
    def getmax(self, i):
        j = 2**self.NN + i - 1
        ma = -1
        while j >= 0:
            ma = max(ma, self.XX[j])
            j = (j-1) // 2
        return -1 if ma <= 0 else INF - ma
    def updaterange(self, a, b, x):
        l = a + (1<<self.NN)
        r = b + (1<<self.NN)
        s = 0
        while l < r:
            if l%2:
                self.XX[l-1] = max(self.XX[l-1], x)
                l += 1
            if r%2:
                r -= 1
                self.XX[r-1] = max(self.XX[r-1], x)
            l >>= 1
            r >>= 1

N, Q = map(int, input().split())
st = segtree(18)
INF = 1<<50
X = []
D = []
for _ in range(N):
    s, t, x = map(int, input().split())
    X.append((s, t, x))
for _ in range(Q):
    D.append(int(input()))

for s, t, x in X:
    st.updaterange(bl(D, s-x), bl(D, t-x), INF-x)
for i in range(Q):
    print(st.getmax(i))

Solution (Python):
import collections

def main():
    N, Q = [int(x) for x in input().split()]
    updates1 = []
    updates2 = []
    for i in range(N):
        S, T, X = [int(x) for x in input().split()]
        updates1.append((S-X, X))
        updates2.append((T-X, X))
 
    active = []
    to_delete = collections.defaultdict(int)
    import heapq
    heapq.heapify(updates1)
    heapq.heapify(updates2)
    for _ in range(Q):
        x = int(input())
        while updates1 and updates1[0][0] <= x:
            coord, val = heapq.heappop(updates1) 
            heapq.heappush(active, val)
        
        while updates2 and updates2[0][0] <= x:
            coord, val = heapq.heappop(updates2)
            to_delete[val] += 1
 
        while active and to_delete[active[0]] > 0:
            to_delete[active[0]] -= 1
            heapq.heappop(active)
        print active[0] if active else -1










py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            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')


import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'


def readnumbers(zero = 0):
    conv = ord if py2 else lambda x:x
    A = []; numb = zero; sign = 1; i = 0; s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'0' [0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-' [0]: sign = -1
            elif s[i] != b'\r' [0]:
                A.append(sign*numb)
                numb = zero; sign = 1
            i += 1
    except:pass
    if s and s[-1] >= b'0' [0]:
        A.append(sign*numb)
    return A

if __name__== "__main__":
  main()

Solution (Python):
import sys
input = sys.stdin.readline
import heapq
from operator import itemgetter
from bisect import bisect_right
N, Q = map(int, input().split())
Stop = []
for i in range(N):
    S, T, X = map(int, input().split())
    Stop.append([S - X, X, 0, i])
    Stop.append([T - X, X, 1, i])
Stop.sort(key=itemgetter(0))
q = []
notClosed = [False]*N
A = [(-1, -1)]
for time, pos, lr, idx in Stop:
    if lr==0:
        heapq.heappush(q, (pos, idx))
    else:
        notClosed[idx] = True
        while len(q)>0 and notClosed[q[0][1]]:
            aaa = heapq.heappop(q)[1]

    if len(q):
        A.append((time, q[0][0]))
    else:
        A.append((time, -1))
A0 = list(map(itemgetter(0), A))
for _ in range(Q):
    D = int(input())
    idx = bisect_right(A0, D)

    print(A[idx-1][1])

Solution (Python):
import sys
input = sys.stdin.readline
import bisect
n, q = map(int, input().split())

ran = []
for i in range(n):
    s, t, x = map(int, input().split())
    ran.append((s-x, t-x-1, x))
ran.sort(key=lambda a: a[2])

qu = []
convert = {}
for i in range(q):
    que = int(input())
    convert[que] = i
    qu.append(que)
qu.sort()

memo = [-1] * q

ans = [-1] * q

for i in range(n):
    x = ran[i][2]
    l = ran[i][0]
    r = ran[i][1]
    ql = bisect.bisect_left(qu, l)
    qr = bisect.bisect_right(qu, r)
    if ql >= qr:
        continue
    while ql < qr:
        if memo[ql] >= 0:
            ql = memo[ql]
        else:
            memo[ql] = qr
            ans[convert[qu[ql]]] = x
            ql += 1

for i in ans:
    print(i)

Solution (Python):
import sys
from collections import deque
from collections import defaultdict
import math
sys.setrecursionlimit(20000000)
input = sys.stdin.readline

n,q = map(int,input().split())
x = []
for i in range(n):
        x.append(list(map(int,input().split())))
x.sort(key = lambda x : x[2])
dd = []
zaa = []
for i in range(q):
        a = int(input())
        dd.append(a)
        zaa.append(a)
y = []

for i in range(n):
        a = x[i][0]-x[i][2]
        b = x[i][1]-1-x[i][2]
        y.append([a,b])
        zaa.append(a)
        zaa.append(b)
import bisect
ans = [-1]*q
tobi = [-1]*q

for i in range(n):
        xx = bisect.bisect_left(dd,y[i][0])
        yy = bisect.bisect_left(dd,y[i][1]+1)
        j = xx
 
 
        while j < yy:
                if ans[j] == -1:
                        ans[j] = x[i][2]
                        tobi[j] = yy
                        j += 1
                        
                else:
                        j = tobi[j]
for i in ans:
        print(i)

Solution (Python):
import bisect
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
kouzi = []
for _ in range(N):
    S, T, X = map(int, input().split())
    kouzi.append([X, S, T-1])
kouzi.sort(reverse = True)

human = [int(input()) for _ in range(Q)]
ans = [-1]*(Q+1)


N0 = 2**(Q-1).bit_length()
data = [None]*(2*N0)
INF = (-1, 2**31-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]
t = 0
for task in kouzi:
    t += 1
    x = task[0]
    l = bisect.bisect_left(human, task[1]-x)
    r = bisect.bisect_right(human, task[2]-x)
    if l == r:
        continue
    update(l, r, (t, x))

for i in range(Q):
    q = query(i)
    if q == 2147483647:
        print(-1)
    else:
        print(q)

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

N,Q=map(int,input().split())
STOP=[list(map(int,input().split())) for i in range(N)]
D=[int(input()) for i in range(Q)]



seg_el=1<<((Q+1).bit_length())
SEG=[10**15]*(2*seg_el)

def updates(l,r,x):
    L=l+seg_el
    R=r+seg_el

    while L<R:
        if L & 1:
            SEG[L]=min(SEG[L],x)
            L+=1

        if R & 1:
            R-=1
            SEG[R]=min(SEG[R],x)
        L>>=1
        R>>=1

def getvalue(n,seg_el):
    i=n+seg_el
    ANS=SEG[i]
    
    
    while i!=0:
        i>>=1
        ANS=min(ANS,SEG[i],SEG[i])
        
    return ANS

for x,y,z in STOP:
    le=bisect.bisect_left(D,x-z)
    ri=bisect.bisect_left(D,y-z)

    updates(le,ri,z)

for d in range(Q):
    ANS=getvalue(d,seg_el)
    if ANS==10**15:
        print(-1)
    else:
        print(ANS)

Solution (Python):
from collections import defaultdict as di
import heapq

def main():
    inp = readnumbers()
    ii = 0
    
    n = inp[ii]
    ii += 1
    q = inp[ii]
    ii += 1

    starts = []
    ends = []

    for _ in range(n):
        s = inp[ii]
        ii += 1
        t = inp[ii]
        ii += 1
        x = inp[ii]
        ii += 1

        starts.append((s-x,x))
        ends.append((t-x,x))

    starts.sort(reverse=True)
    ends.sort(reverse=True)

    D = inp[ii:ii+q]
    ii += q

    count = di(int)
    active = []

    for d in D:
        while starts and starts[-1][0]<=d:
            _,x = starts.pop()
            heapq.heappush(active,x)
        while ends and ends[-1][0]<=d:
            _,x = ends.pop()
            count[x] += 1

        while active and count[active[0]]>0:
            x = heapq.heappop(active)
            count[x] -= 1

        if active:
            print active[0]

        else:
            print -1
        
        
    










py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            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')


import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'


def readnumbers(zero = 0):
    conv = ord if py2 else lambda x:x
    A = []; numb = zero; sign = 1; i = 0; s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'0' [0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-' [0]: sign = -1
            elif s[i] != b'\r' [0]:
                A.append(sign*numb)
                numb = zero; sign = 1
            i += 1
    except:pass
    if s and s[-1] >= b'0' [0]:
        A.append(sign*numb)
    return A

if __name__== "__main__":
  main()