Problem:
 Score : 500 points    Problem Statement There is an infinitely long street that runs west to east, which we consider as a number line.  There are N roadworks scheduled on this street.
The i -th roadwork blocks the point at coordinate X_i from time S_i - 0.5 to time T_i - 0.5 .  Q people are standing at coordinate 0 . The i -th person will start the coordinate 0 at time D_i , continue to walk with speed 1 in the positive direction and stop walking when reaching a blocked point.  Find the distance each of the Q people will walk.      Constraints  All values in input are integers.  1 \leq N, Q \leq 2 \times 10^5  0 \leq S_i < T_i \leq 10^9  1 \leq X_i \leq 10^9  0 \leq D_1 < D_2 < ... < D_Q \leq 10^9  If i \neq j and X_i = X_j , the intervals [S_i, T_i) and [S_j, T_j) do not overlap.         Input Input is given from Standard Input in the following format:  N  Q  S_1  T_1  X_1  :  S_N  T_N  X_N  D_1  :  D_Q       Output Print Q lines. The i -th line should contain the distance the i -th person will walk or -1 if that person walks forever.        Sample Input 1 4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8      Sample Output 1 2
2
10
-1
13
-1  The first person starts coordinate 0 at time 0 and stops walking at coordinate 2 when reaching a point blocked by the first roadwork at time 2 .  The second person starts coordinate 0 at time 1 and reaches coordinate 2 at time 3 . The first roadwork has ended, but the fourth roadwork has begun, so this person also stops walking at coordinate 2 .  The fourth and sixth persons encounter no roadworks while walking, so they walk forever. The output for these cases is -1 .

Solution (Python):

import re
import math
import fractions
import random
from heapq import heappop,heappush
import time
import sys
input = sys.stdin.readline

mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
 

 

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

for a in range(Q):
    E.append((int(input()),2,0))
E.sort()
 
S=set()
H=[]
for time_,type_,x in E:
    if type_==1:
        S.add(x)
        heappush(H,x)
    elif type_==0:
        S.remove(x)
    else:
        while H and H[0] not in S:
            heappop(H)
        print(H[0] if H else -1)

Solution (Python):

n,q = map(int,input().split())
import heapq
import sys
input = sys.stdin.readline
event = []
for _ in range(n):
  s,t,x = map(int,input().split())
  heapq.heappush(event,(s-x,t-x,x))
t = 0
now = []
for _ in range(q):
  d = int(input())
  if event:
    while event[0][0] <= d:
      tmp = heapq.heappop(event)
      heapq.heappush(now,(tmp[2],tmp[1]))
      if not event:
        break
  if now:
    while now[0][1] <= d:
      heapq.heappop(now)
      if not now:
        print(-1)
        break
    else:
      print(now[0][0])
  else:
    print(-1)

Solution (Python):
def main():

    import sys
    import heapq

    N, Q = map(int, sys.stdin.readline().split())
    events = []

    for i in range(N):
        s, t, x = map(int, sys.stdin.readline().split())
        events.append((s - x, 1, x))  
        events.append((t - x, -1, x))  

    for i in range(Q):
        d = int(input())
        events.append((d, 2, 0))

    events.sort()
    events.append([float('inf'), 'guard', None])

    i = 0
    closing = set()
    hq = []  
    while d >= events[i][0]:
        time, event, x = events[i]
        if event == 1:
            closing.add(x)
            heapq.heappush(hq, x)

        elif event == -1:
            closing.remove(x)

        else:
            while hq and (hq[0] not in closing):
                heapq.heappop(hq)

            if hq:
                print(hq[0])
            else:
                print(-1)

        i += 1


if __name__ == '__main__':
    main()

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
from heapq import heappush, heappop


I = sys.stdin.readlines()
N, Q = map(int, I[0].split())
P = []
for i in range(1, N + 1):
    s, t, x = map(int, I[i].split())
    P.append((s - x, t - 1 - x, x))
P.sort()


q = []
cur = 0
cnt = 0
for i in range(N + 1, N + Q + 1):
    d = int(I[i])
    while cur < N and P[cur][0] <= d:
        s, t, x = P[cur]
        heappush(q, (x, t))
        cnt += 1
        cur += 1
    ans = -1
    while cnt:
        if d <= q[0][1]:
            ans = q[0][0]
            break
        else:
            heappop(q)
            cnt -= 1
    print(ans)

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


I = sys.stdin.readlines()
N, Q = map(int, I[0].split())
P = []
for i in range(1, N + 1):
    s, t, x = map(int, I[i].split())
    P.append((s - x, t - 1 - x, x))
P.sort()


q = []
cur = 0
ans = [-1] * Q
for i in range(N + 1, N + Q + 1):
    d = int(I[i])
    while cur < N and P[cur][0] <= d:
        s, t, x = P[cur]
        heappush(q, (x, t))
        cur += 1
    while q and q[0][1] < d:
        heappop(q)
    if q:
        ans[i - N - 1] = q[0][0]

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

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


N, Q = map(int, input().split())
P = []
for i in range(1, N + 1):
    s, t, x = map(int, sys.stdin.readline().split())
    P.append((s - x, t - 1 - x, x))
P.sort()


q = []
cur = 0
ans = [-1] * Q
for i, d in enumerate(map(int, sys.stdin)):
    while cur < N and P[cur][0] <= d:
        s, t, x = P[cur]
        heappush(q, (x, t))
        cur += 1
    while q and q[0][1] < d:
        heappop(q)
    if q:
        ans[i] = q[0][0]

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

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


N, Q = map(int, input().split())
P = []
for i in range(1, N + 1):
    s, t, x = map(int, sys.stdin.readline().split())
    P.append((s - x, t - 1 - x, x))
P.sort()


q = []
cur = 0
ans = [-1] * Q
for i, d in enumerate(map(int, sys.stdin)):
    while cur < N and P[cur][0] <= d:
        s, t, x = P[cur]
        heappush(q, (x, t))
        cur += 1
    while q:
        x, t = q[0]
        if d <= t:
            ans[i] = x
            break
        else:
            heappop(q)

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

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


I = sys.stdin.readlines()
N, Q = map(int, I[0].split())
P = []
for i in range(1, N + 1):
    s, t, x = map(int, I[i].split())
    P.append((s - x, t - 1 - x, x))
P.sort()
INF = float('inf')
P.append((INF, INF, INF))

q = []
cur = 0
s, t, x = P[cur]
for i in range(N + 1, N + Q + 1):
    d = int(I[i])
    while s <= d:
        heappush(q, (x, t))
        cur += 1
        s, t, x = P[cur]
    ans = -1
    while len(q) > 0:
        x1, t1 = q[0]
        if d <= t1:
            ans = x1
            break
        else:
            heappop(q)
    print(ans)

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


I = sys.stdin.readlines()
N, Q = map(int, I[0].split())
P = []
for i in range(1, N + 1):
    s, t, x = map(int, I[i].split())
    P.append((s - x, t - 1 - x, x))
P.sort()


q = []
cur = 0
for i in range(N + 1, N + Q + 1):
    d = int(I[i])
    while cur < N and P[cur][0] <= d:
        s, t, x = P[cur]
        heappush(q, (x, t))
        cur += 1
    ans = -1
    while len(q) > 0:
        x, t = q[0]
        if d <= t:
            ans = x
            break
        else:
            heappop(q)
    print(ans)

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

n, q = map(int, sys.stdin.readline().split())
stx = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
*d, = map(int, sys.stdin.read().split())

def main():
    queue = []
    for s, t, x in stx:
        queue.append((s-x, 1, x))
        queue.append((t-x, 0, x))
    
    for i in range(q):
        queue.append((d[i], 2, i))
    
    queue.sort()

    res = [None] * q
    hq = []
    running = set()
    
    for t, f, x in queue:
        if f == 1:
            heappush(hq, x)
            running.add(x)
        elif f == 0:
            running -= set([x])
        elif f == 2:
            i = x
            while hq:
                if not hq[0] in running:
                    heappop(hq)
                    continue
                res[i] = hq[0]
                break
            else:
                res[i] = -1
    return res

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

Solution (Python):

import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
n,q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(n)]
D=[int(input()) for i in range(q)]
event=[]
for si,ti,xi in STX:
  event.append((si-xi,0,xi))
  event.append((ti-xi,-1,xi))
for di in D:
  event.append((di,1,di))
event.sort()
hq=[]; S=set()
for time, query, number in event:
  if query == 0:
    heapq.heappush(hq,number)
    S.add(number)
  elif query == -1:
    S.remove(number)
  else:
    while hq and hq[0] not in S:
      heapq.heappop(hq)
    if not hq:
      print(-1)
    else:
      print(hq[0])

Solution (Python):

import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(n)]
D=[int(input()) for i in range(q)]
event=[]
for si,ti,xi in STX:
  event.append((si-xi,0,xi))
  event.append((ti-xi,-1,xi))
for di in D:
  event.append((di,1,di))
event.sort()
hq=[]; S=set()
for time, query, number in event:
  if query == 0:
    heapq.heappush(hq,number)
    S.add(number)
  elif query == -1:
    S.remove(number)
  else:
    while hq and hq[0] not in S:
      heapq.heappop(hq)
    if not hq:
      print(-1)
    else:
      print(hq[0])

Solution (Python):

import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline()
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(n)]
D=[int(input()) for i in range(q)]
event=[]
for si,ti,xi in STX:
  event.append((si-xi,0,xi))
  event.append((ti-xi,-1,xi))
for di in D:
  event.append((di,1,di))
event.sort()
hq=[]; S=set()
ans = []
for time, query, number in event:
  if query == 0:
    heapq.heappush(hq,number)
    S.add(number)
  elif query == -1:
    S.remove(number)
  else:
    while hq and hq[0] not in S:
      heapq.heappop(hq)
    if not hq:
      ans.append(-1)
    else:
      ans.append(hq[0])
print(*ans,sep="\n")

Solution (Python):

import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(n)]
D=[int(input()) for i in range(q)]
event=[]
for si,ti,xi in STX:
  event.append((si-xi,0,xi))
  event.append((ti-xi,-1,xi))
for di in D:
  event.append((di,1,di))
event.sort()
hq=[]; S=set()
ans = []
for time, query, number in event:
  if query == 0:
    heapq.heappush(hq,number)
    S.add(number)
  elif query == -1:
    S.remove(number)
  else:
    while hq and hq[0] not in S:
      heapq.heappop(hq)
    if not hq:
      ans.append(-1)
    else:
      ans.append(hq[0])
print(*ans,sep="\n")

Solution (Python):

import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(n)]
D=[int(input()) for i in range(q)]
event=[]
for si,ti,xi in STX:
  event.append((si-xi,0,xi))
  event.append((ti-xi,-1,xi))
for di in D:
  event.append((di,1,di))
event.sort()
hq=[]; S=set()
for time, query, number in event:
  if query == 0:
    heapq.heappush(hq,number)
    S.add(number)
  elif query == -1:
    S.remove(number)
  else:
    while hq and hq[0] not in S:
      heapq.heappop(hq)
    if not hq:
      print(-1)
    else:
      print(hq[0])

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')


from heapq import heappush,heappop

n,q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(n)]
D=[int(input()) for i in range(q)]
event=[]
for si,ti,xi in STX:
  event.append((si-xi,0,xi))
  event.append((ti-xi,-1,xi))
for di in D:
  event.append((di,1,di))
event.sort()
hq=[]; S=set()
for time, query, number in event:
  if query == 0:
    heappush(hq,number)
    S.add(number)
  elif query == -1:
    S.remove(number)
  else:
    while hq and hq[0] not in S:
      heappop(hq)
    if not hq:
      print(-1)
    else:
      print(hq[0])

Solution (Python):

import sys
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')


from heapq import heappush,heappop

n,q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(n)]
D=[int(input()) for i in range(q)]
event=[]
for si,ti,xi in STX:
  event.append((si-xi,0,xi))
  event.append((ti-xi,-1,xi))
for di in D:
  event.append((di,1,di))
event.sort()
hq=[]; S=set()
for time, query, number in event:
  if query == 0:
    heappush(hq,number)
    S.add(number)
  elif query == -1:
    S.remove(number)
  else:
    while hq and hq[0] not in S:
      heappop(hq)
    if not hq:
      print(-1)
    else:
      print(hq[0])

Solution (Python):

import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(n)]
D=[int(input()) for i in range(q)]
event=[]
for si,ti,xi in STX:
  event.append((si-xi,0,xi))
  event.append((ti-xi,-1,xi))
for di in D:
  event.append((di,1,di))
event.sort()
hq=[]; S=set()
for time, query, number in event:
  if query == 0:
    heapq.heappush(hq,number)
    S.add(number)
  elif query == -1:
    S.remove(number)
  else:
    while hq and hq[0] not in S:
      heapq.heappop(hq)
    if not hq:
      print(-1)
    else:
      print(hq[0])

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

import heapq

def main():
  n, q = map(int, input().split())
  event = []
  stop = set()
  minque = []
  for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s-x, 1, x))
    event.append((t-x, -1, x))
  event.sort()
  event.append((float("inf"), 0, 0))
  D = list(map(int, read().split()))
  now = 0
  for t, b, x in event:
    while minque and minque[0] not in stop:
      heapq.heappop(minque)
    m = minque[0] if minque else -1
    while t > D[now]:
      print(m)
      now += 1
      if now == q:
        exit()
    if b == 1:
      stop.add(x)
      heapq.heappush(minque, x)
    else:
      stop.remove(x)
      
if __name__ == "__main__":
  main()

Solution (Python):
N,Q = map(int,input().split())
STX = [tuple(map(int,input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]

starts = []
ends = []
for i,(s,t,x) in enumerate(STX):
    starts.append((s-x,i))
    ends.append((t-x,i))
starts.sort(key=lambda x:x[0], reverse=True)
ends.sort(key=lambda x:x[0], reverse=True)

import heapq
hq = []
heapq.heapify(hq)
delset = set()

ans = []
for d in D:
    while starts and starts[-1][0] <= d:
        _,i = starts.pop()
        x = STX[i][2]
        heapq.heappush(hq, x*N+i)
    while ends and ends[-1][0] <= d:
        _,i = ends.pop()
        delset.add(i)
    while hq:
        i = hq[0]%N
        if i in delset:
            heapq.heappop(hq)
        else:
            break
    if len(hq)==0:
        ans.append(-1)
    else:
        ans.append(hq[0]//N)

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

Solution (Python):
import sys
from heapq import heappush,heappop
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,1,x))
  e.append((t-x,-1,x))
for i in range(q):
  d=int(input())
  e.append((d,2,0))
e.sort()
s=set()
a=[]
for time_,type_,x_ in e:
  if type_==1:
    s.add(x_)
    heappush(a,x_)
  elif type_==-1:
    s.remove(x_)
  else:
    while a and a[0] not in s:
      heappop(a)
    if a:
      print(a[0])
    else:
      print(-1)

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


class SegmentTree:
    def __init__(self, N):
        tmp = 1
        while tmp < N:
            tmp <<= 1
        
        self.N = tmp
        
        
        self.data = [float('inf') for _ in range(2*self.N)]

    
    
    def update(self, l, r, x):
        L = l + self.N
        R = r + self.N
        while L < R:
            if L & 1:
                self.data[L] = min([self.data[L], x])
                L += 1
            if R & 1:
                R -= 1
                self.data[R] = min([self.data[R], x])
            L >>= 1
            R >>= 1

    def query(self, k):
        k += self.N
        res = self.data[k]
        while k != 1:
            k >>= 1
            res = min(res, self.data[k])
        return res



def main():
    N, Q = map(int, input().split())
    road = []
    for _ in range(N):
        S, T, X = map(int, input().split())
        road.append((S,T,X))

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

    st = SegmentTree(Q)
    for S, T, X in road:
        l = bisect_left(D, S - X)
        r = bisect_left(D, T - X)
        st.update(l, r, X)

    for q in range(Q):
        ans = st.query(q)
        if ans == float('inf'):
            print(-1)
        else:
            print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

def main():
    N,Q = list(map(int,input().split()))

    road = []
    x_list = []

    for i in range(N):
        s,t,x = list(map(int,input().split()))
        road.append([0,s-x,x])
        road.append([1,t-x,x])

    for i in range(Q):
        road.append([2,int(input()),i])

    from collections import defaultdict

    counter = defaultdict(int)
    counter[10**27] = 1
    ans = [0]*Q

    road.sort(key=lambda x:x[0])
    road.sort(key=lambda x:x[1])

    q = [10**27]

    from heapq import heappop,heappush

    for id,_,x in road:
        if id==0:
            heappush(q,x)
            counter[x]+=1
        elif id==1:
            counter[x]-=1
        else:
            while counter[q[0]]==0:
                heappop(q)
            
            if q[0]<10**27:
                ans[x] = q[0]
            else:
                ans[x] = -1
    print("\n".join(map(str,ans)))

if __name__ == '__main__':
    main()

Solution (Python):

import re
import math
import fractions
import random
from heapq import heappop,heappush
import time
import sys
input = sys.stdin.readline

mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
 

 

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

for a in range(Q):
    E.append((int(input()),2,0))
E.sort()
 
S=set()
H=[]
for time_,type_,x in E:
    if type_==1:
        S.add(x)
        heappush(H,x)
    elif type_==0:
        S.remove(x)
    else:
        while H and H[0] not in S:
            heappop(H)
        print(H[0] if H else -1)

Solution (Python):

import re
import math
import fractions
import random
from heapq import heappop,heappush
import time
import sys
input = sys.stdin.readline


 

 

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

for a in range(Q):
    E.append((int(input()),2,0))
E.sort()
 
S=set()
H=[]
for time_,type_,x in E:
    if type_&1:
        S.add(x)
        heappush(H,x)
    elif not type_:
        S.remove(x)
    else:
        while H and H[0] not in S:
            heappop(H)
        print(H[0] if H else -1)

Solution (Python):

import re
import math
import fractions
import random
import heapq
import time
import sys
input = sys.stdin.readline

mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
 
 

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

for a in range(Q):
    E.append([int(input()),0,0])
E.sort(key=lambda x:x[0])
 
S=set()
H=[]
for time_,type_,x in E:
    if type_==1:
        
        S.add(x)
        heapq.heappush(H,x)
    elif type_==-1:
        if(x in S):S.remove(x)
    else:
        while H and H[0] not in S:
            heapq.heappop(H)
        print(H[0] if H else -1)

Solution (Python):

import re
import math
import fractions
import random
import heapq
import time
import sys
input = sys.stdin.readline

mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
 
 

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

for a in range(Q):
    E.append([int(input()),0,0])
E.sort(key=lambda x:x[0])
 
S=set()
H=[]
for time_,type_,x in E:
    if type_==1:
        S.add(x)
        heapq.heappush(H,x)
    elif type_==-1:
        if(x in S):S.remove(x)
    else:
        while H and H[0] not in S:
            heapq.heappop(H)
        print(H[0] if H else -1)

Solution (Python):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) 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 FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,Q=LI()
HQ=[]
EVS=[]
for i in range(N):
    S,T,X=LI()
    EVS.append((S-0.5-X, 1, X))
    EVS.append((T-0.5-X, 0, X))
for i in range(Q):
    D=II()
    EVS.append((D, 2, D))
EVS.sort()

st=set()
PQ=[]
for time, ev, loc in EVS:
    if ev == 1:
        heapq.heappush(PQ, loc)
        st.add(loc)
    elif ev == 0:
        st.remove(loc)
    else:
        while PQ and PQ[0] not in st:
            heapq.heappop(PQ)
        if PQ:
            print(PQ[0])
        else:
            print(-1)

Solution (Python):
import sys
input = sys.stdin.readline
n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 
def update(k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x,True,x,i), (t-x,False,x,i)]
    qs = []
    for _ in range(Q):
        qs.append(int(input()))
    xs.sort(key=lambda x:x[0])
    j = 0
    for x in xs:
        while Q-j and qs[j] < x[0]:
            print(segl[0] if segl[0]!= mx else -1)
            j += 1
        update(x[3], x[2] if x[1] else mx)
    while Q-j:
        print(-1)
        j+=1

Solution (Python):
import sys
input = sys.stdin.readline
n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 
def update(k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x,True,x,i), (t-x,False,x,i)]
    qs = []
    for _ in range(Q):
        qs.append(int(input()))
    xs.sort(key=lambda x:x[0])
    j = 0
    for x in xs:
        while Q-j:
            if qs[j] < x[0]:
                print(segl[0] if segl[0]!= mx else -1)
                j += 1
                continue
            break
        update(x[3], x[2] if x[1] else mx)
    while Q-j:
        print(-1)
        j+=1

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

n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 

def update(k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
    for _ in range(Q):
        xs.append((int(input()),2))
    xs.sort(key=lambda x:x[0])
    for x in xs:
        if x[1]==2:
            print(segl[0] if segl[0]!= mx else -1)
            continue
        update(x[3], x[2] if x[1] else mx)

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

N,Q = map(int,input().split(" "))
querys = []
START = 1
GOAL = 0
GO = 2

for _ in range(N):
    s,t,x = (map(int,input().split(" ")))
    s -=(x + 0.5)
    t -= (x + 0.5)
    querys.append( (s,START,x) )
    querys.append( (t,GOAL,x) )

for _ in range(Q):

    querys.append( (int(input()),GO,-1)  )
koji_place = []
koji_um = set([])
heapq.heapify(koji_place)
querys.sort()
for query in querys:
    time,qtype,place = query
    if qtype == START:
        heapq.heappush(koji_place,place)
        koji_um.add(place)
    elif qtype == GOAL:
        koji_um.remove(place)
    else:
        while koji_place and koji_place[0] not in koji_um: 
            heapq.heappop(koji_place) 
            
        if not koji_place:
            print(-1)
        else:
            print(koji_place[0])

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

N,Q = map(int,input().split(" "))
querys = []
START = 1
GOAL = 0
GO = 2

for _ in range(N):
    s,t,x = (map(int,input().split(" ")))
    s -=(x + 0.5)
    t -= (x + 0.5)
    querys.append( (s,START,x) )
    querys.append( (t,GOAL,x) )

for _ in range(Q):

    querys.append( (int(input()),GO,-1)  )
koji_place = []
koji_um = set([])
heapq.heapify(koji_place)
querys.sort()
for query in querys:
    time,qtype,place = query
    if qtype == START:
        heapq.heappush(koji_place,place)
        koji_um.add(place)
    elif qtype == GOAL:
        koji_um.remove(place)
    else:
        while koji_place and koji_place[0] not in koji_um: 
            heapq.heappop(koji_place) 
            
        if koji_place:
            print(koji_place[0])
        else:
            print(-1)