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 sys
input = sys.stdin.readline





class Segment:
    def __init__(self, N, init_val):
        """[セグメント木]

        Args:
            N ([int]): [要素数]
            init_val ([list]): [初期化する値]
        """
        self.identity_element = 2 ** 31 - 1  
        self.N0 = 1 << (N - 1).bit_length()
        
        self.dat = [self.identity_element] * (2 * self.N0)
        
        for i in range(N):
            self.dat[i + self.N0 - 1] = init_val[i]
        
        for i in range(self.N0 - 2, -1, -1):
            self.dat[i] = self.segfunc(self.dat[2 * i + 1], self.dat[2 * i + 2])

    
    def update(self, k, x):
        k += self.N0 - 1
        self.dat[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.dat[k] = self.segfunc(self.dat[2 * k + 1], self.dat[2 * k + 2])

    
    def query(self, l, r):
        L = l + self.N0
        R = r + self.N0
        s = self.identity_element
        
        while L < R:
            if R & 1:
                R -= 1
                s = self.segfunc(s, self.dat[R - 1])
            if L & 1:
                s = self.segfunc(s, self.dat[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return s

    def segfunc(self, x, y):
        return min(x, y)  


def compress(arr):
    *XS, = set(arr)
    XS.sort()
    return {e: i for i, e in enumerate(XS)}


n, q = map(int, input().split())
s, t, x = [0] * n, [0] * n, [0] * n
for i in range(n):
    s[i], t[i], x[i] = map(int, input().split())
    s[i] -= x[i]
    t[i] -= x[i]
    s[i] = max(s[i], 0)
    t[i] = max(t[i], 0)

d = [int(input()) for i in range(q)]

com = compress(s + t + d)
k = len(com) + 1

for i in range(n):
    s[i] = com[s[i]]
    t[i] = com[t[i]]

for i in range(q):
    d[i] = com[d[i]]
INF = 1 << 30
a = [INF] * k
b = [[] for i in range(k)]
c = [[] for i in range(k)]
seg = Segment(n, [INF] * n)
for i in range(n):
    b[s[i]].append(i)
    c[t[i]].append(i)

for i in range(k):
    for j in b[i]:
        seg.update(j, x[j])
    for j in c[i]:
        seg.update(j, INF)
    a[i] = seg.query(0, n)

for i in d:
    print(-1 if a[i] == INF else a[i])

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



class Segment:
    def __init__(self, N, init_val):
        self.N0 = 2 ** (N - 1).bit_length()
        
        self.dat = [identity_element] * (2 * self.N0)
        
        for i in range(N):
            self.dat[i + self.N0 - 1] = init_val[i]
        
        for i in range(self.N0 - 2, -1, -1):
            self.dat[i] = segfunc(self.dat[2 * i + 1], self.dat[2 * i + 2])

    
    def update(self, k, x):
        k += self.N0 - 1
        self.dat[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.dat[k] = segfunc(self.dat[2 * k + 1], self.dat[2 * k + 2])

    
    def query(self, l, r):
        L = l + self.N0
        R = r + self.N0
        s = identity_element
        
        while L < R:
            if R & 1:
                R -= 1
                s = segfunc(s, self.dat[R - 1])
            if L & 1:
                s = segfunc(s, self.dat[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return s





def segfunc(x, y):
    return min(x, y)  


identity_element = 2 ** 31 - 1  


def compress(arr):
    *XS, = set(arr)
    XS.sort()
    return {e: i for i, e in enumerate(XS)}


n, q = map(int, input().split())
s, t, x = [0] * n, [0] * n, [0] * n
for i in range(n):
    s[i], t[i], x[i] = map(int, input().split())
    s[i] -= x[i]
    t[i] -= x[i]
    s[i] = max(s[i], 0)
    t[i] = max(t[i], 0)

d = [int(input()) for i in range(q)]

com = compress(s + t + d)
k = len(com) + 1

for i in range(n):
    s[i] = com[s[i]]
    t[i] = com[t[i]]

for i in range(q):
    d[i] = com[d[i]]
INF = 1 << 30
a = [INF] * k
b = [[] for i in range(k)]
c = [[] for i in range(k)]
seg = Segment(n, [INF] * n)
for i in range(n):
    b[s[i]].append(i)
    c[t[i]].append(i)

for i in range(k):
    for j in b[i]:
        seg.update(j, x[j])
    for j in c[i]:
        seg.update(j, INF)
    a[i] = seg.query(0, n)

for i in d:
    print(-1 if a[i] == INF else a[i])

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

def main():
    n, q = map(int, input().split())
    
    key = []
    for i in range(n):
        s, t, x = map(int, input().split())
        l, r = max(0, s-x), max(0, t-x)
        key.append((l, -1, x))
        key.append((r, 1, x))

    key.sort()
    judge = []
    already = dict()
    search = []
    
    for i in range(n*2):
        s, j, x = key[i]
        
        if j == -1:
            heappush(judge, x)
        else:
            if x in already:
                already[x] += 1
            else:
                already[x] = 1
        
        if i == n*2-1 or key[i][0] != key[i+1][0]:
            while judge:
                if judge[0] in already and already[judge[0]] > 0:
                    already[judge[0]] -= 1
                    heappop(judge)
                else:
                    break
            if judge:
                search.append((s, judge[0]))
            else:
                search.append((s, -1))

    size = len(search)
    index = 0
    answer = []
    for i in range(q):
        d = int(input())
        while index < size-1:
            if search[index+1][0] <= d:
                index += 1
            else:
                break
        print(search[index][1])

    
if __name__ == "__main__":
    main()

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

def main():
    n, q = map(int, input().split())
    
    key = []
    for i in range(n):
        s, t, x = map(int, input().split())
        l, r = max(0, s-x), max(0, t-x)
        key.append((l, 1, x))
        key.append((r, -1, x))
    
    for i in range(q):
        d = int(input())
        key.append((d, 2))

    key.sort()
    judge = []
    already = dict()
    
    for i in range(2*n+q):
        k = key[i]
        if k[1] == -1:
            if k[2] in already:
                already[k[2]] += 1
            else:
                already[k[2]] = 1
        elif k[1] == 1:
            heappush(judge, k[2])
        else:
            while judge:
                if judge[0] in already and already[judge[0]] > 0:
                    already[judge[0]] -= 1
                    heappop(judge)
                else:
                    break
            if judge:
                print(judge[0])
            else:
                print(-1)
    

    
if __name__ == "__main__":
    main()

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

def main():
    n, q = map(int, input().split())
    
    key = []
    for i in range(n):
        s, t, x = map(int, input().split())
        l, r = max(0, s-x), max(0, t-x)
        key.append((l, 1, x))
        key.append((r, -1, x))
    
    for i in range(q):
        d = int(input())
        key.append((d, 2))

    key.sort()
    judge = []
    already = dict()
    
    for i in range(2*n+q):
        k = key[i]
        if k[1] == -1:
            if k[2] in already:
                already[k[2]] += 1
            else:
                already[k[2]] = 1
        elif k[1] == 1:
            heappush(judge, k[2])
        else:
            while judge:
                if judge[0] in already and already[judge[0]] > 0:
                    already[judge[0]] -= 1
                    heappop(judge)
                else:
                    break
            if judge:
                print(judge[0])
            else:
                print(-1)
    

    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
INF = 1 << 30


class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.lst = None
        self.rst = None
        self.bias = 0


class AVLTree:
    def __init__(self):
        self.root = None

    def rotate_left(self, v):
        u = v.rst
        v.rst = u.lst
        u.lst = v
        if u.bias == -1:
            u.bias = v.bias = 0
        else:
            u.bias = 1
            v.bias = -1
        return u

    def rotate_right(self, v):
        u = v.lst
        v.lst = u.rst
        u.rst = v
        if u.bias == 1:
            u.bias = v.bias = 0
        else:
            u.bias = -1
            v.bias = 1
        return u

    def rotateLR(self, v):
        u = v.lst
        t = u.rst
        u.rst = t.lst
        t.lst = u
        v.lst = t.rst
        t.rst = v
        self.update_bias_double(t)
        return t

    def rotateRL(self, v):
        u = v.rst
        t = u.lst
        u.lst = t.rst
        t.rst = u
        v.rst = t.lst
        t.lst = v
        self.update_bias_double(t)
        return t

    def update_bias_double(self, v):
        if v.bias == 1:
            v.rst.bias = -1
            v.lst.bias = 0
        elif v.bias == -1:
            v.rst.bias = 0
            v.lst.bias = 1
        else:
            v.rst.bias = 0
            v.lst.bias = 0
        v.bias = 0

    def insert(self, key, val):
        if self.root is None:
            self.root = Node(key, val)
            return

        v = self.root
        history = []
        while v is not None:
            if key < v.key:
                history.append((v, 1))
                v = v.lst
            elif v.key < key:
                history.append((v, -1))
                v = v.rst
            elif v.key == key:
                v.val = val
                return

        p, pdir = history[-1]
        if pdir == 1:
            p.lst = Node(key, val)
        else:
            p.rst = Node(key, val)

        while history:
            v, direction = history.pop()
            v.bias += direction

            new_v = None
            b = v.bias
            if b == 0:
                break

            if b == 2:
                u = v.lst
                if u.bias == -1:
                    new_v = self.rotateLR(v)
                else:
                    new_v = self.rotate_right(v)
                break
            if b == -2:
                u = v.rst
                if u.bias == 1:
                    new_v = self.rotateRL(v)
                else:
                    new_v = self.rotate_left(v)
                break

        if new_v is not None:
            if len(history) == 0:
                self.root = new_v
                return
            p, pdir = history.pop()
            if pdir == 1:
                p.lst = new_v
            else:
                p.rst = new_v

    def delete(self, key):
        v = self.root
        history = []
        while v is not None:
            if key < v.key:
                history.append((v, 1))
                v = v.lst
            elif v.key < key:
                history.append((v, -1))
                v = v.rst
            else:
                break
        else:
            return False

        if v.lst is not None:
            history.append((v, 1))
            lmax = v.lst
            while lmax.rst is not None:
                history.append((lmax, -1))
                lmax = lmax.rst

            v.key = lmax.key
            v.val = lmax.val

            v = lmax

        c = v.rst if v.lst is None else v.lst

        if history:
            p, pdir = history[-1]
            if pdir == 1:
                p.lst = c
            else:
                p.rst = c

        else:
            self.root = c
            return True

        while history:
            new_p = None

            p, pdir = history.pop()
            p.bias -= pdir

            b = p.bias
            if b == 2:
                if p.lst.bias == -1:
                    new_p = self.rotateLR(p)
                else:
                    new_p = self.rotate_right(p)

            elif b == -2:
                if p.rst.bias == 1:
                    new_p = self.rotateRL(p)
                else:
                    new_p = self.rotate_left(p)

            elif b != 0:
                break

            if new_p is not None:
                if len(history) == 0:
                    self.root = new_p
                    return True
                gp, gpdir = history[-1]
                if gpdir == 1:
                    gp.lst = new_p
                else:
                    gp.rst = new_p
                if new_p.bias != 0:
                    break
        return True

    def get(self, key):
        v = self.root
        while v is not None:
            if key < v.key:
                v = v.lst
            elif v.key < key:
                v = v.rst
            else:
                return v.val
        return None

    def lower_bound(self, key):
        ret = float('inf')
        v = self.root
        while v is not None:
            if v.key >= key:
                if ret > v.key:
                    ret = v.key
                v = v.lst
            else:
                v = v.rst
        return ret

    def __contains__(self, key): return self.member(key)
    def __getitem__(self, key): return self.get(key)
    def __setitem__(self, key, val): return self.insert(key, val)
    def __delitem__(self, key): return self.delete(key)
    def __bool__(self): return self.root is not None


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

event.sort(reverse=True)

avl = AVLTree()
ans = []
for d in map(int, read().split()):
    while event and event[-1][0] <= d:
        time, k, x = event.pop()
        if k == 1:
            avl[x] = 1
        else:
            del avl[x]
    x = avl.lower_bound(-INF)
    ans.append(x if x < INF else -1)

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

Solution (Python):
import sys
INF = 1 << 30


class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.lst = None
        self.rst = None
        self.bias = 0


class AVLTree:
    def __init__(self):
        self.root = None

    def rotate_left(self, v):
        u = v.rst
        v.rst = u.lst
        u.lst = v
        if u.bias == -1:
            u.bias = v.bias = 0
        else:
            u.bias = 1
            v.bias = -1
        return u

    def rotate_right(self, v):
        u = v.lst
        v.lst = u.rst
        u.rst = v
        if u.bias == 1:
            u.bias = v.bias = 0
        else:
            u.bias = -1
            v.bias = 1
        return u

    def rotateLR(self, v):
        u = v.lst
        t = u.rst
        u.rst = t.lst
        t.lst = u
        v.lst = t.rst
        t.rst = v
        self.update_bias_double(t)
        return t

    def rotateRL(self, v):
        u = v.rst
        t = u.lst
        u.lst = t.rst
        t.rst = u
        v.rst = t.lst
        t.lst = v
        self.update_bias_double(t)
        return t

    def update_bias_double(self, v):
        if v.bias == 1:
            v.rst.bias = -1
            v.lst.bias = 0
        elif v.bias == -1:
            v.rst.bias = 0
            v.lst.bias = 1
        else:
            v.rst.bias = 0
            v.lst.bias = 0
        v.bias = 0

    def insert(self, key, val):
        if self.root is None:
            self.root = Node(key, val)
            return

        v = self.root
        history = []
        while v is not None:
            if key < v.key:
                history.append((v, 1))
                v = v.lst
            elif v.key < key:
                history.append((v, -1))
                v = v.rst
            elif v.key == key:
                v.val = val
                return

        p, pdir = history[-1]
        if pdir == 1:
            p.lst = Node(key, val)
        else:
            p.rst = Node(key, val)

        while history:
            v, direction = history.pop()
            v.bias += direction

            new_v = None
            b = v.bias
            if b == 0:
                break

            if b == 2:
                u = v.lst
                if u.bias == -1:
                    new_v = self.rotateLR(v)
                else:
                    new_v = self.rotate_right(v)
                break
            if b == -2:
                u = v.rst
                if u.bias == 1:
                    new_v = self.rotateRL(v)
                else:
                    new_v = self.rotate_left(v)
                break

        if new_v is not None:
            if len(history) == 0:
                self.root = new_v
                return
            p, pdir = history.pop()
            if pdir == 1:
                p.lst = new_v
            else:
                p.rst = new_v

    def delete(self, key):
        v = self.root
        history = []
        while v is not None:
            if key < v.key:
                history.append((v, 1))
                v = v.lst
            elif v.key < key:
                history.append((v, -1))
                v = v.rst
            else:
                break
        else:
            return False

        if v.lst is not None:
            history.append((v, 1))
            lmax = v.lst
            while lmax.rst is not None:
                history.append((lmax, -1))
                lmax = lmax.rst

            v.key = lmax.key
            v.val = lmax.val

            v = lmax

        c = v.rst if v.lst is None else v.lst

        if history:
            p, pdir = history[-1]
            if pdir == 1:
                p.lst = c
            else:
                p.rst = c

        else:
            self.root = c
            return True

        while history:
            new_p = None

            p, pdir = history.pop()
            p.bias -= pdir

            b = p.bias
            if b == 2:
                if p.lst.bias == -1:
                    new_p = self.rotateLR(p)
                else:
                    new_p = self.rotate_right(p)

            elif b == -2:
                if p.rst.bias == 1:
                    new_p = self.rotateRL(p)
                else:
                    new_p = self.rotate_left(p)

            elif b != 0:
                break

            if new_p is not None:
                if len(history) == 0:
                    self.root = new_p
                    return True
                gp, gpdir = history[-1]
                if gpdir == 1:
                    gp.lst = new_p
                else:
                    gp.rst = new_p
                if new_p.bias != 0:
                    break
        return True

    def member(self, key):
        v = self.root
        while v is not None:
            if key < v.key:
                v = v.lst
            elif v.key < key:
                v = v.rst
            else:
                return True
        return False

    def get(self, key):
        v = self.root
        while v is not None:
            if key < v.key:
                v = v.lst
            elif v.key < key:
                v = v.rst
            else:
                return v.val
        return None

    def lower_bound(self, key):
        ret = INF
        v = self.root
        while v is not None:
            if v.key >= key:
                if ret > v.key:
                    ret = v.key
                v = v.lst
            else:
                v = v.rst
        return ret

    def __contains__(self, key): return self.member(key)
    def __getitem__(self, key): return self.get(key)
    def __setitem__(self, key, val): return self.insert(key, val)
    def __delitem__(self, key): return self.delete(key)
    def __bool__(self): return self.root is not None


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

event.sort(reverse=True)

avl = AVLTree()
ans = []
for d in map(int, read().split()):
    while event and event[-1][0] <= d:
        time, k, x = event.pop()
        if k == 1:
            avl[x] = 1
        else:
            del avl[x]
    x = avl.lower_bound(-INF)
    ans.append(x if x < INF else -1)

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

Solution (Python):
import sys


class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.lst = None
        self.rst = None
        self.bias = 0


class AVLTree:
    def __init__(self):
        self.root = None

    def rotate_left(self, v):
        u = v.rst
        v.rst = u.lst
        u.lst = v
        if u.bias == -1:
            u.bias = v.bias = 0
        else:
            u.bias = 1
            v.bias = -1
        return u

    def rotate_right(self, v):
        u = v.lst
        v.lst = u.rst
        u.rst = v
        if u.bias == 1:
            u.bias = v.bias = 0
        else:
            u.bias = -1
            v.bias = 1
        return u

    def rotateLR(self, v):
        u = v.lst
        t = u.rst
        u.rst = t.lst
        t.lst = u
        v.lst = t.rst
        t.rst = v
        self.update_bias_double(t)
        return t

    def rotateRL(self, v):
        u = v.rst
        t = u.lst
        u.lst = t.rst
        t.rst = u
        v.rst = t.lst
        t.lst = v
        self.update_bias_double(t)
        return t

    def update_bias_double(self, v):
        if v.bias == 1:
            v.rst.bias = -1
            v.lst.bias = 0
        elif v.bias == -1:
            v.rst.bias = 0
            v.lst.bias = 1
        else:
            v.rst.bias = 0
            v.lst.bias = 0
        v.bias = 0

    def insert(self, key, val):
        if self.root is None:
            self.root = Node(key, val)
            return

        v = self.root
        history = []
        while v is not None:
            if key < v.key:
                history.append((v, 1))
                v = v.lst
            elif v.key < key:
                history.append((v, -1))
                v = v.rst
            elif v.key == key:
                v.val = val
                return

        p, pdir = history[-1]
        if pdir == 1:
            p.lst = Node(key, val)
        else:
            p.rst = Node(key, val)

        while history:
            v, direction = history.pop()
            v.bias += direction

            new_v = None
            b = v.bias
            if b == 0:
                break

            if b == 2:
                u = v.lst
                if u.bias == -1:
                    new_v = self.rotateLR(v)
                else:
                    new_v = self.rotate_right(v)
                break
            if b == -2:
                u = v.rst
                if u.bias == 1:
                    new_v = self.rotateRL(v)
                else:
                    new_v = self.rotate_left(v)
                break

        if new_v is not None:
            if len(history) == 0:
                self.root = new_v
                return
            p, pdir = history.pop()
            if pdir == 1:
                p.lst = new_v
            else:
                p.rst = new_v

    def delete(self, key):
        v = self.root
        history = []
        while v is not None:
            if key < v.key:
                history.append((v, 1))
                v = v.lst
            elif v.key < key:
                history.append((v, -1))
                v = v.rst
            else:
                break
        else:
            return False

        if v.lst is not None:
            history.append((v, 1))
            lmax = v.lst
            while lmax.rst is not None:
                history.append((lmax, -1))
                lmax = lmax.rst

            v.key = lmax.key
            v.val = lmax.val

            v = lmax

        c = v.rst if v.lst is None else v.lst

        if history:
            p, pdir = history[-1]
            if pdir == 1:
                p.lst = c
            else:
                p.rst = c

        else:
            self.root = c
            return True

        while history:
            new_p = None

            p, pdir = history.pop()
            p.bias -= pdir

            b = p.bias
            if b == 2:
                if p.lst.bias == -1:
                    new_p = self.rotateLR(p)
                else:
                    new_p = self.rotate_right(p)

            elif b == -2:
                if p.rst.bias == 1:
                    new_p = self.rotateRL(p)
                else:
                    new_p = self.rotate_left(p)

            elif b != 0:
                break

            if new_p is not None:
                if len(history) == 0:
                    self.root = new_p
                    return True
                gp, gpdir = history[-1]
                if gpdir == 1:
                    gp.lst = new_p
                else:
                    gp.rst = new_p
                if new_p.bias != 0:
                    break
        return True

    def member(self, key):
        v = self.root
        while v is not None:
            if key < v.key:
                v = v.lst
            elif v.key < key:
                v = v.rst
            else:
                return True
        return False

    def get(self, key):
        v = self.root
        while v is not None:
            if key < v.key:
                v = v.lst
            elif v.key < key:
                v = v.rst
            else:
                return v.val
        return None

    def lower_bound(self, key):
        ret = (float('inf'), 0)
        v = self.root
        while v is not None:
            if v.key >= key:
                if ret > v.key:
                    ret = v.key
                v = v.lst
            else:
                v = v.rst
        return ret

    def upper_bound(self, key):
        ret = -float('inf')
        v = self.root
        while v is not None:
            if v.key <= key:
                if ret < v.key:
                    ret = v.key
                v = v.rst
            else:
                v = v.lst
        return ret

    def __contains__(self, key): return self.member(key)
    def __getitem__(self, key): return self.get(key)
    def __setitem__(self, key, val): return self.insert(key, val)
    def __delitem__(self, key): return self.delete(key)
    def __bool__(self): return self.root is not None

    def __str__(self):
        return self.tostr_rec("", "", self.root)

    def tostr_rec(self, head, bar, t):
        graph = ""

        if t != None:
            graph += self.tostr_rec(head + "    ", "／", t.rst)
            node = str(t.key) + ":" + str(t.bias)
            graph += head + bar + node + "\n"
            graph += self.tostr_rec(head + "    ", "＼", t.lst)

        return graph


read = sys.stdin.buffer.read
readlines = sys.stdin.buffer.readlines
input = sys.stdin.buffer.readline
N, Q = map(int, input().split())
S = []
T = []
for i in range(N):
    s, t, x = map(int, input().split())
    S.append((s-x, s, x))
    T.append((t-x, s, x))

S.sort(reverse=True)
T.sort(reverse=True)

INF = 10**10
avl = AVLTree()
ans = []
for d in map(int, read().split()):
    while S and S[-1][0] <= d:
        sx, s, x = S.pop()
        avl[(x, sx+x)] = x

    while T and T[-1][0] <= d:
        tx, s, x = T.pop()

        del avl[(x, s)]
    x, s = avl.lower_bound((-INF, 0))
    ans.append(x if x < INF else -1)

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

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,q = map(int,ipt().split())
    base = 10**9+1
    hq = []
    for i in range(n):
        s,t,x = map(int,ipt().split())
        if t < x:
            continue
        hpq.heappush(hq,max(0,(s-x))*2*base+x*2+1)
        hpq.heappush(hq,(t-x)*2*base+x*2)


    iv = []
    dd = dict()
    for i in range(q):
        f = True
        d = (int(ipt())+1)*2*base
        while hq and hq[0] < d:
            hi = hpq.heappop(hq)
            t = hi//(2*base)
            p = hi%2
            x = (hi//2)%base
            if p:
                dd[x] = True
                hpq.heappush(iv,x)
            else:
                dd[x] = False
        while iv:
            ii = iv[0]
            if dd[ii]:
                print(ii)
                f = False
                break
            else:
                hpq.heappop(iv)
        if f:
            print(-1)

    return None

if __name__ == '__main__':
    main()