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 ctypes import *
import subprocess as sp
from operator import itemgetter
import sys

set_code = r"""


std::set<int> s;

void add(int x) {
    s.insert(x);
}

bool find(int x) {
    return s.find(x) != s.end();
}

void remove(int x) {
    s.erase(x);
}

bool empty() {
	return s.empty();
}

int getMin() {
	return *s.begin();
}
"""

class CppSet:
	counter = 0

	def __init__(self):
		lib_name = './hoge{}.so'.format(CppSet.counter)
		code_file_name = "tmp.cpp"
		with open(code_file_name, "w") as f:
			f.write(set_code)

		CppSet.counter += 1
		sp.Popen(['g++', '-fPIC', '-shared', '-std=c++11', code_file_name, '-o', lib_name]).communicate()

		lib = CDLL(lib_name)
		self.add = getattr(lib, "_Z3addi")
		self.find = CFUNCTYPE(c_bool, c_int)(
						("_Z4findi", lib),
						((1, "x"), )
					)
		self.remove = getattr(lib, "_Z6removei")
		self.empty = CFUNCTYPE(c_bool)(
						("_Z5emptyv", lib),
						()
					)

		self.getMin = CFUNCTYPE(c_int)(
						("_Z6getMinv", lib),
						()
					)

def main():
	N, Q = map(int, sys.stdin.readline().split())
	tmp = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
	stx = [(s - x, 1, x) for s, t, x in tmp] + [(t - x, -1, x) for s, t, x in tmp]
	stx.sort()
	
	D = [int(sys.stdin.readline()) for _ in range(Q)] 
	ans = [-1]*Q

	idx = 0
	stx_len = len(stx)
	se = CppSet()
	for i, d in enumerate(D):
		while idx < stx_len:
			t, com, x = stx[idx]
			if t > d:
				break
			if com == 1:
				se.add(x)
			else:
				se.remove(x)
			idx += 1
		ans[i] = (-1 if se.empty() else se.getMin())

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

if __name__ == "__main__":
	main()

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

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


from bisect import bisect_left

n, q = li()

stx = [list(li()) for _ in range(n)]
d = [ni() for _ in range(q)]

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

ans = [-1]*q
skip = [-1]*q

for si, ti, xi in stx:
    left = bisect_left(d, si-xi)
    right = bisect_left(d, ti-xi)

    while left < right:
        if skip[left] == -1:
            ans[left] = xi
            skip[left] = right
            left += 1

        else:
            left = skip[left]

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

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):
from operator import itemgetter
import sys

input = sys.stdin.readline

inf = float('inf')

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

events = []
method_events_append = events.append

for _ in range(N):
    s, t, x = map(int, input().split())
    method_events_append((s - x, 1, x))  
    method_events_append((t - x, -1, x))  

events.sort(key=itemgetter(0))  

under_construction = set()
method_uc_add = under_construction.add
method_uc_discard = under_construction.discard

min_stop = inf
not_chg_flg = True

cur = 0
for _ in range(Q):
    d = int(input())
    while cur < N * 2 and events[cur][0] <= d:
        exec_time, event_type, under_construction_x = events[cur]
        if event_type == 1:  
            method_uc_add(under_construction_x)
            if not_chg_flg:  
                min_stop = min(min_stop, under_construction_x)
        else:  
            method_uc_discard(under_construction_x)
            if not_chg_flg and min_stop == under_construction_x:
                not_chg_flg = False
        cur += 1

    if not not_chg_flg:
        min_stop = min(under_construction) if under_construction else inf
        not_chg_flg = True
    print(min_stop if min_stop != inf else -1)

Solution (Python):
from operator import itemgetter
import sys

input = sys.stdin.readline

inf = float('inf')

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

events = []

for _ in range(N):
    s, t, x = map(int, input().split())
    add_event = (s - x, 1, x)
    remove_event = (t - x, -1, x)
    events.append(add_event)
    events.append(remove_event)

events.sort(key=itemgetter(0))  

under_construction = set()

min_stop = inf
chg_flg = False

cur = 0
for _ in range(Q):
    d = int(input())
    while cur < N * 2 and events[cur][0] <= d:
        exec_time, event_type, under_construction_x = events[cur]
        if event_type == 1:  
            under_construction.add(under_construction_x)
            if not chg_flg:
                min_stop = min(min_stop, under_construction_x)
        else:  
            under_construction.discard(under_construction_x)
            if not chg_flg and min_stop == under_construction_x:
                chg_flg = True
        cur += 1

    if chg_flg:
        min_stop = min(under_construction) if under_construction else inf
        chg_flg = False
    print(min_stop if min_stop != inf else -1)

Solution (Python):

def BinarySearchLowerBound(_arr, _ele): 
    low_ind = 0
    up_ind = len(_arr) - 1
    if _arr[low_ind] >= _ele:
        return low_ind
    if _arr[up_ind] <= _ele:
        return up_ind + 1
    found = None
    while (up_ind - low_ind) > 1:
        mid = (up_ind + low_ind) / 2
        if _arr[mid] < _ele:
            low_ind = mid
        elif _arr[mid] > _ele:
            up_ind = mid
        elif _arr[mid] == _ele:
            found = mid
            break
    if found is not None:
        cnt = found
    else:
        cnt = up_ind
    return cnt

def solve():
    N, Q = [int(_) for _ in raw_input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in raw_input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append(int(raw_input()))
    STX.sort(key = lambda x:x[2])
    
    ans = [-1] * Q
    l = [None] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        if len(D) == 0:
            break
        lit = BinarySearchLowerBound(D, Li)
        rit = BinarySearchLowerBound(D, Ri)
        while lit < rit:
            if l[lit] is not None:
                lit = l[lit]
            else:
                ans[lit] = Xi
                l[lit] = rit
                lit += 1
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()

Solution (Python):
from bisect import bisect_left as bisect
N,Q = map(int,input().split())
event = [tuple(map(int,input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]

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

ans = [-1]*Q
neg = [-1]*Q

for s,t,x in event:
    l = bisect(D,s-x)
    r = bisect(D,t-x)
    t = l
    while t < r:
        if neg[t] == -1:
            ans[t] = x
            neg[t] = r
            t += 1
        else:
            t = neg[t]

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

Solution (Python):
import bisect

def solve():
    N, Q = [int(_) for _ in raw_input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in raw_input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(raw_input()), i))
    STX.sort(key = lambda x:x[2])
    
    ans = [-1] * Q
    l = [None] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        lit = bisect.bisect_left(D, (Li, -1))
        rit = bisect.bisect_left(D, (Ri, -1))
        while lit < rit:
            if l[lit] is not None:
                lit = l[lit]
            else:
                ans[D[lit][1]] = Xi
                l[lit] = rit
                lit += 1
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()

Solution (Python):

from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  
            skip[t] = r  
            t += 1
        else:
            t = skip[t]  
print(*ans, sep='\n')

Solution (Python):



from bisect import bisect_left
N, Q = map(int, input().split())
consts = []
for _ in range(N):
    s,t,x = map(int, input().split())
    consts.append((x,s,t))
consts.sort()
D=[int(input()) for _ in range(Q)]
ans=[-1]*Q
jump=[-1]*Q
for x,s,t in consts:
    left=bisect_left(D,s-x)
    right=bisect_left(D,t-x)
    while left<right:
        if jump[left]==-1:
            ans[left]=x
            jump[left]=right
            left += 1
        else:
            left=jump[left]
print(*ans, sep='\n')

Solution (Python):
from bisect import bisect_left
N, Q = map(int, input().split())
consts = []
for _ in range(N):
    s,t,x = map(int, input().split())
    consts.append((x,s,t))
consts.sort()
D=[int(input()) for _ in range(Q)]
ans=[-1]*Q
jump=[-1]*Q
for x,s,t in consts:
    left=bisect_left(D,s-x)
    right=bisect_left(D,t-x)
    while left<right:
        if jump[left]==-1:
            ans[left]=x
            jump[left]=right
            left += 1
        else:
            left=jump[left]
print(*ans, sep='\n')

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

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))


def main():
    N ,Q = ints_raw()
    origST = []

    for _  in range(N):
        S,T,X = ints_raw()
        origST.append([S-X,T-X,X])
    Ds = [int(input()) for _ in range(Q)]

    origST.sort()
    stidx = 0
    cur_set = []
    for d in Ds:

        while stidx < len(origST):
            st = origST[stidx]
            if st[0] > d:
                break
            heappush(cur_set,(st[2],st[1]))
            stidx+=1
        while cur_set and cur_set[0][1] <=d:
            heappop(cur_set)
        if cur_set:
            print(cur_set[0][0])
        else:
            print(-1)
main()

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

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))


def main():
    N ,Q = ints_raw()
    origST = []

    for idx  in range(N):
        S,T,X = ints_raw()
        origST.append([S-X,T-X,X])
    Ds = [int(input()) for _ in range(Q)]

    origST.sort()
    stidx = 0
    cur_set = []
    for q in Ds:

        while stidx < len(origST):
            st = origST[stidx]
            if st[0] > q:
                break
            heappush(cur_set,(st[2],st[1]))
            stidx+=1
        while cur_set and cur_set[0][1] <=q:
            heappop(cur_set)
        if len(cur_set)==0:
            print(-1)
        else:
            print(cur_set[0][0])
main()

Solution (Python):
import sys
import bisect


class DualSegmentTree():

    def __init__(self, n):
        INF = float("inf")
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [INF] * (2*self.size - 1)

    def update(self, begin, end, val):
        begin += (self.size - 1)
        end += (self.size - 1)
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                self.node[end] = min(val, self.node[end])
            if (begin - 1) & 1:
                self.node[begin] = min(val, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2

    def get_val(self, i):
        i += (self.size - 1)
        val = self.node[i]
        while i > 0:
            i = (i - 1) // 2
            val = min(val, self.node[i])
        return val

n, q = map(int, input().split())
info = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
d = [int(sys.stdin.readline()) for i in range(q)]
INF = float("inf")

st = DualSegmentTree(len(d)+1)

for i in range(n):
    a, b = info[i][0] - info[i][2], info[i][1] - info[i][2]  
    l = bisect.bisect_left(d, a)
    r = bisect.bisect_left(d, b)
    st.update(l, r, info[i][2])

for i in range(q):
    tmp = st.get_val(i)
    if tmp == float("inf"):
        print(-1)
    else:
        print(tmp)

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

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

cons.sort(key=lambda x: x[2])
for i in range(n):
    cons[i][0] -= cons[i][2]
    cons[i][1] -= cons[i][2]

ans = [-1] * q
l = [-1] * q
for i in range(n):
    s = bisect.bisect_left(d, cons[i][0])
    t = bisect.bisect_left(d, cons[i][1])
    while s < t:
        if l[s] != -1:
            s = l[s]
        else:
            ans[s] = cons[i][2]
            l[s] = t
            s += 1
print(*ans, sep="\n")

Solution (Python):
import bisect

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

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

list_xst.sort(key=lambda l:l[0])

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

retn = [-1] * q
jmp = [-1] * q

for x,s,t in list_xst:
    i = bisect.bisect_left(list_d, s)
    tt = bisect.bisect_left(list_d, t)
    while i < tt:
        if (jmp[i] != -1):
            i = jmp[i]
        else:
            retn[i] = x
            jmp[i] = tt
            i += 1

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

Solution (Python):
import sys
from itertools import accumulate
from collections import Counter
from bisect import bisect as br, bisect_left as bl
from operator import itemgetter
class DammyMap:
    
    def __init__(self, A, B):
        
        
        self.X = B[:]
        self.comp = {v : k for k, v in enumerate(D, 1)}
        self.size = len(self.X)
        self.tree = [0] * (self.size + 1)
        self.p = 2**(self.size.bit_length() - 1)
        self.dep = self.size.bit_length()
        
        CA = Counter(A)
        S = [0] + list(accumulate([CA[self.X[i]] for i in range(self.size)]))
        for i in range(1, 1+self.size):
            self.tree[i] = S[i] - S[i - (i&-i)]
        
    def compress(self, L):
        
        L2 = list(set(L))
        L2.sort()
        C = {v : k for k, v in enumerate(L2, 1)}
        
        return L2, C
    
    def leng(self):
        
        return self.count(self.size)
    
    def count(self, i):
        
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def less(self, v):
        
        i = bl(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def leq(self, v):
        
        i = br(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        
        i = self.comp[i]
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        
        
    def get(self, v):
        
        if v <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < v:
                s += k
                v -= self.tree[s]
            k //= 2
        return self.X[s]

N, Q = map(int, input().split())
stx = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
stx.sort(key = itemgetter(2))
D = [int(sys.stdin.readline()) for _ in range(Q)] 

T = DammyMap(D, D)
ans = [-1]*Q

for s, t, x in stx:
    tl = T.less(s - x)
    tr = T.less(t - x)
    d = tr - tl
    for _ in range(d):
        i = T.get(tl + 1)
        T.add(i, -1)
        ans[T.comp[i]-1] = x
print(*ans, sep = '\n')

Solution (Python):
import sys
from itertools import accumulate
from collections import Counter
from bisect import bisect as br, bisect_left as bl
from operator import itemgetter
class DammyMap:
    
    def __init__(self, A, B):
        
        self.X, self.comp = self.compress(B)
        self.size = len(self.X)
        self.tree = [0] * (self.size + 1)
        self.p = 2**(self.size.bit_length() - 1)
        self.dep = self.size.bit_length()
        
        CA = Counter(A)
        S = [0] + list(accumulate([CA[self.X[i]] for i in range(self.size)]))
        for i in range(1, 1+self.size):
            self.tree[i] = S[i] - S[i - (i&-i)]
        
    def compress(self, L):
        
        L2 = list(set(L))
        L2.sort()
        C = {v : k for k, v in enumerate(L2, 1)}
        
        return L2, C
    
    def leng(self):
        
        return self.count(self.size)
    
    def count(self, i):
        
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def less(self, v):
        
        i = bl(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def leq(self, v):
        
        i = br(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        
        i = self.comp[i]
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        
        
    def get(self, v):
        
        if v <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < v:
                s += k
                v -= self.tree[s]
            k //= 2
        return self.X[s]

def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C

N, Q = map(int, input().split())
stx = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
stx.sort(key = itemgetter(2))
D = [int(sys.stdin.readline()) for _ in range(Q)] 
_, comp = compress(D)

T = DammyMap(D, D)

ans = [-1]*Q

for s, t, x in stx:
    tl = T.less(s - x)
    tr = T.less(t - x)
    d = tr - tl
    for _ in range(d):
        i = T.get(tl + 1)
        T.add(i, -1)
        ans[comp[i]] = x
print(*ans, sep = '\n')

Solution (Python):
import sys
from itertools import accumulate
from collections import Counter
from bisect import bisect as br, bisect_left as bl
from operator import itemgetter
class DammyMap:
    
    def __init__(self, A, B):
        
        self.X, self.comp = self.compress(B)
        self.size = len(self.X)
        self.tree = [0] * (self.size + 1)
        self.p = 2**(self.size.bit_length() - 1)
        self.dep = self.size.bit_length()
        
        CA = Counter(A)
        S = [0] + list(accumulate([CA[self.X[i]] for i in range(self.size)]))
        for i in range(1, 1+self.size):
            self.tree[i] = S[i] - S[i - (i&-i)]
        
    def compress(self, L):
        
        L2 = list(set(L))
        L2.sort()
        C = {v : k for k, v in enumerate(L2, 1)}
        
        return L2, C
    
    def leng(self):
        
        return self.count(self.size)
    
    def count(self, i):
        
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def less(self, v):
        
        i = bl(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def leq(self, v):
        
        i = br(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        
        i = self.comp[i]
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        
        
    def get(self, v):
        
        if v <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < v:
                s += k
                v -= self.tree[s]
            k //= 2
        return self.X[s]

def compress(L):
    
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C

N, Q = map(int, input().split())
stx = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
stx.sort(key = itemgetter(2))
D = [int(sys.stdin.readline()) for _ in range(Q)] 
_, comp = compress(D)

T = DammyMap(D, D)

ans = [-1]*Q

for s, t, x in stx:
    tl = T.less(s - x)
    tr = T.less(t - x)
    d = tr - tl
    for _ in range(d):
        i = T.get(tl + 1)
        T.add(i, -1)
        ans[comp[i]] = x
for a in ans:
    print(a)

Solution (Python):
from bisect import bisect_left
from operator import itemgetter
import sys

input = sys.stdin.readline

N, Q = map(int, input().split(" "))
check_points = [tuple(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = [-1] * Q
jump = [-1] * Q
check_points = sorted(check_points, key=itemgetter(2))
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    while left < right:
        if time[left] == -1:
            time[left] = x
            jump[left] = right
            left += 1
        else:
            left = jump[left]

for t in time:
    print(t)

Solution (Python):
from bisect import bisect_left
from operator import itemgetter

N, Q = map(int, input().split(" "))
check_points = [tuple(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = [-1] * Q
jump = [-1] * Q
check_points = sorted(check_points, key=itemgetter(2))
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    while left < right:
        if time[left] == -1:
            time[left] = x
            jump[left] = right
            left += 1
        else:
            left = jump[left]

for t in time:
    print(t)

Solution (Python):
from bisect import bisect_left
from operator import itemgetter

N, Q = map(int, input().split(" "))
check_points = [tuple(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = [-1 for _ in range(Q)]
jump = [-1 for _ in range(Q)]
check_points = sorted(check_points, key=itemgetter(2))
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    while left < right:
        if time[left] == -1:
            time[left] = x
            jump[left] = right
            left += 1
        else:
            left = jump[left]

for t in time:
    print(t)

Solution (Python):
import sys
from bisect import *

input = sys.stdin.readline

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

    ds = []
    for i in range(q):
        d = int(input())
        ds.append(d)

    ans = [-1] * q
    jump = [-1] * q

    for x, s, t in xst:
        i = bisect_left(ds, s)
        fi = bisect_left(ds, t)
        while i < fi:
            if jump[i] != -1:
                i = jump[i]
            else:
                ans[i] = x
                jump[i] = fi
                i += 1

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

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

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

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

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

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

event.sort()

closed = []
ei = 0

for d in D :
    while ei < N and event[ei][0] <= d :
        heapq.heappush(closed, (event[ei][2], event[ei][1]))
        ei += 1
    while closed and closed[0][1] <= d :
        heapq.heappop(closed)
    
    if closed :
        print(closed[0][0])
    else :
        print(-1)

Solution (Python):
import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()

Solution (Python):


import sys
from bisect import bisect_left

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    closure = []
    for _ in range(N):
        start, end, pos = map(int, input().split())
        closure.append((pos, start, end))

    closure.sort()

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

    ans = [-1] * Q
    skip = [-1] * Q
    for pos, start, end in closure:
        left = bisect_left(D, start - pos)
        right = bisect_left(D, end - pos)

        while left < right:
            if skip[left] == -1:
                ans[left] = pos
                skip[left] = right
                left += 1
            else:
                left = skip[left]

    return ans


if __name__ == '__main__':
    print(*main(), sep='\n')

Solution (Python):

from bisect import bisect_left
from sys import stdin



readl = stdin.readline


N,Q = map(int, readl().rstrip().split())
STX = [list(map(int, readl().rstrip().split())) for _ in range(N)]
Dn = [None for _ in range(Q+1)]
for i in range(Q):
  Dn[i] = int(readl().rstrip())
Dn[Q] = 10**10
ans = [-1] * (Q+1)
skip = [-1] * (Q+1)

for s,t,x in sorted(STX,key=lambda x:x[2]):
  l = bisect_left(Dn,s-x)
  r = bisect_left(Dn,t-x)
  while l < r:
    if skip[l] < 0:
      ans[l] = x
      skip[l] = r
      l += 1
    else:
      l = skip[l]

for d in ans[:-1]:
  print(d)

Solution (Python):
from heapq import heappop as hpp, heappush as hp
import sys
N, Q = map(int, input().split())
stx = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
stx = [(s-x, t-x, x) for s, t, x in stx]
stx.sort(reverse = True)

D = [int(sys.stdin.readline()) for _ in range(Q)] 
H = []
ans = [None]*Q

for i, d in enumerate(D):
    while stx and stx[-1][0] <= d:
        hp(H, stx.pop()[1:][::-1])    
    while H and H[0][1] <= d:
        hpp(H)
    if not H:
        ans[i] = -1
    else:
        ans[i] = H[0][0]

for a in ans:
    print(a)

Solution (Python):
import sys
import bisect
 
N, Q = map(int, input().split(' '))
G = [list(map(int, sys.stdin.readline().split(' '))) for _ in range(N)]
T = [int(sys.stdin.readline()) for _ in range(Q)]

class SegTree :
    def __init__(self, n) :
        self.n = n
        self.A = [10**15] * (2 << (n + 1).bit_length())
 
    def update(self, l, r, val) :
      l += len(self.A) // 2
      r += len(self.A) // 2
      while l < r:
          if l & 1 :
              self.A[l] = min(self.A[l], val)
              l += 1
          if r & 1:
              self.A[r-1] = min(self.A[r-1], val)
              r -= 1
          l //= 2
          r //= 2

    def get(self, i) :
      i += len(self.A) // 2
      ret = self.A[i]
      while i > 0 :
          i //= 2
          ret = min(ret, self.A[i])
      return ret if ret < 10**15 else -1

ST = SegTree(Q)
for g in G :
    s = g[0] - g[2]
    e = g[1] - g[2]
 
    ll = bisect.bisect_left(T, s)
    rr = bisect.bisect_left(T, e)
 
    if ll == rr :
        continue
 
    ST.update(ll, rr, g[2])
 
for i in range(Q) :
    ans = ST.get(i)
    print(ans)

Solution (Python):
from bisect import bisect_left
import sys
n, Q = [int(x) for x in sys.stdin.readline().split()]
stx = [[int(x) for x in sys.stdin.readline().split()] for i in range(n)]
q = [int(sys.stdin.readline()) for i in range(Q)]
stx.sort(key=lambda x: x[2])
ans = [-1 for i in range(Q)]
skip = [-1 for i in range(Q)]

for (s, t, x) in stx:
  begin = bisect_left(q, s-x)
  end = bisect_left(q, t-x)
  while begin<end:
    if skip[begin]==-1:
      ans[begin] = x
      skip[begin] = end
      begin += 1
    else:
      begin = skip[begin]
for e in ans:
  print(e)