Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
sys.stdin.readline
n,p=map(int,input().split())

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
e.sort()
q = deque()
for _ in range(p):
    q.append(int(input()))
s = set()
removed = set()
s_min = None

for t,f,x in e:
    while t > q[0]:
        q.popleft()
        if s:
            if s_min is None:
              s_min = min(s)
            print(s_min)
        else:
            print(-1)
        if not q:
            sys.exit()
    if f == 1:
        s.add(x)
        if s_min is not None and s_min > x:
          s_min = x
    else:
        s.remove(x)
        if x == s_min:
          s_min = None

        
while q:
    q.pop()
    print(-1)


Fixed submission:
import random
from collections import deque
import sys
sys.stdin.readline

class AvlTree:  # std::set
    def __init__(self, values=None, sorted_=False, n=0):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # n: add メソッドを使う回数の最大値

        # sorted_==True であれば、初期値の数の線形時間で木を構築する
        # 値を追加するときは必ず n を設定する
        if values is None:
            self.left = [-1] * (n + 1)
            self.right = [-1] * (n + 1)
            self.values = [-float("inf")]
            self.diff = [0] * (n + 1)  # left - right
            self.size_l = [0] * (n + 1)
            self.idx_new_val = 0
        else:
            if not sorted_:
                values.sort()
            len_ = self.idx_new_val = len(values)
            n += len_
            self_left = self.left = [-1] * (n + 1)
            self_right = self.right = [-1] * (n + 1)
            self_values = self.values = [-float("inf")] + values
            self_diff = self.diff = [0] * (n + 1)  # left - right
            self_size_l = self.size_l = [0] * (n + 1)

            st = [[1, len_ + 1, 0]]
            while len(st) > 0:  # dfs っぽく木を構築
                l, r, idx_par = st.pop()  # 半開区間
                c = (l + r) >> 1  # python -> //2  pypy -> >>1
                if self_values[c] < self_values[idx_par]:
                    self_left[idx_par] = c
                else:
                    self_right[idx_par] = c
                siz = r - l
                if siz & -siz == siz != 1:  # 2 冪だったら
                    self_diff[c] = 1
                self_size_l[c] = siz_l = c - l
                if siz_l > 0:
                    st.append([l, c, c])
                    c1 = c + 1
                    if c1 < r:  # 左にノードがなければ右には必ず無いので
                        st.append([c1, r, c])

    def rotate_right(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == 2
        idx_l = self_left[idx]
        diff_l = self_diff[idx_l]

        if diff_l == -1:  # 複回転
            idx_lr = self_right[idx_l]
            diff_lr = self_diff[idx_lr]
            if diff_lr == 0:
                self_diff[idx] = 0
                self_diff[idx_l] = 0
            elif diff_lr == 1:
                self_diff[idx] = -1
                self_diff[idx_l] = 0
                self_diff[idx_lr] = 0
            else:  # diff_lr == -1
                self_diff[idx] = 0
                self_diff[idx_l] = 1
                self_diff[idx_lr] = 0

            # 部分木の大きさの計算
            self_size_l[idx_lr] += self_size_l[idx_l] + 1
            self_size_l[idx] -= self_size_l[idx_lr] + 1

            # 回転
            self_right[idx_l] = self_left[idx_lr]
            self_left[idx] = self_right[idx_lr]
            self_left[idx_lr] = idx_l
            self_right[idx_lr] = idx
            lr_container[idx_par] = idx_lr

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = 1
                nb = self_diff[idx_l] = -1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_l] = 0

            # 部分木の大きさの計算
            self_size_l[idx] -= self_size_l[idx_l] + 1

            # 回転
            self_left[idx] = self_right[idx_l]
            self_right[idx_l] = idx
            lr_container[idx_par] = idx_l

            return nb  # 新しい根の diff を返す

    def rotate_left(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == -2
        idx_r = self_right[idx]
        diff_l = self_diff[idx_r]

        if diff_l == 1:  # 複回転
            idx_rl = self_left[idx_r]
            diff_rl = self_diff[idx_rl]
            if diff_rl == 0:
                self_diff[idx] = 0
                self_diff[idx_r] = 0
            elif diff_rl == -1:
                self_diff[idx] = 1
                self_diff[idx_r] = 0
                self_diff[idx_rl] = 0
            else:  # diff_lr == 1
                self_diff[idx] = 0
                self_diff[idx_r] = -1
                self_diff[idx_rl] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] -= self_size_l[idx_rl] + 1
            self_size_l[idx_rl] += self_size_l[idx] + 1

            # 回転
            self_left[idx_r] = self_right[idx_rl]
            self_right[idx] = self_left[idx_rl]
            self_right[idx_rl] = idx_r
            self_left[idx_rl] = idx
            lr_container[idx_par] = idx_rl

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = -1
                nb = self_diff[idx_r] = 1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_r] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] += self_size_l[idx] + 1

            # 回転
            self_right[idx] = self_left[idx_r]
            self_left[idx_r] = idx
            lr_container[idx_par] = idx_r

            return nb  # 新しい根の diff を返す

    def add(self, x):  # insert
        # x を加える
        # x が既に入ってる場合は False を、
        # そうでなければ True を返す

        idx = 0
        path = []
        path_left = []

        self_values = self.values
        self_left = self.left
        self_right = self.right

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if x < value:
                path_left.append(idx)  # 重複を許さないので処理を後にする必要がある
                idx = self_left[idx]
            elif value < x:
                idx = self_right[idx]
            else:  # x == value
                return False  # 重複を許さない

        self.idx_new_val += 1
        self_diff = self.diff
        self_size_l = self.size_l

        idx = path[-1]
        if x < value:
            self_left[idx] = self.idx_new_val
        else:
            self_right[idx] = self.idx_new_val

        self_values.append(x)

        for idx_ in path_left:
            self_size_l[idx_] += 1

        self_diff[idx] += 1 if x < value else -1
        for idx_par in path[-2::-1]:
            diff = self_diff[idx]
            if diff == 0:
                return True
            elif diff == 2:  # 右回転
                self.rotate_right(idx_par, self_right[idx_par] == idx)
                return True
            elif diff == -2:  # 左回転
                self.rotate_left(idx_par, self_right[idx_par] == idx)
                return True
            else:
                self_diff[idx_par] += 1 if self_left[idx_par] == idx else -1
            idx = idx_par
        return True

    def remove(self, x):  # erase
        # x を削除する
        # x の存在が保証されている必要がある

        idx = 0
        path = []
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if value < x:
                idx = self_right[idx]
            elif x < value:
                self_size_l[idx] -= 1  # 値の存在を保証しているので
                idx = self_left[idx]
            else:  # x == value
                idx_x = idx
                self_size_l[idx] -= 1
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return True
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return True
            else:
                return True
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return True

    def pop(self, idx_):
        # 小さい方から idx_ 番目の要素を削除してその要素を返す（0-indexed）
        # idx_ 番目の値の存在が保証されている必要がある

        path = [0]
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            path.append(idx)
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                self_size_l[idx] -= 1  # 値の存在が保証されているので
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:
                idx_x = idx
                x = self_values[idx]
                self_size_l[idx] -= 1  # なんで？
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return x
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return x
            else:
                return x
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return x

    def __getitem__(self, idx_):
        # 小さい方から idx_ 番目の要素を返す

        self_left = self.left
        self_right = self.right
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:  # c == idx_
                return self.values[idx]
        raise IndexError

    def __contains__(self, x):  # count
        # 値 x があるか

        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:
                return True  # res + self_size_l[idx]
        return False

    def bisect_left(self, x):  # lower_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x
                return res + self_size_l[idx]
        return res

    def bisect_right(self, x):  # upper_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x:
                return res + self_size_l[idx] + 1
        return res

    def print_tree(self, idx=0, depth=0, from_="・"):
        if idx == 0:
            idx = self.right[idx]
        if idx == -1:
            return
        self.print_tree(self.left[idx], depth + 1, "┏")
        print("\t\t" * depth + from_ + " val=[" + str(self.values[idx]) +
              "] diff=[" + str(self.diff[idx]) +
              "] size_l=[" + str(self.size_l[idx]) + "]")
        self.print_tree(self.right[idx], depth + 1, "┗")

    
def main():
  n,p=map(int,sys.stdin.buffer.readline().split())

  e=[]
  for _ in range(n):
      s,t,x = map(int,sys.stdin.buffer.readline().split())
      e.append((s-x,1,x))
      e.append((t-x,-1,x))
  e.sort()
  q = deque()
  for _ in range(p):
      q.append(int(input()))
  s=AvlTree(n=len(e))

  for t,f,x in e:
      while t > q[0]:
          q.popleft()
          try:
              print(s[0])
          except IndexError:
              print(-1)
          if not q:
              sys.exit()
      if f == 1:
          s.add(x)
      else:
          s.remove(x)

  while q:
      q.pop()
      print(-1)

main()

Buggy python submission (verdict: Time Limit Exceeded):
import random
from collections import deque
import sys
sys.stdin.readline

import random
class Treap:
    def __init__(self):
        self.node = None  # root

    def __str__(self):
        L = []
        def recursiveSearch(node):
            if node.left is not None:
                recursiveSearch(node.left)
            L.append((node.val, node.priority))
            if node.right is not None:
                recursiveSearch(node.right)
        recursiveSearch(self.node)
        return str(L)

    def add(self, x):
        i = self.bisect(x)
        self.node = self.insert(self.node, i, x)

    def remove(self, x):
        i = self.bisect(x)
        self.node = self.erase(self.node, i)

    def bisect(self, x):  # bisect_left
        def recursiveSearch(node):
            if node is None:
                return 0
            res = 0
            if x <= node.val:
                if node.left is not None:
                    return recursiveSearch(node.left)
                else:
                    return 0
            else:
                res += self.count(node.left) + 1
                if node.right is not None:
                    return res + recursiveSearch(node.right)
                else:
                    return res
        return recursiveSearch(self.node)

    def min(self):
        t = self.node
        while t.left is not None:
          t = t.left
        return t.val

    class Node:
        def __init__(self, x):
            self.val = x
            self.priority = random.randint(0, 1<<30)
            self.left = None
            self.right = None
            self.cnt = 1
        def __str__(self):
            return str(self.val)

    def count(self, t: Node):
        return 0 if t is None else t.cnt

    def update(self, t: Node):
        t.cnt = self.count(t.left) + self.count(t.right) + 1
        return t

    def merge(self, l: Node, r: Node):
        if l is None: return r
        if r is None: return l
        if l.priority > r.priority:
            l.right = self.merge(l.right, r)
            return self.update(l)
        else:
            r.left = self.merge(l, r.left)
            return self.update(r)

    def split(self, t: Node, k: int) -> (Node, Node):  # [0,k),[k,n)
        if t is None: return None, None
        if k <= self.count(t.left):
            s = self.split(t.left, k)
            t.left = s[1]
            return s[0], self.update(t)
        else:
            s = self.split(t.right, k - self.count(t.left) - 1)
            t.right = s[0]
            return self.update(t), s[1]

    def insert(self, t: Node, k: int, x):
        l, r = self.split(t, k)
        return self.merge(self.merge(l, self.Node(x)), r)

    def erase(self, t: Node, k):
        l, r = self.split(t, k)
        _, r = self.split(r, 1)
        return self.merge(l, r)

    
def main():
  n,p=map(int,sys.stdin.buffer.readline().split())

  e=[]
  for _ in range(n):
      s,t,x = map(int,sys.stdin.buffer.readline().split())
      e.append((s-x,1,x))
      e.append((t-x,-1,x))
  e.sort()
  q = deque()
  for _ in range(p):
      q.append(int(input()))
  s=Treap()

  for t,f,x in e:
      while t > q[0]:
          q.popleft()
          if s.node:
              print(s.min())
          else:
              print(-1)
          if not q:
              sys.exit()
      if f == 1:
          s.add(x)
      else:
          s.remove(x)

  while q:
      q.pop()
      print(-1)

main()


Fixed submission:
import random
from collections import deque
import sys
sys.stdin.readline

class AvlTree:  # std::set
    def __init__(self, values=None, sorted_=False, n=0):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # n: add メソッドを使う回数の最大値

        # sorted_==True であれば、初期値の数の線形時間で木を構築する
        # 値を追加するときは必ず n を設定する
        if values is None:
            self.left = [-1] * (n + 1)
            self.right = [-1] * (n + 1)
            self.values = [-float("inf")]
            self.diff = [0] * (n + 1)  # left - right
            self.size_l = [0] * (n + 1)
            self.idx_new_val = 0
        else:
            if not sorted_:
                values.sort()
            len_ = self.idx_new_val = len(values)
            n += len_
            self_left = self.left = [-1] * (n + 1)
            self_right = self.right = [-1] * (n + 1)
            self_values = self.values = [-float("inf")] + values
            self_diff = self.diff = [0] * (n + 1)  # left - right
            self_size_l = self.size_l = [0] * (n + 1)

            st = [[1, len_ + 1, 0]]
            while len(st) > 0:  # dfs っぽく木を構築
                l, r, idx_par = st.pop()  # 半開区間
                c = (l + r) >> 1  # python -> //2  pypy -> >>1
                if self_values[c] < self_values[idx_par]:
                    self_left[idx_par] = c
                else:
                    self_right[idx_par] = c
                siz = r - l
                if siz & -siz == siz != 1:  # 2 冪だったら
                    self_diff[c] = 1
                self_size_l[c] = siz_l = c - l
                if siz_l > 0:
                    st.append([l, c, c])
                    c1 = c + 1
                    if c1 < r:  # 左にノードがなければ右には必ず無いので
                        st.append([c1, r, c])

    def rotate_right(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == 2
        idx_l = self_left[idx]
        diff_l = self_diff[idx_l]

        if diff_l == -1:  # 複回転
            idx_lr = self_right[idx_l]
            diff_lr = self_diff[idx_lr]
            if diff_lr == 0:
                self_diff[idx] = 0
                self_diff[idx_l] = 0
            elif diff_lr == 1:
                self_diff[idx] = -1
                self_diff[idx_l] = 0
                self_diff[idx_lr] = 0
            else:  # diff_lr == -1
                self_diff[idx] = 0
                self_diff[idx_l] = 1
                self_diff[idx_lr] = 0

            # 部分木の大きさの計算
            self_size_l[idx_lr] += self_size_l[idx_l] + 1
            self_size_l[idx] -= self_size_l[idx_lr] + 1

            # 回転
            self_right[idx_l] = self_left[idx_lr]
            self_left[idx] = self_right[idx_lr]
            self_left[idx_lr] = idx_l
            self_right[idx_lr] = idx
            lr_container[idx_par] = idx_lr

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = 1
                nb = self_diff[idx_l] = -1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_l] = 0

            # 部分木の大きさの計算
            self_size_l[idx] -= self_size_l[idx_l] + 1

            # 回転
            self_left[idx] = self_right[idx_l]
            self_right[idx_l] = idx
            lr_container[idx_par] = idx_l

            return nb  # 新しい根の diff を返す

    def rotate_left(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == -2
        idx_r = self_right[idx]
        diff_l = self_diff[idx_r]

        if diff_l == 1:  # 複回転
            idx_rl = self_left[idx_r]
            diff_rl = self_diff[idx_rl]
            if diff_rl == 0:
                self_diff[idx] = 0
                self_diff[idx_r] = 0
            elif diff_rl == -1:
                self_diff[idx] = 1
                self_diff[idx_r] = 0
                self_diff[idx_rl] = 0
            else:  # diff_lr == 1
                self_diff[idx] = 0
                self_diff[idx_r] = -1
                self_diff[idx_rl] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] -= self_size_l[idx_rl] + 1
            self_size_l[idx_rl] += self_size_l[idx] + 1

            # 回転
            self_left[idx_r] = self_right[idx_rl]
            self_right[idx] = self_left[idx_rl]
            self_right[idx_rl] = idx_r
            self_left[idx_rl] = idx
            lr_container[idx_par] = idx_rl

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = -1
                nb = self_diff[idx_r] = 1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_r] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] += self_size_l[idx] + 1

            # 回転
            self_right[idx] = self_left[idx_r]
            self_left[idx_r] = idx
            lr_container[idx_par] = idx_r

            return nb  # 新しい根の diff を返す

    def add(self, x):  # insert
        # x を加える
        # x が既に入ってる場合は False を、
        # そうでなければ True を返す

        idx = 0
        path = []
        path_left = []

        self_values = self.values
        self_left = self.left
        self_right = self.right

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if x < value:
                path_left.append(idx)  # 重複を許さないので処理を後にする必要がある
                idx = self_left[idx]
            elif value < x:
                idx = self_right[idx]
            else:  # x == value
                return False  # 重複を許さない

        self.idx_new_val += 1
        self_diff = self.diff
        self_size_l = self.size_l

        idx = path[-1]
        if x < value:
            self_left[idx] = self.idx_new_val
        else:
            self_right[idx] = self.idx_new_val

        self_values.append(x)

        for idx_ in path_left:
            self_size_l[idx_] += 1

        self_diff[idx] += 1 if x < value else -1
        for idx_par in path[-2::-1]:
            diff = self_diff[idx]
            if diff == 0:
                return True
            elif diff == 2:  # 右回転
                self.rotate_right(idx_par, self_right[idx_par] == idx)
                return True
            elif diff == -2:  # 左回転
                self.rotate_left(idx_par, self_right[idx_par] == idx)
                return True
            else:
                self_diff[idx_par] += 1 if self_left[idx_par] == idx else -1
            idx = idx_par
        return True

    def remove(self, x):  # erase
        # x を削除する
        # x の存在が保証されている必要がある

        idx = 0
        path = []
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if value < x:
                idx = self_right[idx]
            elif x < value:
                self_size_l[idx] -= 1  # 値の存在を保証しているので
                idx = self_left[idx]
            else:  # x == value
                idx_x = idx
                self_size_l[idx] -= 1
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return True
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return True
            else:
                return True
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return True

    def pop(self, idx_):
        # 小さい方から idx_ 番目の要素を削除してその要素を返す（0-indexed）
        # idx_ 番目の値の存在が保証されている必要がある

        path = [0]
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            path.append(idx)
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                self_size_l[idx] -= 1  # 値の存在が保証されているので
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:
                idx_x = idx
                x = self_values[idx]
                self_size_l[idx] -= 1  # なんで？
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return x
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return x
            else:
                return x
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return x

    def __getitem__(self, idx_):
        # 小さい方から idx_ 番目の要素を返す

        self_left = self.left
        self_right = self.right
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:  # c == idx_
                return self.values[idx]
        raise IndexError

    def __contains__(self, x):  # count
        # 値 x があるか

        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:
                return True  # res + self_size_l[idx]
        return False

    def bisect_left(self, x):  # lower_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x
                return res + self_size_l[idx]
        return res

    def bisect_right(self, x):  # upper_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x:
                return res + self_size_l[idx] + 1
        return res

    def print_tree(self, idx=0, depth=0, from_="・"):
        if idx == 0:
            idx = self.right[idx]
        if idx == -1:
            return
        self.print_tree(self.left[idx], depth + 1, "┏")
        print("\t\t" * depth + from_ + " val=[" + str(self.values[idx]) +
              "] diff=[" + str(self.diff[idx]) +
              "] size_l=[" + str(self.size_l[idx]) + "]")
        self.print_tree(self.right[idx], depth + 1, "┗")

    
def main():
  n,p=map(int,sys.stdin.buffer.readline().split())

  e=[]
  for _ in range(n):
      s,t,x = map(int,sys.stdin.buffer.readline().split())
      e.append((s-x,1,x))
      e.append((t-x,-1,x))
  e.sort()
  q = deque()
  for _ in range(p):
      q.append(int(input()))
  s=AvlTree(n=len(e))

  for t,f,x in e:
      while t > q[0]:
          q.popleft()
          try:
              print(s[0])
          except IndexError:
              print(-1)
          if not q:
              sys.exit()
      if f == 1:
          s.add(x)
      else:
          s.remove(x)

  while q:
      q.pop()
      print(-1)

main()

Buggy python submission (verdict: Runtime Error):
import random
from collections import deque
import sys
sys.stdin.readline

import random
class Treap:
    def __init__(self):
        self.node = None  # root

    def __str__(self):
        L = []
        def recursiveSearch(node):
            if node.left is not None:
                recursiveSearch(node.left)
            L.append((node.val, node.priority))
            if node.right is not None:
                recursiveSearch(node.right)
        recursiveSearch(self.node)
        return str(L)

    def add(self, x):
        i = self.bisect(x)
        self.node = self.insert(self.node, i, x)

    def remove(self, x):
        i = self.bisect(x)
        self.node = self.erase(self.node, i)

    def bisect(self, x):  # bisect_left
        def recursiveSearch(node):
            if node is None:
                return 0
            res = 0
            if x <= node.val:
                if node.left is not None:
                    return recursiveSearch(node.left)
                else:
                    return 0
            else:
                res += self.count(node.left) + 1
                if node.right is not None:
                    return res + recursiveSearch(node.right)
                else:
                    return res
        return recursiveSearch(self.node)

    def min(self):
        t = self.node
        while t.left is not None:
          t = t.left
        return t.val

    class Node:
        def __init__(self, x):
            self.val = x
            self.priority = random.randint(0, 1<<30)
            self.left = None
            self.right = None
            self.cnt = 1
        def __str__(self):
            return str(self.val)

    def count(self, t: Node):
        return 0 if t is None else t.cnt

    def update(self, t: Node):
        t.cnt = self.count(t.left) + self.count(t.right) + 1
        return t

    def merge(self, l: Node, r: Node):
        if l is None: return r
        if r is None: return l
        if l.priority > r.priority:
            l.right = self.merge(l.right, r)
            return self.update(l)
        else:
            r.left = self.merge(l, r.left)
            return self.update(r)

    def split(self, t: Node, k: int) -> (Node, Node):  # [0,k),[k,n)
        if t is None: return None, None
        if k <= self.count(t.left):
            s = self.split(t.left, k)
            t.left = s[1]
            return s[0], self.update(t)
        else:
            s = self.split(t.right, k - self.count(t.left) - 1)
            t.right = s[0]
            return self.update(t), s[1]

    def insert(self, t: Node, k: int, x):
        l, r = self.split(t, k)
        return self.merge(self.merge(l, self.Node(x)), r)

    def erase(self, t: Node, k):
        l, r = self.split(t, k)
        _, r = self.split(r, 1)
        return self.merge(l, r)

    
def main():
  n,p=map(int,sys.stdin.buffer.readline().split())

  e=[]
  for _ in range(n):
      s,t,x = map(int,sys.stdin.buffer.readline().split())
      e.append((s-x,1,x))
      e.append((t-x,-1,x))
  e.sort()
  q = deque()
  for _ in range(p):
      q.append(int(input()))
  s=Treap()

  for t,f,x in e:
      while t > q[0]:
          q.popleft()
          if s.node:
              print(s[0])
          else:
              print(-1)
          if not q:
              sys.exit()
      if f == 1:
          s.add(x)
      else:
          s.remove(x)

  while q:
      q.pop()
      print(-1)

main()


Fixed submission:
import random
from collections import deque
import sys
sys.stdin.readline

class AvlTree:  # std::set
    def __init__(self, values=None, sorted_=False, n=0):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # n: add メソッドを使う回数の最大値

        # sorted_==True であれば、初期値の数の線形時間で木を構築する
        # 値を追加するときは必ず n を設定する
        if values is None:
            self.left = [-1] * (n + 1)
            self.right = [-1] * (n + 1)
            self.values = [-float("inf")]
            self.diff = [0] * (n + 1)  # left - right
            self.size_l = [0] * (n + 1)
            self.idx_new_val = 0
        else:
            if not sorted_:
                values.sort()
            len_ = self.idx_new_val = len(values)
            n += len_
            self_left = self.left = [-1] * (n + 1)
            self_right = self.right = [-1] * (n + 1)
            self_values = self.values = [-float("inf")] + values
            self_diff = self.diff = [0] * (n + 1)  # left - right
            self_size_l = self.size_l = [0] * (n + 1)

            st = [[1, len_ + 1, 0]]
            while len(st) > 0:  # dfs っぽく木を構築
                l, r, idx_par = st.pop()  # 半開区間
                c = (l + r) >> 1  # python -> //2  pypy -> >>1
                if self_values[c] < self_values[idx_par]:
                    self_left[idx_par] = c
                else:
                    self_right[idx_par] = c
                siz = r - l
                if siz & -siz == siz != 1:  # 2 冪だったら
                    self_diff[c] = 1
                self_size_l[c] = siz_l = c - l
                if siz_l > 0:
                    st.append([l, c, c])
                    c1 = c + 1
                    if c1 < r:  # 左にノードがなければ右には必ず無いので
                        st.append([c1, r, c])

    def rotate_right(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == 2
        idx_l = self_left[idx]
        diff_l = self_diff[idx_l]

        if diff_l == -1:  # 複回転
            idx_lr = self_right[idx_l]
            diff_lr = self_diff[idx_lr]
            if diff_lr == 0:
                self_diff[idx] = 0
                self_diff[idx_l] = 0
            elif diff_lr == 1:
                self_diff[idx] = -1
                self_diff[idx_l] = 0
                self_diff[idx_lr] = 0
            else:  # diff_lr == -1
                self_diff[idx] = 0
                self_diff[idx_l] = 1
                self_diff[idx_lr] = 0

            # 部分木の大きさの計算
            self_size_l[idx_lr] += self_size_l[idx_l] + 1
            self_size_l[idx] -= self_size_l[idx_lr] + 1

            # 回転
            self_right[idx_l] = self_left[idx_lr]
            self_left[idx] = self_right[idx_lr]
            self_left[idx_lr] = idx_l
            self_right[idx_lr] = idx
            lr_container[idx_par] = idx_lr

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = 1
                nb = self_diff[idx_l] = -1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_l] = 0

            # 部分木の大きさの計算
            self_size_l[idx] -= self_size_l[idx_l] + 1

            # 回転
            self_left[idx] = self_right[idx_l]
            self_right[idx_l] = idx
            lr_container[idx_par] = idx_l

            return nb  # 新しい根の diff を返す

    def rotate_left(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == -2
        idx_r = self_right[idx]
        diff_l = self_diff[idx_r]

        if diff_l == 1:  # 複回転
            idx_rl = self_left[idx_r]
            diff_rl = self_diff[idx_rl]
            if diff_rl == 0:
                self_diff[idx] = 0
                self_diff[idx_r] = 0
            elif diff_rl == -1:
                self_diff[idx] = 1
                self_diff[idx_r] = 0
                self_diff[idx_rl] = 0
            else:  # diff_lr == 1
                self_diff[idx] = 0
                self_diff[idx_r] = -1
                self_diff[idx_rl] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] -= self_size_l[idx_rl] + 1
            self_size_l[idx_rl] += self_size_l[idx] + 1

            # 回転
            self_left[idx_r] = self_right[idx_rl]
            self_right[idx] = self_left[idx_rl]
            self_right[idx_rl] = idx_r
            self_left[idx_rl] = idx
            lr_container[idx_par] = idx_rl

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = -1
                nb = self_diff[idx_r] = 1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_r] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] += self_size_l[idx] + 1

            # 回転
            self_right[idx] = self_left[idx_r]
            self_left[idx_r] = idx
            lr_container[idx_par] = idx_r

            return nb  # 新しい根の diff を返す

    def add(self, x):  # insert
        # x を加える
        # x が既に入ってる場合は False を、
        # そうでなければ True を返す

        idx = 0
        path = []
        path_left = []

        self_values = self.values
        self_left = self.left
        self_right = self.right

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if x < value:
                path_left.append(idx)  # 重複を許さないので処理を後にする必要がある
                idx = self_left[idx]
            elif value < x:
                idx = self_right[idx]
            else:  # x == value
                return False  # 重複を許さない

        self.idx_new_val += 1
        self_diff = self.diff
        self_size_l = self.size_l

        idx = path[-1]
        if x < value:
            self_left[idx] = self.idx_new_val
        else:
            self_right[idx] = self.idx_new_val

        self_values.append(x)

        for idx_ in path_left:
            self_size_l[idx_] += 1

        self_diff[idx] += 1 if x < value else -1
        for idx_par in path[-2::-1]:
            diff = self_diff[idx]
            if diff == 0:
                return True
            elif diff == 2:  # 右回転
                self.rotate_right(idx_par, self_right[idx_par] == idx)
                return True
            elif diff == -2:  # 左回転
                self.rotate_left(idx_par, self_right[idx_par] == idx)
                return True
            else:
                self_diff[idx_par] += 1 if self_left[idx_par] == idx else -1
            idx = idx_par
        return True

    def remove(self, x):  # erase
        # x を削除する
        # x の存在が保証されている必要がある

        idx = 0
        path = []
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if value < x:
                idx = self_right[idx]
            elif x < value:
                self_size_l[idx] -= 1  # 値の存在を保証しているので
                idx = self_left[idx]
            else:  # x == value
                idx_x = idx
                self_size_l[idx] -= 1
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return True
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return True
            else:
                return True
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return True

    def pop(self, idx_):
        # 小さい方から idx_ 番目の要素を削除してその要素を返す（0-indexed）
        # idx_ 番目の値の存在が保証されている必要がある

        path = [0]
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            path.append(idx)
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                self_size_l[idx] -= 1  # 値の存在が保証されているので
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:
                idx_x = idx
                x = self_values[idx]
                self_size_l[idx] -= 1  # なんで？
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return x
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return x
            else:
                return x
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return x

    def __getitem__(self, idx_):
        # 小さい方から idx_ 番目の要素を返す

        self_left = self.left
        self_right = self.right
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:  # c == idx_
                return self.values[idx]
        raise IndexError

    def __contains__(self, x):  # count
        # 値 x があるか

        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:
                return True  # res + self_size_l[idx]
        return False

    def bisect_left(self, x):  # lower_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x
                return res + self_size_l[idx]
        return res

    def bisect_right(self, x):  # upper_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x:
                return res + self_size_l[idx] + 1
        return res

    def print_tree(self, idx=0, depth=0, from_="・"):
        if idx == 0:
            idx = self.right[idx]
        if idx == -1:
            return
        self.print_tree(self.left[idx], depth + 1, "┏")
        print("\t\t" * depth + from_ + " val=[" + str(self.values[idx]) +
              "] diff=[" + str(self.diff[idx]) +
              "] size_l=[" + str(self.size_l[idx]) + "]")
        self.print_tree(self.right[idx], depth + 1, "┗")

    
def main():
  n,p=map(int,sys.stdin.buffer.readline().split())

  e=[]
  for _ in range(n):
      s,t,x = map(int,sys.stdin.buffer.readline().split())
      e.append((s-x,1,x))
      e.append((t-x,-1,x))
  e.sort()
  q = deque()
  for _ in range(p):
      q.append(int(input()))
  s=AvlTree(n=len(e))

  for t,f,x in e:
      while t > q[0]:
          q.popleft()
          try:
              print(s[0])
          except IndexError:
              print(-1)
          if not q:
              sys.exit()
      if f == 1:
          s.add(x)
      else:
          s.remove(x)

  while q:
      q.pop()
      print(-1)

main()

Buggy python submission (verdict: Time Limit Exceeded):
import random
from collections import deque
import sys
sys.stdin.readline

import random
class Treap:
    def __init__(self):
        self.node = None  # root

    def __str__(self):
        L = []
        def recursiveSearch(node):
            if node.left is not None:
                recursiveSearch(node.left)
            L.append((node.val, node.priority))
            if node.right is not None:
                recursiveSearch(node.right)
        recursiveSearch(self.node)
        return str(L)

    def add(self, x):
        i = self.bisect(x)
        self.node = self.insert(self.node, i, x)

    def remove(self, x):
        i = self.bisect(x)
        self.node = self.erase(self.node, i)

    def bisect(self, x):  # bisect_left
        def recursiveSearch(node):
            if node is None:
                return 0
            res = 0
            if x <= node.val:
                if node.left is not None:
                    return recursiveSearch(node.left)
                else:
                    return 0
            else:
                res += self.count(node.left) + 1
                if node.right is not None:
                    return res + recursiveSearch(node.right)
                else:
                    return res
        return recursiveSearch(self.node)

    def __getitem__(self, k, t=None):
        if t is None: t = self.node
        if k < self.count(t.left):
            if t.left is None:
                return t.val
            return self.__getitem__(k, t.left)
        elif k == self.count(t.left):
            return t.val
        else:
            if t.right is None:
                return t.val
            return self.__getitem__(k - self.count(t.left) - 1, t.right)

    class Node:
        def __init__(self, x):
            self.val = x
            self.priority = random.randint(0, 1<<30)
            self.left = None
            self.right = None
            self.cnt = 1
        def __str__(self):
            return str(self.val)

    def count(self, t: Node):
        return 0 if t is None else t.cnt

    def update(self, t: Node):
        t.cnt = self.count(t.left) + self.count(t.right) + 1
        return t

    def merge(self, l: Node, r: Node):
        if l is None: return r
        if r is None: return l
        if l.priority > r.priority:
            l.right = self.merge(l.right, r)
            return self.update(l)
        else:
            r.left = self.merge(l, r.left)
            return self.update(r)

    def split(self, t: Node, k: int) -> (Node, Node):  # [0,k),[k,n)
        if t is None: return None, None
        if k <= self.count(t.left):
            s = self.split(t.left, k)
            t.left = s[1]
            return s[0], self.update(t)
        else:
            s = self.split(t.right, k - self.count(t.left) - 1)
            t.right = s[0]
            return self.update(t), s[1]

    def insert(self, t: Node, k: int, x):
        l, r = self.split(t, k)
        return self.merge(self.merge(l, self.Node(x)), r)

    def erase(self, t: Node, k):
        l, r = self.split(t, k)
        _, r = self.split(r, 1)
        return self.merge(l, r)

    
def main():
  n,p=map(int,sys.stdin.buffer.readline().split())

  e=[]
  for _ in range(n):
      s,t,x = map(int,sys.stdin.buffer.readline().split())
      e.append((s-x,1,x))
      e.append((t-x,-1,x))
  e.sort()
  q = deque()
  for _ in range(p):
      q.append(int(input()))
  s=Treap()

  for t,f,x in e:
      while t > q[0]:
          q.popleft()
          if s.node:
              print(s[0])
          else:
              print(-1)
          if not q:
              sys.exit()
      if f == 1:
          s.add(x)
      else:
          s.remove(x)

  while q:
      q.pop()
      print(-1)

main()

Fixed submission:
import random
from collections import deque
import sys
sys.stdin.readline

class AvlTree:  # std::set
    def __init__(self, values=None, sorted_=False, n=0):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # n: add メソッドを使う回数の最大値

        # sorted_==True であれば、初期値の数の線形時間で木を構築する
        # 値を追加するときは必ず n を設定する
        if values is None:
            self.left = [-1] * (n + 1)
            self.right = [-1] * (n + 1)
            self.values = [-float("inf")]
            self.diff = [0] * (n + 1)  # left - right
            self.size_l = [0] * (n + 1)
            self.idx_new_val = 0
        else:
            if not sorted_:
                values.sort()
            len_ = self.idx_new_val = len(values)
            n += len_
            self_left = self.left = [-1] * (n + 1)
            self_right = self.right = [-1] * (n + 1)
            self_values = self.values = [-float("inf")] + values
            self_diff = self.diff = [0] * (n + 1)  # left - right
            self_size_l = self.size_l = [0] * (n + 1)

            st = [[1, len_ + 1, 0]]
            while len(st) > 0:  # dfs っぽく木を構築
                l, r, idx_par = st.pop()  # 半開区間
                c = (l + r) >> 1  # python -> //2  pypy -> >>1
                if self_values[c] < self_values[idx_par]:
                    self_left[idx_par] = c
                else:
                    self_right[idx_par] = c
                siz = r - l
                if siz & -siz == siz != 1:  # 2 冪だったら
                    self_diff[c] = 1
                self_size_l[c] = siz_l = c - l
                if siz_l > 0:
                    st.append([l, c, c])
                    c1 = c + 1
                    if c1 < r:  # 左にノードがなければ右には必ず無いので
                        st.append([c1, r, c])

    def rotate_right(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == 2
        idx_l = self_left[idx]
        diff_l = self_diff[idx_l]

        if diff_l == -1:  # 複回転
            idx_lr = self_right[idx_l]
            diff_lr = self_diff[idx_lr]
            if diff_lr == 0:
                self_diff[idx] = 0
                self_diff[idx_l] = 0
            elif diff_lr == 1:
                self_diff[idx] = -1
                self_diff[idx_l] = 0
                self_diff[idx_lr] = 0
            else:  # diff_lr == -1
                self_diff[idx] = 0
                self_diff[idx_l] = 1
                self_diff[idx_lr] = 0

            # 部分木の大きさの計算
            self_size_l[idx_lr] += self_size_l[idx_l] + 1
            self_size_l[idx] -= self_size_l[idx_lr] + 1

            # 回転
            self_right[idx_l] = self_left[idx_lr]
            self_left[idx] = self_right[idx_lr]
            self_left[idx_lr] = idx_l
            self_right[idx_lr] = idx
            lr_container[idx_par] = idx_lr

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = 1
                nb = self_diff[idx_l] = -1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_l] = 0

            # 部分木の大きさの計算
            self_size_l[idx] -= self_size_l[idx_l] + 1

            # 回転
            self_left[idx] = self_right[idx_l]
            self_right[idx_l] = idx
            lr_container[idx_par] = idx_l

            return nb  # 新しい根の diff を返す

    def rotate_left(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == -2
        idx_r = self_right[idx]
        diff_l = self_diff[idx_r]

        if diff_l == 1:  # 複回転
            idx_rl = self_left[idx_r]
            diff_rl = self_diff[idx_rl]
            if diff_rl == 0:
                self_diff[idx] = 0
                self_diff[idx_r] = 0
            elif diff_rl == -1:
                self_diff[idx] = 1
                self_diff[idx_r] = 0
                self_diff[idx_rl] = 0
            else:  # diff_lr == 1
                self_diff[idx] = 0
                self_diff[idx_r] = -1
                self_diff[idx_rl] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] -= self_size_l[idx_rl] + 1
            self_size_l[idx_rl] += self_size_l[idx] + 1

            # 回転
            self_left[idx_r] = self_right[idx_rl]
            self_right[idx] = self_left[idx_rl]
            self_right[idx_rl] = idx_r
            self_left[idx_rl] = idx
            lr_container[idx_par] = idx_rl

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = -1
                nb = self_diff[idx_r] = 1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_r] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] += self_size_l[idx] + 1

            # 回転
            self_right[idx] = self_left[idx_r]
            self_left[idx_r] = idx
            lr_container[idx_par] = idx_r

            return nb  # 新しい根の diff を返す

    def add(self, x):  # insert
        # x を加える
        # x が既に入ってる場合は False を、
        # そうでなければ True を返す

        idx = 0
        path = []
        path_left = []

        self_values = self.values
        self_left = self.left
        self_right = self.right

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if x < value:
                path_left.append(idx)  # 重複を許さないので処理を後にする必要がある
                idx = self_left[idx]
            elif value < x:
                idx = self_right[idx]
            else:  # x == value
                return False  # 重複を許さない

        self.idx_new_val += 1
        self_diff = self.diff
        self_size_l = self.size_l

        idx = path[-1]
        if x < value:
            self_left[idx] = self.idx_new_val
        else:
            self_right[idx] = self.idx_new_val

        self_values.append(x)

        for idx_ in path_left:
            self_size_l[idx_] += 1

        self_diff[idx] += 1 if x < value else -1
        for idx_par in path[-2::-1]:
            diff = self_diff[idx]
            if diff == 0:
                return True
            elif diff == 2:  # 右回転
                self.rotate_right(idx_par, self_right[idx_par] == idx)
                return True
            elif diff == -2:  # 左回転
                self.rotate_left(idx_par, self_right[idx_par] == idx)
                return True
            else:
                self_diff[idx_par] += 1 if self_left[idx_par] == idx else -1
            idx = idx_par
        return True

    def remove(self, x):  # erase
        # x を削除する
        # x の存在が保証されている必要がある

        idx = 0
        path = []
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if value < x:
                idx = self_right[idx]
            elif x < value:
                self_size_l[idx] -= 1  # 値の存在を保証しているので
                idx = self_left[idx]
            else:  # x == value
                idx_x = idx
                self_size_l[idx] -= 1
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return True
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return True
            else:
                return True
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return True

    def pop(self, idx_):
        # 小さい方から idx_ 番目の要素を削除してその要素を返す（0-indexed）
        # idx_ 番目の値の存在が保証されている必要がある

        path = [0]
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            path.append(idx)
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                self_size_l[idx] -= 1  # 値の存在が保証されているので
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:
                idx_x = idx
                x = self_values[idx]
                self_size_l[idx] -= 1  # なんで？
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return x
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return x
            else:
                return x
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return x

    def __getitem__(self, idx_):
        # 小さい方から idx_ 番目の要素を返す

        self_left = self.left
        self_right = self.right
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:  # c == idx_
                return self.values[idx]
        raise IndexError

    def __contains__(self, x):  # count
        # 値 x があるか

        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:
                return True  # res + self_size_l[idx]
        return False

    def bisect_left(self, x):  # lower_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x
                return res + self_size_l[idx]
        return res

    def bisect_right(self, x):  # upper_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x:
                return res + self_size_l[idx] + 1
        return res

    def print_tree(self, idx=0, depth=0, from_="・"):
        if idx == 0:
            idx = self.right[idx]
        if idx == -1:
            return
        self.print_tree(self.left[idx], depth + 1, "┏")
        print("\t\t" * depth + from_ + " val=[" + str(self.values[idx]) +
              "] diff=[" + str(self.diff[idx]) +
              "] size_l=[" + str(self.size_l[idx]) + "]")
        self.print_tree(self.right[idx], depth + 1, "┗")

    
def main():
  n,p=map(int,sys.stdin.buffer.readline().split())

  e=[]
  for _ in range(n):
      s,t,x = map(int,sys.stdin.buffer.readline().split())
      e.append((s-x,1,x))
      e.append((t-x,-1,x))
  e.sort()
  q = deque()
  for _ in range(p):
      q.append(int(input()))
  s=AvlTree(n=len(e))

  for t,f,x in e:
      while t > q[0]:
          q.popleft()
          try:
              print(s[0])
          except IndexError:
              print(-1)
          if not q:
              sys.exit()
      if f == 1:
          s.add(x)
      else:
          s.remove(x)

  while q:
      q.pop()
      print(-1)

main()

Buggy python submission (verdict: Time Limit Exceeded):
import random
from collections import deque
import sys
sys.stdin.readline

import random
class Treap:
    def __init__(self):
        self.node = None  # root

    def __str__(self):
        L = []
        def recursiveSearch(node):
            if node.left is not None:
                recursiveSearch(node.left)
            L.append((node.val, node.priority))
            if node.right is not None:
                recursiveSearch(node.right)
        recursiveSearch(self.node)
        return str(L)

    def add(self, x):
        i = self.bisect(x)
        self.node = self.insert(self.node, i, x)

    def remove(self, x):
        i = self.bisect(x)
        self.node = self.erase(self.node, i)

    def bisect(self, x):  # bisect_left
        def recursiveSearch(node):
            if node is None:
                return 0
            res = 0
            if x <= node.val:
                if node.left is not None:
                    return recursiveSearch(node.left)
                else:
                    return 0
            else:
                res += self.count(node.left) + 1
                if node.right is not None:
                    return res + recursiveSearch(node.right)
                else:
                    return res
        return recursiveSearch(self.node)

    def __getitem__(self, k, t=None):
        if t is None: t = self.node
        if k < self.count(t.left):
            if t.left is None:
                return t.val
            return self.__getitem__(k, t.left)
        elif k == self.count(t.left):
            return t.val
        else:
            if t.right is None:
                return t.val
            return self.__getitem__(k - self.count(t.left) - 1, t.right)

    class Node:
        def __init__(self, x):
            self.val = x
            self.priority = random.randint(0, 1<<30)
            self.left = None
            self.right = None
            self.cnt = 1
        def __str__(self):
            return str(self.val)

    def count(self, t: Node):
        return 0 if t is None else t.cnt

    def update(self, t: Node):
        t.cnt = self.count(t.left) + self.count(t.right) + 1
        return t

    def merge(self, l: Node, r: Node):
        if l is None: return r
        if r is None: return l
        if l.priority > r.priority:
            l.right = self.merge(l.right, r)
            return self.update(l)
        else:
            r.left = self.merge(l, r.left)
            return self.update(r)

    def split(self, t: Node, k: int) -> (Node, Node):  # [0,k),[k,n)
        if t is None: return None, None
        if k <= self.count(t.left):
            s = self.split(t.left, k)
            t.left = s[1]
            return s[0], self.update(t)
        else:
            s = self.split(t.right, k - self.count(t.left) - 1)
            t.right = s[0]
            return self.update(t), s[1]

    def insert(self, t: Node, k: int, x):
        l, r = self.split(t, k)
        return self.merge(self.merge(l, self.Node(x)), r)

    def erase(self, t: Node, k):
        l, r = self.split(t, k)
        _, r = self.split(r, 1)
        return self.merge(l, r)

    
def main():
  n,p=map(int,sys.stdin.buffer.readline().split())

  e=[]
  for _ in range(n):
      s,t,x = map(int,sys.stdin.buffer.readline().split())
      e.append((s-x,1,x))
      e.append((t-x,-1,x))
  e.sort()
  q = deque()
  for _ in range(p):
      q.append(int(input()))
  s=Treap()

  for t,f,x in e:
      while t > q[0]:
          q.popleft()
          if s.node:
              print(s[0])
          else:
              print(-1)
          if not q:
              sys.exit()
      if f == 1:
          s.add(x)
      else:
          s.remove(x)

  while q:
      q.pop()
      print(-1)

main()

Fixed submission:
import random
from collections import deque
import sys
sys.stdin.readline

class AvlTree:  # std::set
    def __init__(self, values=None, sorted_=False, n=0):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # n: add メソッドを使う回数の最大値

        # sorted_==True であれば、初期値の数の線形時間で木を構築する
        # 値を追加するときは必ず n を設定する
        if values is None:
            self.left = [-1] * (n + 1)
            self.right = [-1] * (n + 1)
            self.values = [-float("inf")]
            self.diff = [0] * (n + 1)  # left - right
            self.size_l = [0] * (n + 1)
            self.idx_new_val = 0
        else:
            if not sorted_:
                values.sort()
            len_ = self.idx_new_val = len(values)
            n += len_
            self_left = self.left = [-1] * (n + 1)
            self_right = self.right = [-1] * (n + 1)
            self_values = self.values = [-float("inf")] + values
            self_diff = self.diff = [0] * (n + 1)  # left - right
            self_size_l = self.size_l = [0] * (n + 1)

            st = [[1, len_ + 1, 0]]
            while len(st) > 0:  # dfs っぽく木を構築
                l, r, idx_par = st.pop()  # 半開区間
                c = (l + r) >> 1  # python -> //2  pypy -> >>1
                if self_values[c] < self_values[idx_par]:
                    self_left[idx_par] = c
                else:
                    self_right[idx_par] = c
                siz = r - l
                if siz & -siz == siz != 1:  # 2 冪だったら
                    self_diff[c] = 1
                self_size_l[c] = siz_l = c - l
                if siz_l > 0:
                    st.append([l, c, c])
                    c1 = c + 1
                    if c1 < r:  # 左にノードがなければ右には必ず無いので
                        st.append([c1, r, c])

    def rotate_right(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == 2
        idx_l = self_left[idx]
        diff_l = self_diff[idx_l]

        if diff_l == -1:  # 複回転
            idx_lr = self_right[idx_l]
            diff_lr = self_diff[idx_lr]
            if diff_lr == 0:
                self_diff[idx] = 0
                self_diff[idx_l] = 0
            elif diff_lr == 1:
                self_diff[idx] = -1
                self_diff[idx_l] = 0
                self_diff[idx_lr] = 0
            else:  # diff_lr == -1
                self_diff[idx] = 0
                self_diff[idx_l] = 1
                self_diff[idx_lr] = 0

            # 部分木の大きさの計算
            self_size_l[idx_lr] += self_size_l[idx_l] + 1
            self_size_l[idx] -= self_size_l[idx_lr] + 1

            # 回転
            self_right[idx_l] = self_left[idx_lr]
            self_left[idx] = self_right[idx_lr]
            self_left[idx_lr] = idx_l
            self_right[idx_lr] = idx
            lr_container[idx_par] = idx_lr

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = 1
                nb = self_diff[idx_l] = -1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_l] = 0

            # 部分木の大きさの計算
            self_size_l[idx] -= self_size_l[idx_l] + 1

            # 回転
            self_left[idx] = self_right[idx_l]
            self_right[idx_l] = idx
            lr_container[idx_par] = idx_l

            return nb  # 新しい根の diff を返す

    def rotate_left(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == -2
        idx_r = self_right[idx]
        diff_l = self_diff[idx_r]

        if diff_l == 1:  # 複回転
            idx_rl = self_left[idx_r]
            diff_rl = self_diff[idx_rl]
            if diff_rl == 0:
                self_diff[idx] = 0
                self_diff[idx_r] = 0
            elif diff_rl == -1:
                self_diff[idx] = 1
                self_diff[idx_r] = 0
                self_diff[idx_rl] = 0
            else:  # diff_lr == 1
                self_diff[idx] = 0
                self_diff[idx_r] = -1
                self_diff[idx_rl] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] -= self_size_l[idx_rl] + 1
            self_size_l[idx_rl] += self_size_l[idx] + 1

            # 回転
            self_left[idx_r] = self_right[idx_rl]
            self_right[idx] = self_left[idx_rl]
            self_right[idx_rl] = idx_r
            self_left[idx_rl] = idx
            lr_container[idx_par] = idx_rl

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = -1
                nb = self_diff[idx_r] = 1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_r] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] += self_size_l[idx] + 1

            # 回転
            self_right[idx] = self_left[idx_r]
            self_left[idx_r] = idx
            lr_container[idx_par] = idx_r

            return nb  # 新しい根の diff を返す

    def add(self, x):  # insert
        # x を加える
        # x が既に入ってる場合は False を、
        # そうでなければ True を返す

        idx = 0
        path = []
        path_left = []

        self_values = self.values
        self_left = self.left
        self_right = self.right

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if x < value:
                path_left.append(idx)  # 重複を許さないので処理を後にする必要がある
                idx = self_left[idx]
            elif value < x:
                idx = self_right[idx]
            else:  # x == value
                return False  # 重複を許さない

        self.idx_new_val += 1
        self_diff = self.diff
        self_size_l = self.size_l

        idx = path[-1]
        if x < value:
            self_left[idx] = self.idx_new_val
        else:
            self_right[idx] = self.idx_new_val

        self_values.append(x)

        for idx_ in path_left:
            self_size_l[idx_] += 1

        self_diff[idx] += 1 if x < value else -1
        for idx_par in path[-2::-1]:
            diff = self_diff[idx]
            if diff == 0:
                return True
            elif diff == 2:  # 右回転
                self.rotate_right(idx_par, self_right[idx_par] == idx)
                return True
            elif diff == -2:  # 左回転
                self.rotate_left(idx_par, self_right[idx_par] == idx)
                return True
            else:
                self_diff[idx_par] += 1 if self_left[idx_par] == idx else -1
            idx = idx_par
        return True

    def remove(self, x):  # erase
        # x を削除する
        # x の存在が保証されている必要がある

        idx = 0
        path = []
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if value < x:
                idx = self_right[idx]
            elif x < value:
                self_size_l[idx] -= 1  # 値の存在を保証しているので
                idx = self_left[idx]
            else:  # x == value
                idx_x = idx
                self_size_l[idx] -= 1
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return True
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return True
            else:
                return True
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return True

    def pop(self, idx_):
        # 小さい方から idx_ 番目の要素を削除してその要素を返す（0-indexed）
        # idx_ 番目の値の存在が保証されている必要がある

        path = [0]
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            path.append(idx)
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                self_size_l[idx] -= 1  # 値の存在が保証されているので
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:
                idx_x = idx
                x = self_values[idx]
                self_size_l[idx] -= 1  # なんで？
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return x
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return x
            else:
                return x
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return x

    def __getitem__(self, idx_):
        # 小さい方から idx_ 番目の要素を返す

        self_left = self.left
        self_right = self.right
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:  # c == idx_
                return self.values[idx]
        raise IndexError

    def __contains__(self, x):  # count
        # 値 x があるか

        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:
                return True  # res + self_size_l[idx]
        return False

    def bisect_left(self, x):  # lower_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x
                return res + self_size_l[idx]
        return res

    def bisect_right(self, x):  # upper_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x:
                return res + self_size_l[idx] + 1
        return res

    def print_tree(self, idx=0, depth=0, from_="・"):
        if idx == 0:
            idx = self.right[idx]
        if idx == -1:
            return
        self.print_tree(self.left[idx], depth + 1, "┏")
        print("\t\t" * depth + from_ + " val=[" + str(self.values[idx]) +
              "] diff=[" + str(self.diff[idx]) +
              "] size_l=[" + str(self.size_l[idx]) + "]")
        self.print_tree(self.right[idx], depth + 1, "┗")

    
def main():
  n,p=map(int,sys.stdin.buffer.readline().split())

  e=[]
  for _ in range(n):
      s,t,x = map(int,sys.stdin.buffer.readline().split())
      e.append((s-x,1,x))
      e.append((t-x,-1,x))
  e.sort()
  q = deque()
  for _ in range(p):
      q.append(int(input()))
  s=AvlTree(n=len(e))

  for t,f,x in e:
      while t > q[0]:
          q.popleft()
          try:
              print(s[0])
          except IndexError:
              print(-1)
          if not q:
              sys.exit()
      if f == 1:
          s.add(x)
      else:
          s.remove(x)

  while q:
      q.pop()
      print(-1)

main()

Buggy python submission (verdict: Time Limit Exceeded):
import random
from collections import deque
import sys
sys.stdin.readline

import random
class Treap:
    def __init__(self):
        self.node = None  # root

    def __str__(self):
        L = []
        def recursiveSearch(node):
            if node.left is not None:
                recursiveSearch(node.left)
            L.append((node.val, node.priority))
            if node.right is not None:
                recursiveSearch(node.right)
        recursiveSearch(self.node)
        return str(L)

    def add(self, x):
        i = self.bisect(x)
        self.node = self.insert(self.node, i, x)

    def remove(self, x):
        i = self.bisect(x)
        self.node = self.erase(self.node, i)

    def bisect(self, x):  # bisect_left
        def recursiveSearch(node):
            if node is None:
                return 0
            res = 0
            if x <= node.val:
                if node.left is not None:
                    return recursiveSearch(node.left)
                else:
                    return 0
            else:
                res += self.count(node.left) + 1
                if node.right is not None:
                    return res + recursiveSearch(node.right)
                else:
                    return res
        return recursiveSearch(self.node)

    def __getitem__(self, k, t=None):
        if t is None: t = self.node
        if k < self.count(t.left):
            if t.left is None:
                return t.val
            return self.__getitem__(k, t.left)
        elif k == self.count(t.left):
            return t.val
        else:
            if t.right is None:
                return t.val
            return self.__getitem__(k - self.count(t.left) - 1, t.right)

    class Node:
        def __init__(self, x):
            self.val = x
            self.priority = random.randint(0, 1<<30)
            self.left = None
            self.right = None
            self.cnt = 1
        def __str__(self):
            return str(self.val)

    def count(self, t: Node):
        return 0 if t is None else t.cnt

    def update(self, t: Node):
        t.cnt = self.count(t.left) + self.count(t.right) + 1
        return t

    def merge(self, l: Node, r: Node):
        if l is None: return r
        if r is None: return l
        if l.priority > r.priority:
            l.right = self.merge(l.right, r)
            return self.update(l)
        else:
            r.left = self.merge(l, r.left)
            return self.update(r)

    def split(self, t: Node, k: int) -> (Node, Node):  # [0,k),[k,n)
        if t is None: return None, None
        if k <= self.count(t.left):
            s = self.split(t.left, k)
            t.left = s[1]
            return s[0], self.update(t)
        else:
            s = self.split(t.right, k - self.count(t.left) - 1)
            t.right = s[0]
            return self.update(t), s[1]

    def insert(self, t: Node, k: int, x):
        l, r = self.split(t, k)
        return self.merge(self.merge(l, self.Node(x)), r)

    def erase(self, t: Node, k):
        l, r = self.split(t, k)
        _, r = self.split(r, 1)
        return self.merge(l, r)

      
n,p=map(int,input().split())

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
e.sort()
q = deque()
for _ in range(p):
    q.append(int(input()))
s=Treap()

for t,f,x in e:
    while t > q[0]:
        q.popleft()
        if s.node:
            print(s[0])
        else:
            print(-1)
        if not q:
            sys.exit()
    if f == 1:
        s.add(x)
    else:
        s.remove(x)
        
while q:
    q.pop()
    print(-1)


Fixed submission:
import random
from collections import deque
import sys
sys.stdin.readline

class AvlTree:  # std::set
    def __init__(self, values=None, sorted_=False, n=0):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # n: add メソッドを使う回数の最大値

        # sorted_==True であれば、初期値の数の線形時間で木を構築する
        # 値を追加するときは必ず n を設定する
        if values is None:
            self.left = [-1] * (n + 1)
            self.right = [-1] * (n + 1)
            self.values = [-float("inf")]
            self.diff = [0] * (n + 1)  # left - right
            self.size_l = [0] * (n + 1)
            self.idx_new_val = 0
        else:
            if not sorted_:
                values.sort()
            len_ = self.idx_new_val = len(values)
            n += len_
            self_left = self.left = [-1] * (n + 1)
            self_right = self.right = [-1] * (n + 1)
            self_values = self.values = [-float("inf")] + values
            self_diff = self.diff = [0] * (n + 1)  # left - right
            self_size_l = self.size_l = [0] * (n + 1)

            st = [[1, len_ + 1, 0]]
            while len(st) > 0:  # dfs っぽく木を構築
                l, r, idx_par = st.pop()  # 半開区間
                c = (l + r) >> 1  # python -> //2  pypy -> >>1
                if self_values[c] < self_values[idx_par]:
                    self_left[idx_par] = c
                else:
                    self_right[idx_par] = c
                siz = r - l
                if siz & -siz == siz != 1:  # 2 冪だったら
                    self_diff[c] = 1
                self_size_l[c] = siz_l = c - l
                if siz_l > 0:
                    st.append([l, c, c])
                    c1 = c + 1
                    if c1 < r:  # 左にノードがなければ右には必ず無いので
                        st.append([c1, r, c])

    def rotate_right(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == 2
        idx_l = self_left[idx]
        diff_l = self_diff[idx_l]

        if diff_l == -1:  # 複回転
            idx_lr = self_right[idx_l]
            diff_lr = self_diff[idx_lr]
            if diff_lr == 0:
                self_diff[idx] = 0
                self_diff[idx_l] = 0
            elif diff_lr == 1:
                self_diff[idx] = -1
                self_diff[idx_l] = 0
                self_diff[idx_lr] = 0
            else:  # diff_lr == -1
                self_diff[idx] = 0
                self_diff[idx_l] = 1
                self_diff[idx_lr] = 0

            # 部分木の大きさの計算
            self_size_l[idx_lr] += self_size_l[idx_l] + 1
            self_size_l[idx] -= self_size_l[idx_lr] + 1

            # 回転
            self_right[idx_l] = self_left[idx_lr]
            self_left[idx] = self_right[idx_lr]
            self_left[idx_lr] = idx_l
            self_right[idx_lr] = idx
            lr_container[idx_par] = idx_lr

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = 1
                nb = self_diff[idx_l] = -1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_l] = 0

            # 部分木の大きさの計算
            self_size_l[idx] -= self_size_l[idx_l] + 1

            # 回転
            self_left[idx] = self_right[idx_l]
            self_right[idx_l] = idx
            lr_container[idx_par] = idx_l

            return nb  # 新しい根の diff を返す

    def rotate_left(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == -2
        idx_r = self_right[idx]
        diff_l = self_diff[idx_r]

        if diff_l == 1:  # 複回転
            idx_rl = self_left[idx_r]
            diff_rl = self_diff[idx_rl]
            if diff_rl == 0:
                self_diff[idx] = 0
                self_diff[idx_r] = 0
            elif diff_rl == -1:
                self_diff[idx] = 1
                self_diff[idx_r] = 0
                self_diff[idx_rl] = 0
            else:  # diff_lr == 1
                self_diff[idx] = 0
                self_diff[idx_r] = -1
                self_diff[idx_rl] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] -= self_size_l[idx_rl] + 1
            self_size_l[idx_rl] += self_size_l[idx] + 1

            # 回転
            self_left[idx_r] = self_right[idx_rl]
            self_right[idx] = self_left[idx_rl]
            self_right[idx_rl] = idx_r
            self_left[idx_rl] = idx
            lr_container[idx_par] = idx_rl

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = -1
                nb = self_diff[idx_r] = 1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_r] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] += self_size_l[idx] + 1

            # 回転
            self_right[idx] = self_left[idx_r]
            self_left[idx_r] = idx
            lr_container[idx_par] = idx_r

            return nb  # 新しい根の diff を返す

    def add(self, x):  # insert
        # x を加える
        # x が既に入ってる場合は False を、
        # そうでなければ True を返す

        idx = 0
        path = []
        path_left = []

        self_values = self.values
        self_left = self.left
        self_right = self.right

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if x < value:
                path_left.append(idx)  # 重複を許さないので処理を後にする必要がある
                idx = self_left[idx]
            elif value < x:
                idx = self_right[idx]
            else:  # x == value
                return False  # 重複を許さない

        self.idx_new_val += 1
        self_diff = self.diff
        self_size_l = self.size_l

        idx = path[-1]
        if x < value:
            self_left[idx] = self.idx_new_val
        else:
            self_right[idx] = self.idx_new_val

        self_values.append(x)

        for idx_ in path_left:
            self_size_l[idx_] += 1

        self_diff[idx] += 1 if x < value else -1
        for idx_par in path[-2::-1]:
            diff = self_diff[idx]
            if diff == 0:
                return True
            elif diff == 2:  # 右回転
                self.rotate_right(idx_par, self_right[idx_par] == idx)
                return True
            elif diff == -2:  # 左回転
                self.rotate_left(idx_par, self_right[idx_par] == idx)
                return True
            else:
                self_diff[idx_par] += 1 if self_left[idx_par] == idx else -1
            idx = idx_par
        return True

    def remove(self, x):  # erase
        # x を削除する
        # x の存在が保証されている必要がある

        idx = 0
        path = []
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if value < x:
                idx = self_right[idx]
            elif x < value:
                self_size_l[idx] -= 1  # 値の存在を保証しているので
                idx = self_left[idx]
            else:  # x == value
                idx_x = idx
                self_size_l[idx] -= 1
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return True
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return True
            else:
                return True
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return True

    def pop(self, idx_):
        # 小さい方から idx_ 番目の要素を削除してその要素を返す（0-indexed）
        # idx_ 番目の値の存在が保証されている必要がある

        path = [0]
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            path.append(idx)
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                self_size_l[idx] -= 1  # 値の存在が保証されているので
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:
                idx_x = idx
                x = self_values[idx]
                self_size_l[idx] -= 1  # なんで？
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return x
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return x
            else:
                return x
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return x

    def __getitem__(self, idx_):
        # 小さい方から idx_ 番目の要素を返す

        self_left = self.left
        self_right = self.right
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:  # c == idx_
                return self.values[idx]
        raise IndexError

    def __contains__(self, x):  # count
        # 値 x があるか

        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:
                return True  # res + self_size_l[idx]
        return False

    def bisect_left(self, x):  # lower_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x
                return res + self_size_l[idx]
        return res

    def bisect_right(self, x):  # upper_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x:
                return res + self_size_l[idx] + 1
        return res

    def print_tree(self, idx=0, depth=0, from_="・"):
        if idx == 0:
            idx = self.right[idx]
        if idx == -1:
            return
        self.print_tree(self.left[idx], depth + 1, "┏")
        print("\t\t" * depth + from_ + " val=[" + str(self.values[idx]) +
              "] diff=[" + str(self.diff[idx]) +
              "] size_l=[" + str(self.size_l[idx]) + "]")
        self.print_tree(self.right[idx], depth + 1, "┗")

    
def main():
  n,p=map(int,sys.stdin.buffer.readline().split())

  e=[]
  for _ in range(n):
      s,t,x = map(int,sys.stdin.buffer.readline().split())
      e.append((s-x,1,x))
      e.append((t-x,-1,x))
  e.sort()
  q = deque()
  for _ in range(p):
      q.append(int(input()))
  s=AvlTree(n=len(e))

  for t,f,x in e:
      while t > q[0]:
          q.popleft()
          try:
              print(s[0])
          except IndexError:
              print(-1)
          if not q:
              sys.exit()
      if f == 1:
          s.add(x)
      else:
          s.remove(x)

  while q:
      q.pop()
      print(-1)

main()

Buggy python submission (verdict: Time Limit Exceeded):
import random
from collections import deque
import sys
sys.stdin.readline


class Node: # ノードの型
    def __init__(self, height, key, x):
        self.height = height # そのノードを根とする部分木の高さ
        self.key    = key    # そのノードのキー
        self.value  = x      # そのノードの値
        self.lst    = None   # 左部分木
        self.rst    = None   # 右部分木

# 部分木 t の高さを返す
def height(t): return 0 if t is None else t.height

# 左右の部分木の高さの差を返す。左が高いと正、右が高いと負
def bias(t): return height(t.lst) - height(t.rst)

# 左右の部分木の高さから、その木の高さを計算して修正する
def modHeight(t): t.height = 1 + max(height(t.lst), height(t.rst))

def rotateL(v): # ２分探索木 v の左回転。回転した木を返す
    u = v.rst; t2 = u.lst
    u.lst = v; v.rst = t2
    modHeight(u.lst)
    modHeight(u)
    return u
def rotateR(u): # ２分探索木 u の右回転。回転した木を返す
    v = u.lst; t2 = v.rst
    v.rst = u; u.lst = t2
    modHeight(v.rst)
    modHeight(v)
    return v
def rotateLR(t): # ２分探索木 t の二重回転(左回転 -> 右回転)。回転した木を返す
    t.lst = rotateL(t.lst)
    return rotateR(t)
def rotateRL(t): # ２分探索木 t の二重回転(右回転 -> 左回転)。回転した木を返す
    t.rst = rotateR(t.rst)
    return rotateL(t)

###############################################################################
# AVL木マップクラス
###############################################################################

class AVLMap:
    def __init__(self):
        self.root   = None  # AVL木の根。Node 型
        self.change = False # 修正が必要かを示すフラグ(True:必要, False:不要)
        self.lmax   = None  # 左部分木のキーの最大値
        self.value  = None  # lmax に対応する値

    ###########################################################################
    # バランス回復
    ###########################################################################

    # 挿入時の修正(balanceLi:左部分木への挿入, balanceRi:右部分木への挿入)
    def balanceLi(self, t): return self.balanceL(t)
    def balanceRi(self, t): return self.balanceR(t)

    # 削除時の修正(balanceLd:左部分木での削除, balanceRd:右部分木での削除)
    def balanceLd(self, t): return self.balanceR(t)
    def balanceRd(self, t): return self.balanceL(t)

    # 部分木 t のバランスを回復して戻り値で返す
    # 左部分木への挿入に伴うAVL木の修正
    # 右部分木での削除に伴うAVL木の修正
    def balanceL(self, t):
        if not self.change: return t
        h = height(t)
        if bias(t) == 2:
            if bias(t.lst) >= 0:
                t = rotateR(t)
            else:
                t = rotateLR(t)
        else: modHeight(t)
        self.change = (h != height(t))
        return t

    # 部分木 t のバランスを回復して戻り値で返す
    # 右部分木への挿入に伴うAVL木の修正
    # 左部分木での削除に伴うAVL木の修正
    def balanceR(self, t):
        if not self.change: return t
        h = height(t)
        if bias(t) == -2:
            if bias(t.rst) <= 0:
                t = rotateL(t)
            else:
                t = rotateRL(t)
        else: modHeight(t)
        self.change = (h != height(t))
        return t

    ###########################################################################
    # insert(挿入)
    ###########################################################################

    # エントリー(key, x のペア)を挿入する
    def insert(self, key, x): self.root = self.insert_sub(self.root, key, x)

    def insert_sub(self, t, key, x):
        if t is None:
            self.change = True
            return Node(1, key, x)
        elif key < t.key:
            t.lst = self.insert_sub(t.lst, key, x)
            return self.balanceLi(t)
        elif key > t.key:
            t.rst = self.insert_sub(t.rst, key, x)
            return self.balanceRi(t)
        else:
            self.change = False
            t.value = x
            return t

    ###########################################################################
    # delete(削除)
    ###########################################################################

    # key で指すエントリー(ノード)を削除する
    def delete(self, key): self.root = self.delete_sub(self.root, key)

    def delete_sub(self, t, key):
        if t is None:
            self.change = False
            return None
        elif key < t.key:
            t.lst = self.delete_sub(t.lst, key)
            return self.balanceLd(t)
        elif key > t.key:
            t.rst = self.delete_sub(t.rst, key)
            return self.balanceRd(t)
        else:
            if t.lst is None:
                self.change = True
                return t.rst # 右部分木を昇格させる
            else:
                t.lst = self.delete_max(t.lst) # 左部分木の最大値を削除する
                t.key = self.lmax # 左部分木の削除した最大値で置き換える
                t.value = self.value
                return self.balanceLd(t)

    # 部分木 t の最大値のノードを削除する
    # 戻り値は削除により修正された部分木
    # 削除した最大値を lmax に保存する
    def delete_max(self, t):
        if t.rst is not None:
            t.rst = self.delete_max(t.rst)
            return self.balanceRd(t)
        else:
            self.change = True
            self.lmax = t.key # 部分木のキーの最大値を保存
            self.value = t.value
            return t.lst # 左部分木を昇格させる

    ###########################################################################
    # member(検索)等
    ###########################################################################

    # キーの検索。ヒットすれば True、しなければ False
    def member(self, key):
        t = self.root
        while t is not None:
            if key < t.key:
                t = t.lst
            elif key > t.key:
                t = t.rst
            else:
                return True
        return False

    # キーから値を得る。キーがヒットしない場合は None を返す
    def lookup(self, key):
        t = self.root
        while t is not None:
            if key < t.key:
                t = t.lst
            elif key > t.key:
                t = t.rst
            else:
                return t.value
        return None

    # マップが空なら True、空でないなら False
    def isEmpty(self): return self.root is None

    # マップを空にする
    def clear(self): self.root = None

    # キーのリスト
    def keys(self): return keys_sub(self.root)

    # 値のリスト
    def values(self): return values_sub(self.root)

    # エントリーのリスト
    def items(self): return items_sub(self.root)

    # マップのサイズ
    def size(self): return len(self.keys())

    def __contains__(self, key): self.member(key)
    def __getitem__(self, key): return self.lookup(key)
    def __setitem__(self, key, x): return self.insert(key, x)
    def __delitem__(self, key): self.delete(key)
    def __bool__(self): return not self.isEmpty()
    def __len__(self): return self.size()
    def __iter__(self): return iter(self.keys())

    ###########################################################################
    # Debug 用メソッド
    ###########################################################################

    # AVL木をグラフ文字列に変換する
    def __str__(self): return toGraph("", "", self.root).rstrip()

    # AVL木のバランスが取れているか確認する
    def balanced(self): return balanced(self.root)

    # ２分探索木になっているか確認する
    def bstValid(self): return bstValid(self.root)
      
      
def keys_sub(t):
    if t is None: return []
    return keys_sub(t.lst) + [t.key] + keys_sub(t.rst)

def values_sub(t):
    if t is None: return []
    return values_sub(t.lst) + [t.value] + values_sub(t.rst)

def items_sub(t):
    if t is None: return []
    return items_sub(t.lst) + [(t.key, t.value)] + items_sub(t.rst)

      
n,p=map(int,input().split())

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
e.sort()
q = deque()
for _ in range(p):
    q.append(int(input()))
s=AVLMap()

for t,f,x in e:
    while t > q[0]:
        q.popleft()
        if s:
            print(next(iter(s)))
        else:
            print(-1)
        if not q:
            sys.exit()
    if f == 1:
        s.insert(x, 1)
    else:
        s.delete(x)
        
while q:
    q.pop()
    print(-1)


Fixed submission:
import random
from collections import deque
import sys
sys.stdin.readline

class AvlTree:  # std::set
    def __init__(self, values=None, sorted_=False, n=0):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # n: add メソッドを使う回数の最大値

        # sorted_==True であれば、初期値の数の線形時間で木を構築する
        # 値を追加するときは必ず n を設定する
        if values is None:
            self.left = [-1] * (n + 1)
            self.right = [-1] * (n + 1)
            self.values = [-float("inf")]
            self.diff = [0] * (n + 1)  # left - right
            self.size_l = [0] * (n + 1)
            self.idx_new_val = 0
        else:
            if not sorted_:
                values.sort()
            len_ = self.idx_new_val = len(values)
            n += len_
            self_left = self.left = [-1] * (n + 1)
            self_right = self.right = [-1] * (n + 1)
            self_values = self.values = [-float("inf")] + values
            self_diff = self.diff = [0] * (n + 1)  # left - right
            self_size_l = self.size_l = [0] * (n + 1)

            st = [[1, len_ + 1, 0]]
            while len(st) > 0:  # dfs っぽく木を構築
                l, r, idx_par = st.pop()  # 半開区間
                c = (l + r) >> 1  # python -> //2  pypy -> >>1
                if self_values[c] < self_values[idx_par]:
                    self_left[idx_par] = c
                else:
                    self_right[idx_par] = c
                siz = r - l
                if siz & -siz == siz != 1:  # 2 冪だったら
                    self_diff[c] = 1
                self_size_l[c] = siz_l = c - l
                if siz_l > 0:
                    st.append([l, c, c])
                    c1 = c + 1
                    if c1 < r:  # 左にノードがなければ右には必ず無いので
                        st.append([c1, r, c])

    def rotate_right(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == 2
        idx_l = self_left[idx]
        diff_l = self_diff[idx_l]

        if diff_l == -1:  # 複回転
            idx_lr = self_right[idx_l]
            diff_lr = self_diff[idx_lr]
            if diff_lr == 0:
                self_diff[idx] = 0
                self_diff[idx_l] = 0
            elif diff_lr == 1:
                self_diff[idx] = -1
                self_diff[idx_l] = 0
                self_diff[idx_lr] = 0
            else:  # diff_lr == -1
                self_diff[idx] = 0
                self_diff[idx_l] = 1
                self_diff[idx_lr] = 0

            # 部分木の大きさの計算
            self_size_l[idx_lr] += self_size_l[idx_l] + 1
            self_size_l[idx] -= self_size_l[idx_lr] + 1

            # 回転
            self_right[idx_l] = self_left[idx_lr]
            self_left[idx] = self_right[idx_lr]
            self_left[idx_lr] = idx_l
            self_right[idx_lr] = idx
            lr_container[idx_par] = idx_lr

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = 1
                nb = self_diff[idx_l] = -1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_l] = 0

            # 部分木の大きさの計算
            self_size_l[idx] -= self_size_l[idx_l] + 1

            # 回転
            self_left[idx] = self_right[idx_l]
            self_right[idx_l] = idx
            lr_container[idx_par] = idx_l

            return nb  # 新しい根の diff を返す

    def rotate_left(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == -2
        idx_r = self_right[idx]
        diff_l = self_diff[idx_r]

        if diff_l == 1:  # 複回転
            idx_rl = self_left[idx_r]
            diff_rl = self_diff[idx_rl]
            if diff_rl == 0:
                self_diff[idx] = 0
                self_diff[idx_r] = 0
            elif diff_rl == -1:
                self_diff[idx] = 1
                self_diff[idx_r] = 0
                self_diff[idx_rl] = 0
            else:  # diff_lr == 1
                self_diff[idx] = 0
                self_diff[idx_r] = -1
                self_diff[idx_rl] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] -= self_size_l[idx_rl] + 1
            self_size_l[idx_rl] += self_size_l[idx] + 1

            # 回転
            self_left[idx_r] = self_right[idx_rl]
            self_right[idx] = self_left[idx_rl]
            self_right[idx_rl] = idx_r
            self_left[idx_rl] = idx
            lr_container[idx_par] = idx_rl

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = -1
                nb = self_diff[idx_r] = 1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_r] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] += self_size_l[idx] + 1

            # 回転
            self_right[idx] = self_left[idx_r]
            self_left[idx_r] = idx
            lr_container[idx_par] = idx_r

            return nb  # 新しい根の diff を返す

    def add(self, x):  # insert
        # x を加える
        # x が既に入ってる場合は False を、
        # そうでなければ True を返す

        idx = 0
        path = []
        path_left = []

        self_values = self.values
        self_left = self.left
        self_right = self.right

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if x < value:
                path_left.append(idx)  # 重複を許さないので処理を後にする必要がある
                idx = self_left[idx]
            elif value < x:
                idx = self_right[idx]
            else:  # x == value
                return False  # 重複を許さない

        self.idx_new_val += 1
        self_diff = self.diff
        self_size_l = self.size_l

        idx = path[-1]
        if x < value:
            self_left[idx] = self.idx_new_val
        else:
            self_right[idx] = self.idx_new_val

        self_values.append(x)

        for idx_ in path_left:
            self_size_l[idx_] += 1

        self_diff[idx] += 1 if x < value else -1
        for idx_par in path[-2::-1]:
            diff = self_diff[idx]
            if diff == 0:
                return True
            elif diff == 2:  # 右回転
                self.rotate_right(idx_par, self_right[idx_par] == idx)
                return True
            elif diff == -2:  # 左回転
                self.rotate_left(idx_par, self_right[idx_par] == idx)
                return True
            else:
                self_diff[idx_par] += 1 if self_left[idx_par] == idx else -1
            idx = idx_par
        return True

    def remove(self, x):  # erase
        # x を削除する
        # x の存在が保証されている必要がある

        idx = 0
        path = []
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if value < x:
                idx = self_right[idx]
            elif x < value:
                self_size_l[idx] -= 1  # 値の存在を保証しているので
                idx = self_left[idx]
            else:  # x == value
                idx_x = idx
                self_size_l[idx] -= 1
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return True
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return True
            else:
                return True
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return True

    def pop(self, idx_):
        # 小さい方から idx_ 番目の要素を削除してその要素を返す（0-indexed）
        # idx_ 番目の値の存在が保証されている必要がある

        path = [0]
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            path.append(idx)
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                self_size_l[idx] -= 1  # 値の存在が保証されているので
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:
                idx_x = idx
                x = self_values[idx]
                self_size_l[idx] -= 1  # なんで？
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return x
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return x
            else:
                return x
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return x

    def __getitem__(self, idx_):
        # 小さい方から idx_ 番目の要素を返す

        self_left = self.left
        self_right = self.right
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:  # c == idx_
                return self.values[idx]
        raise IndexError

    def __contains__(self, x):  # count
        # 値 x があるか

        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:
                return True  # res + self_size_l[idx]
        return False

    def bisect_left(self, x):  # lower_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x
                return res + self_size_l[idx]
        return res

    def bisect_right(self, x):  # upper_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x:
                return res + self_size_l[idx] + 1
        return res

    def print_tree(self, idx=0, depth=0, from_="・"):
        if idx == 0:
            idx = self.right[idx]
        if idx == -1:
            return
        self.print_tree(self.left[idx], depth + 1, "┏")
        print("\t\t" * depth + from_ + " val=[" + str(self.values[idx]) +
              "] diff=[" + str(self.diff[idx]) +
              "] size_l=[" + str(self.size_l[idx]) + "]")
        self.print_tree(self.right[idx], depth + 1, "┗")

    
def main():
  n,p=map(int,sys.stdin.buffer.readline().split())

  e=[]
  for _ in range(n):
      s,t,x = map(int,sys.stdin.buffer.readline().split())
      e.append((s-x,1,x))
      e.append((t-x,-1,x))
  e.sort()
  q = deque()
  for _ in range(p):
      q.append(int(input()))
  s=AvlTree(n=len(e))

  for t,f,x in e:
      while t > q[0]:
          q.popleft()
          try:
              print(s[0])
          except IndexError:
              print(-1)
          if not q:
              sys.exit()
      if f == 1:
          s.add(x)
      else:
          s.remove(x)

  while q:
      q.pop()
      print(-1)

main()

Buggy python submission (verdict: Time Limit Exceeded):
import random
from collections import deque
import sys
sys.stdin.readline

class TreapNode(object):
    def __init__(self, key, data):
        self.key = key
        self.ran = random.random()
        self.size = 1
        self.cnt = 1
        self.data = data
        self.left = None
        self.right = None

    def left_rotate(self):
        a = self
        b = a.right
        a.right = b.left
        b.left = a
        a = b
        b = a.left
        b.size = b.left_size() + b.right_size() + b.cnt
        a.size = a.left_size() + a.right_size() + a.cnt
        return a

    def right_rotate(self):
        a = self
        b = a.left
        a.left = b.right
        b.right = a
        a = b
        b = a.right
        b.size = b.left_size() + b.right_size() + b.cnt
        a.size = a.left_size() + a.right_size() + a.cnt
        return a

    def left_size(self):
        return 0 if self.left is None else self.left.size

    def right_size(self):
        return 0 if self.right is None else self.right.size
    
    def __repr__(self):
        return '<node key:%s ran:%f size:%d left:%s right:%s>' % (str(self.key), self.ran, self.size, str(self.left), str(self.right))


class Treap(object):
    def __init__(self):
        self.root = None

    def _insert(self, node, key, data=None):
        if node is None:
            node = TreapNode(key, data)
            return node
        node.size += 1
        if key < node.key:
            node.left = self._insert(node.left, key, data)
            if node.left.ran < node.ran:
                node = node.right_rotate()
        elif key >= node.key:
            node.right = self._insert(node.right, key, data)
            if node.right.ran < node.ran:
                node = node.left_rotate()
        #else:
        #    node.cnt += 1
        return node

    def insert(self, key, data=None):
        self.root = self._insert(self.root, key, data)
    
    def _find(self, node, key):
        if node == None:
            return None
        if node.key == key:
            return node
        if key < node.key:
            return self._find(node.left, key)
        else:
            return self._find(node.right, key)

    def find(self, key):
        return self._find(self.root, key)

    def _delete(self, node, key):
        if node is None:
            return False
        if node.key == key:
            if node.left is None and node.right is None:
                return None
            elif node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                if node.left.ran < node.right.ran:
                    node = node.right_rotate()
                    node.right = self._delete(node.right, key)
                else:
                    node = node.left_rotate()
                    node.left = self._delete(node.left, key)
        elif key < node.key:
            node.left = self._delete(node.left, key)
        else:
            node.right = self._delete(node.right, key)
        node.size = node.left_size() + node.right_size() + node.cnt
        return node

    def delete(self, key):
        if self.find(key) is None: return False
        self.root = self._delete(self.root, key)
        return True

    def _find_kth(self, node, k):
        if node is None: return None
        if k <= node.left_size():
            return self._find_kth(node.left, k)
        if k > node.left_size() + node.cnt:
            return self._find_kth(node.right, k - node.left_size() - node.cnt)
        return node

    def find_kth(self, k):
        if k <=0 or k > self.size():
            return None
        return self._find_kth(self.root, k)

    def size(self):
        return 0 if self.root is None else self.root.size
      
      
n,p=map(int,input().split())

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
e.sort()
q = deque()
for _ in range(p):
    q.append(int(input()))
s=Treap()

for t,f,x in e:
    while t > q[0]:
        q.popleft()
        if s.size():
            print(s.find_kth(1).key)
        else:
            print(-1)
        if not q:
            sys.exit()
    if f == 1:
        s.insert(x)
    else:
        s.delete(x)
        
while q:
    q.pop()
    print(-1)


Fixed submission:
import random
from collections import deque
import sys
sys.stdin.readline

class AvlTree:  # std::set
    def __init__(self, values=None, sorted_=False, n=0):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # n: add メソッドを使う回数の最大値

        # sorted_==True であれば、初期値の数の線形時間で木を構築する
        # 値を追加するときは必ず n を設定する
        if values is None:
            self.left = [-1] * (n + 1)
            self.right = [-1] * (n + 1)
            self.values = [-float("inf")]
            self.diff = [0] * (n + 1)  # left - right
            self.size_l = [0] * (n + 1)
            self.idx_new_val = 0
        else:
            if not sorted_:
                values.sort()
            len_ = self.idx_new_val = len(values)
            n += len_
            self_left = self.left = [-1] * (n + 1)
            self_right = self.right = [-1] * (n + 1)
            self_values = self.values = [-float("inf")] + values
            self_diff = self.diff = [0] * (n + 1)  # left - right
            self_size_l = self.size_l = [0] * (n + 1)

            st = [[1, len_ + 1, 0]]
            while len(st) > 0:  # dfs っぽく木を構築
                l, r, idx_par = st.pop()  # 半開区間
                c = (l + r) >> 1  # python -> //2  pypy -> >>1
                if self_values[c] < self_values[idx_par]:
                    self_left[idx_par] = c
                else:
                    self_right[idx_par] = c
                siz = r - l
                if siz & -siz == siz != 1:  # 2 冪だったら
                    self_diff[c] = 1
                self_size_l[c] = siz_l = c - l
                if siz_l > 0:
                    st.append([l, c, c])
                    c1 = c + 1
                    if c1 < r:  # 左にノードがなければ右には必ず無いので
                        st.append([c1, r, c])

    def rotate_right(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == 2
        idx_l = self_left[idx]
        diff_l = self_diff[idx_l]

        if diff_l == -1:  # 複回転
            idx_lr = self_right[idx_l]
            diff_lr = self_diff[idx_lr]
            if diff_lr == 0:
                self_diff[idx] = 0
                self_diff[idx_l] = 0
            elif diff_lr == 1:
                self_diff[idx] = -1
                self_diff[idx_l] = 0
                self_diff[idx_lr] = 0
            else:  # diff_lr == -1
                self_diff[idx] = 0
                self_diff[idx_l] = 1
                self_diff[idx_lr] = 0

            # 部分木の大きさの計算
            self_size_l[idx_lr] += self_size_l[idx_l] + 1
            self_size_l[idx] -= self_size_l[idx_lr] + 1

            # 回転
            self_right[idx_l] = self_left[idx_lr]
            self_left[idx] = self_right[idx_lr]
            self_left[idx_lr] = idx_l
            self_right[idx_lr] = idx
            lr_container[idx_par] = idx_lr

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = 1
                nb = self_diff[idx_l] = -1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_l] = 0

            # 部分木の大きさの計算
            self_size_l[idx] -= self_size_l[idx_l] + 1

            # 回転
            self_left[idx] = self_right[idx_l]
            self_right[idx_l] = idx
            lr_container[idx_par] = idx_l

            return nb  # 新しい根の diff を返す

    def rotate_left(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == -2
        idx_r = self_right[idx]
        diff_l = self_diff[idx_r]

        if diff_l == 1:  # 複回転
            idx_rl = self_left[idx_r]
            diff_rl = self_diff[idx_rl]
            if diff_rl == 0:
                self_diff[idx] = 0
                self_diff[idx_r] = 0
            elif diff_rl == -1:
                self_diff[idx] = 1
                self_diff[idx_r] = 0
                self_diff[idx_rl] = 0
            else:  # diff_lr == 1
                self_diff[idx] = 0
                self_diff[idx_r] = -1
                self_diff[idx_rl] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] -= self_size_l[idx_rl] + 1
            self_size_l[idx_rl] += self_size_l[idx] + 1

            # 回転
            self_left[idx_r] = self_right[idx_rl]
            self_right[idx] = self_left[idx_rl]
            self_right[idx_rl] = idx_r
            self_left[idx_rl] = idx
            lr_container[idx_par] = idx_rl

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = -1
                nb = self_diff[idx_r] = 1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_r] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] += self_size_l[idx] + 1

            # 回転
            self_right[idx] = self_left[idx_r]
            self_left[idx_r] = idx
            lr_container[idx_par] = idx_r

            return nb  # 新しい根の diff を返す

    def add(self, x):  # insert
        # x を加える
        # x が既に入ってる場合は False を、
        # そうでなければ True を返す

        idx = 0
        path = []
        path_left = []

        self_values = self.values
        self_left = self.left
        self_right = self.right

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if x < value:
                path_left.append(idx)  # 重複を許さないので処理を後にする必要がある
                idx = self_left[idx]
            elif value < x:
                idx = self_right[idx]
            else:  # x == value
                return False  # 重複を許さない

        self.idx_new_val += 1
        self_diff = self.diff
        self_size_l = self.size_l

        idx = path[-1]
        if x < value:
            self_left[idx] = self.idx_new_val
        else:
            self_right[idx] = self.idx_new_val

        self_values.append(x)

        for idx_ in path_left:
            self_size_l[idx_] += 1

        self_diff[idx] += 1 if x < value else -1
        for idx_par in path[-2::-1]:
            diff = self_diff[idx]
            if diff == 0:
                return True
            elif diff == 2:  # 右回転
                self.rotate_right(idx_par, self_right[idx_par] == idx)
                return True
            elif diff == -2:  # 左回転
                self.rotate_left(idx_par, self_right[idx_par] == idx)
                return True
            else:
                self_diff[idx_par] += 1 if self_left[idx_par] == idx else -1
            idx = idx_par
        return True

    def remove(self, x):  # erase
        # x を削除する
        # x の存在が保証されている必要がある

        idx = 0
        path = []
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if value < x:
                idx = self_right[idx]
            elif x < value:
                self_size_l[idx] -= 1  # 値の存在を保証しているので
                idx = self_left[idx]
            else:  # x == value
                idx_x = idx
                self_size_l[idx] -= 1
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return True
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return True
            else:
                return True
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return True

    def pop(self, idx_):
        # 小さい方から idx_ 番目の要素を削除してその要素を返す（0-indexed）
        # idx_ 番目の値の存在が保証されている必要がある

        path = [0]
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            path.append(idx)
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                self_size_l[idx] -= 1  # 値の存在が保証されているので
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:
                idx_x = idx
                x = self_values[idx]
                self_size_l[idx] -= 1  # なんで？
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return x
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return x
            else:
                return x
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return x

    def __getitem__(self, idx_):
        # 小さい方から idx_ 番目の要素を返す

        self_left = self.left
        self_right = self.right
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:  # c == idx_
                return self.values[idx]
        raise IndexError

    def __contains__(self, x):  # count
        # 値 x があるか

        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:
                return True  # res + self_size_l[idx]
        return False

    def bisect_left(self, x):  # lower_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x
                return res + self_size_l[idx]
        return res

    def bisect_right(self, x):  # upper_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x:
                return res + self_size_l[idx] + 1
        return res

    def print_tree(self, idx=0, depth=0, from_="・"):
        if idx == 0:
            idx = self.right[idx]
        if idx == -1:
            return
        self.print_tree(self.left[idx], depth + 1, "┏")
        print("\t\t" * depth + from_ + " val=[" + str(self.values[idx]) +
              "] diff=[" + str(self.diff[idx]) +
              "] size_l=[" + str(self.size_l[idx]) + "]")
        self.print_tree(self.right[idx], depth + 1, "┗")

    
def main():
  n,p=map(int,sys.stdin.buffer.readline().split())

  e=[]
  for _ in range(n):
      s,t,x = map(int,sys.stdin.buffer.readline().split())
      e.append((s-x,1,x))
      e.append((t-x,-1,x))
  e.sort()
  q = deque()
  for _ in range(p):
      q.append(int(input()))
  s=AvlTree(n=len(e))

  for t,f,x in e:
      while t > q[0]:
          q.popleft()
          try:
              print(s[0])
          except IndexError:
              print(-1)
          if not q:
              sys.exit()
      if f == 1:
          s.add(x)
      else:
          s.remove(x)

  while q:
      q.pop()
      print(-1)

main()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
sys.stdin.readline

def main():
  n,p=map(int,input().split())

  e=[]
  for _ in range(n):
      s,t,x = map(int,input().split())
      e.append((s-x,1,x))
      e.append((t-x,-1,x))
  e.sort()
  q = deque()
  for _ in range(p):
      q.append(int(input()))
  s=set()

  for t,f,x in e:
      while t > q[0]:
          q.popleft()
          if s:
              print(min(s))
          else:
              print(-1)
          if not q:
              sys.exit()
      if f == 1:
          s.add(x)
      else:
          s.remove(x)

  while q:
      q.pop()
      print(-1)

main()

Fixed submission:
import random
from collections import deque
import sys
sys.stdin.readline

class AvlTree:  # std::set
    def __init__(self, values=None, sorted_=False, n=0):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # n: add メソッドを使う回数の最大値

        # sorted_==True であれば、初期値の数の線形時間で木を構築する
        # 値を追加するときは必ず n を設定する
        if values is None:
            self.left = [-1] * (n + 1)
            self.right = [-1] * (n + 1)
            self.values = [-float("inf")]
            self.diff = [0] * (n + 1)  # left - right
            self.size_l = [0] * (n + 1)
            self.idx_new_val = 0
        else:
            if not sorted_:
                values.sort()
            len_ = self.idx_new_val = len(values)
            n += len_
            self_left = self.left = [-1] * (n + 1)
            self_right = self.right = [-1] * (n + 1)
            self_values = self.values = [-float("inf")] + values
            self_diff = self.diff = [0] * (n + 1)  # left - right
            self_size_l = self.size_l = [0] * (n + 1)

            st = [[1, len_ + 1, 0]]
            while len(st) > 0:  # dfs っぽく木を構築
                l, r, idx_par = st.pop()  # 半開区間
                c = (l + r) >> 1  # python -> //2  pypy -> >>1
                if self_values[c] < self_values[idx_par]:
                    self_left[idx_par] = c
                else:
                    self_right[idx_par] = c
                siz = r - l
                if siz & -siz == siz != 1:  # 2 冪だったら
                    self_diff[c] = 1
                self_size_l[c] = siz_l = c - l
                if siz_l > 0:
                    st.append([l, c, c])
                    c1 = c + 1
                    if c1 < r:  # 左にノードがなければ右には必ず無いので
                        st.append([c1, r, c])

    def rotate_right(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == 2
        idx_l = self_left[idx]
        diff_l = self_diff[idx_l]

        if diff_l == -1:  # 複回転
            idx_lr = self_right[idx_l]
            diff_lr = self_diff[idx_lr]
            if diff_lr == 0:
                self_diff[idx] = 0
                self_diff[idx_l] = 0
            elif diff_lr == 1:
                self_diff[idx] = -1
                self_diff[idx_l] = 0
                self_diff[idx_lr] = 0
            else:  # diff_lr == -1
                self_diff[idx] = 0
                self_diff[idx_l] = 1
                self_diff[idx_lr] = 0

            # 部分木の大きさの計算
            self_size_l[idx_lr] += self_size_l[idx_l] + 1
            self_size_l[idx] -= self_size_l[idx_lr] + 1

            # 回転
            self_right[idx_l] = self_left[idx_lr]
            self_left[idx] = self_right[idx_lr]
            self_left[idx_lr] = idx_l
            self_right[idx_lr] = idx
            lr_container[idx_par] = idx_lr

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = 1
                nb = self_diff[idx_l] = -1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_l] = 0

            # 部分木の大きさの計算
            self_size_l[idx] -= self_size_l[idx_l] + 1

            # 回転
            self_left[idx] = self_right[idx_l]
            self_right[idx_l] = idx
            lr_container[idx_par] = idx_l

            return nb  # 新しい根の diff を返す

    def rotate_left(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == -2
        idx_r = self_right[idx]
        diff_l = self_diff[idx_r]

        if diff_l == 1:  # 複回転
            idx_rl = self_left[idx_r]
            diff_rl = self_diff[idx_rl]
            if diff_rl == 0:
                self_diff[idx] = 0
                self_diff[idx_r] = 0
            elif diff_rl == -1:
                self_diff[idx] = 1
                self_diff[idx_r] = 0
                self_diff[idx_rl] = 0
            else:  # diff_lr == 1
                self_diff[idx] = 0
                self_diff[idx_r] = -1
                self_diff[idx_rl] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] -= self_size_l[idx_rl] + 1
            self_size_l[idx_rl] += self_size_l[idx] + 1

            # 回転
            self_left[idx_r] = self_right[idx_rl]
            self_right[idx] = self_left[idx_rl]
            self_right[idx_rl] = idx_r
            self_left[idx_rl] = idx
            lr_container[idx_par] = idx_rl

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = -1
                nb = self_diff[idx_r] = 1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_r] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] += self_size_l[idx] + 1

            # 回転
            self_right[idx] = self_left[idx_r]
            self_left[idx_r] = idx
            lr_container[idx_par] = idx_r

            return nb  # 新しい根の diff を返す

    def add(self, x):  # insert
        # x を加える
        # x が既に入ってる場合は False を、
        # そうでなければ True を返す

        idx = 0
        path = []
        path_left = []

        self_values = self.values
        self_left = self.left
        self_right = self.right

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if x < value:
                path_left.append(idx)  # 重複を許さないので処理を後にする必要がある
                idx = self_left[idx]
            elif value < x:
                idx = self_right[idx]
            else:  # x == value
                return False  # 重複を許さない

        self.idx_new_val += 1
        self_diff = self.diff
        self_size_l = self.size_l

        idx = path[-1]
        if x < value:
            self_left[idx] = self.idx_new_val
        else:
            self_right[idx] = self.idx_new_val

        self_values.append(x)

        for idx_ in path_left:
            self_size_l[idx_] += 1

        self_diff[idx] += 1 if x < value else -1
        for idx_par in path[-2::-1]:
            diff = self_diff[idx]
            if diff == 0:
                return True
            elif diff == 2:  # 右回転
                self.rotate_right(idx_par, self_right[idx_par] == idx)
                return True
            elif diff == -2:  # 左回転
                self.rotate_left(idx_par, self_right[idx_par] == idx)
                return True
            else:
                self_diff[idx_par] += 1 if self_left[idx_par] == idx else -1
            idx = idx_par
        return True

    def remove(self, x):  # erase
        # x を削除する
        # x の存在が保証されている必要がある

        idx = 0
        path = []
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if value < x:
                idx = self_right[idx]
            elif x < value:
                self_size_l[idx] -= 1  # 値の存在を保証しているので
                idx = self_left[idx]
            else:  # x == value
                idx_x = idx
                self_size_l[idx] -= 1
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return True
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return True
            else:
                return True
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return True

    def pop(self, idx_):
        # 小さい方から idx_ 番目の要素を削除してその要素を返す（0-indexed）
        # idx_ 番目の値の存在が保証されている必要がある

        path = [0]
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            path.append(idx)
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                self_size_l[idx] -= 1  # 値の存在が保証されているので
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:
                idx_x = idx
                x = self_values[idx]
                self_size_l[idx] -= 1  # なんで？
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return x
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return x
            else:
                return x
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return x

    def __getitem__(self, idx_):
        # 小さい方から idx_ 番目の要素を返す

        self_left = self.left
        self_right = self.right
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:  # c == idx_
                return self.values[idx]
        raise IndexError

    def __contains__(self, x):  # count
        # 値 x があるか

        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:
                return True  # res + self_size_l[idx]
        return False

    def bisect_left(self, x):  # lower_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x
                return res + self_size_l[idx]
        return res

    def bisect_right(self, x):  # upper_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x:
                return res + self_size_l[idx] + 1
        return res

    def print_tree(self, idx=0, depth=0, from_="・"):
        if idx == 0:
            idx = self.right[idx]
        if idx == -1:
            return
        self.print_tree(self.left[idx], depth + 1, "┏")
        print("\t\t" * depth + from_ + " val=[" + str(self.values[idx]) +
              "] diff=[" + str(self.diff[idx]) +
              "] size_l=[" + str(self.size_l[idx]) + "]")
        self.print_tree(self.right[idx], depth + 1, "┗")

    
def main():
  n,p=map(int,sys.stdin.buffer.readline().split())

  e=[]
  for _ in range(n):
      s,t,x = map(int,sys.stdin.buffer.readline().split())
      e.append((s-x,1,x))
      e.append((t-x,-1,x))
  e.sort()
  q = deque()
  for _ in range(p):
      q.append(int(input()))
  s=AvlTree(n=len(e))

  for t,f,x in e:
      while t > q[0]:
          q.popleft()
          try:
              print(s[0])
          except IndexError:
              print(-1)
          if not q:
              sys.exit()
      if f == 1:
          s.add(x)
      else:
          s.remove(x)

  while q:
      q.pop()
      print(-1)

main()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
sys.stdin.readline
n,p=map(int,input().split())

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
e.sort()
q = deque()
for _ in range(p):
    q.append(int(input()))
s=set()

for t,f,x in e:
    while t > q[0]:
        q.popleft()
        if s:
            print(min(s))
        else:
            print(-1)
        if not q:
            sys.exit()
    if f == 1:
        s.add(x)
    else:
        s.remove(x)
        
while q:
    q.pop()
    print(-1)


Fixed submission:
import random
from collections import deque
import sys
sys.stdin.readline

class AvlTree:  # std::set
    def __init__(self, values=None, sorted_=False, n=0):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # n: add メソッドを使う回数の最大値

        # sorted_==True であれば、初期値の数の線形時間で木を構築する
        # 値を追加するときは必ず n を設定する
        if values is None:
            self.left = [-1] * (n + 1)
            self.right = [-1] * (n + 1)
            self.values = [-float("inf")]
            self.diff = [0] * (n + 1)  # left - right
            self.size_l = [0] * (n + 1)
            self.idx_new_val = 0
        else:
            if not sorted_:
                values.sort()
            len_ = self.idx_new_val = len(values)
            n += len_
            self_left = self.left = [-1] * (n + 1)
            self_right = self.right = [-1] * (n + 1)
            self_values = self.values = [-float("inf")] + values
            self_diff = self.diff = [0] * (n + 1)  # left - right
            self_size_l = self.size_l = [0] * (n + 1)

            st = [[1, len_ + 1, 0]]
            while len(st) > 0:  # dfs っぽく木を構築
                l, r, idx_par = st.pop()  # 半開区間
                c = (l + r) >> 1  # python -> //2  pypy -> >>1
                if self_values[c] < self_values[idx_par]:
                    self_left[idx_par] = c
                else:
                    self_right[idx_par] = c
                siz = r - l
                if siz & -siz == siz != 1:  # 2 冪だったら
                    self_diff[c] = 1
                self_size_l[c] = siz_l = c - l
                if siz_l > 0:
                    st.append([l, c, c])
                    c1 = c + 1
                    if c1 < r:  # 左にノードがなければ右には必ず無いので
                        st.append([c1, r, c])

    def rotate_right(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == 2
        idx_l = self_left[idx]
        diff_l = self_diff[idx_l]

        if diff_l == -1:  # 複回転
            idx_lr = self_right[idx_l]
            diff_lr = self_diff[idx_lr]
            if diff_lr == 0:
                self_diff[idx] = 0
                self_diff[idx_l] = 0
            elif diff_lr == 1:
                self_diff[idx] = -1
                self_diff[idx_l] = 0
                self_diff[idx_lr] = 0
            else:  # diff_lr == -1
                self_diff[idx] = 0
                self_diff[idx_l] = 1
                self_diff[idx_lr] = 0

            # 部分木の大きさの計算
            self_size_l[idx_lr] += self_size_l[idx_l] + 1
            self_size_l[idx] -= self_size_l[idx_lr] + 1

            # 回転
            self_right[idx_l] = self_left[idx_lr]
            self_left[idx] = self_right[idx_lr]
            self_left[idx_lr] = idx_l
            self_right[idx_lr] = idx
            lr_container[idx_par] = idx_lr

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = 1
                nb = self_diff[idx_l] = -1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_l] = 0

            # 部分木の大きさの計算
            self_size_l[idx] -= self_size_l[idx_l] + 1

            # 回転
            self_left[idx] = self_right[idx_l]
            self_right[idx_l] = idx
            lr_container[idx_par] = idx_l

            return nb  # 新しい根の diff を返す

    def rotate_left(self, idx_par, lr):  # lr: 親の左なら 0
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        lr_container = self_right if lr else self_left
        idx = lr_container[idx_par]
        #assert self_diff[idx] == -2
        idx_r = self_right[idx]
        diff_l = self_diff[idx_r]

        if diff_l == 1:  # 複回転
            idx_rl = self_left[idx_r]
            diff_rl = self_diff[idx_rl]
            if diff_rl == 0:
                self_diff[idx] = 0
                self_diff[idx_r] = 0
            elif diff_rl == -1:
                self_diff[idx] = 1
                self_diff[idx_r] = 0
                self_diff[idx_rl] = 0
            else:  # diff_lr == 1
                self_diff[idx] = 0
                self_diff[idx_r] = -1
                self_diff[idx_rl] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] -= self_size_l[idx_rl] + 1
            self_size_l[idx_rl] += self_size_l[idx] + 1

            # 回転
            self_left[idx_r] = self_right[idx_rl]
            self_right[idx] = self_left[idx_rl]
            self_right[idx_rl] = idx_r
            self_left[idx_rl] = idx
            lr_container[idx_par] = idx_rl

            return 0

        else:  # 単回転
            if diff_l == 0:
                self_diff[idx] = -1
                nb = self_diff[idx_r] = 1
            else:  # diff_l == 1
                self_diff[idx] = 0
                nb = self_diff[idx_r] = 0

            # 部分木の大きさの計算
            self_size_l[idx_r] += self_size_l[idx] + 1

            # 回転
            self_right[idx] = self_left[idx_r]
            self_left[idx_r] = idx
            lr_container[idx_par] = idx_r

            return nb  # 新しい根の diff を返す

    def add(self, x):  # insert
        # x を加える
        # x が既に入ってる場合は False を、
        # そうでなければ True を返す

        idx = 0
        path = []
        path_left = []

        self_values = self.values
        self_left = self.left
        self_right = self.right

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if x < value:
                path_left.append(idx)  # 重複を許さないので処理を後にする必要がある
                idx = self_left[idx]
            elif value < x:
                idx = self_right[idx]
            else:  # x == value
                return False  # 重複を許さない

        self.idx_new_val += 1
        self_diff = self.diff
        self_size_l = self.size_l

        idx = path[-1]
        if x < value:
            self_left[idx] = self.idx_new_val
        else:
            self_right[idx] = self.idx_new_val

        self_values.append(x)

        for idx_ in path_left:
            self_size_l[idx_] += 1

        self_diff[idx] += 1 if x < value else -1
        for idx_par in path[-2::-1]:
            diff = self_diff[idx]
            if diff == 0:
                return True
            elif diff == 2:  # 右回転
                self.rotate_right(idx_par, self_right[idx_par] == idx)
                return True
            elif diff == -2:  # 左回転
                self.rotate_left(idx_par, self_right[idx_par] == idx)
                return True
            else:
                self_diff[idx_par] += 1 if self_left[idx_par] == idx else -1
            idx = idx_par
        return True

    def remove(self, x):  # erase
        # x を削除する
        # x の存在が保証されている必要がある

        idx = 0
        path = []
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        while idx != -1:
            path.append(idx)
            value = self_values[idx]
            if value < x:
                idx = self_right[idx]
            elif x < value:
                self_size_l[idx] -= 1  # 値の存在を保証しているので
                idx = self_left[idx]
            else:  # x == value
                idx_x = idx
                self_size_l[idx] -= 1
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return True
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return True
            else:
                return True
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return True

    def pop(self, idx_):
        # 小さい方から idx_ 番目の要素を削除してその要素を返す（0-indexed）
        # idx_ 番目の値の存在が保証されている必要がある

        path = [0]
        idx_x = -1

        self_values = self.values
        self_left = self.left
        self_right = self.right
        self_diff = self.diff
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            path.append(idx)
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                self_size_l[idx] -= 1  # 値の存在が保証されているので
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:
                idx_x = idx
                x = self_values[idx]
                self_size_l[idx] -= 1  # なんで？
                idx = self_left[idx]

        idx_last_par, idx_last = path[-2:]

        if idx_last == idx_x:  # x に左の子が存在しない
            # 親の idx を付け替える
            if self_left[idx_last_par] == idx_x:
                self_left[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] -= 1
            else:
                self_right[idx_last_par] = self_right[idx_x]
                self_diff[idx_last_par] += 1
        else:  # x に左の子が存在する
            # 自身の value を付け替える
            self_values[idx_x] = self_values[idx_last]
            if idx_last_par == idx_x:  # x 左 idx_last (左 _)?
                self_left[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] -= 1
            else:  # x 左 _ 右 ... 右 idx_last (左 _)?
                self_right[idx_last_par] = self_left[idx_last]
                self_diff[idx_last_par] += 1

        self_rotate_left = self.rotate_left
        self_rotate_right = self.rotate_right
        diff = self_diff[idx_last_par]
        idx = idx_last_par
        for idx_par in path[-3::-1]:
            # assert diff == self_diff[idx]
            lr = self_right[idx_par] == idx
            if diff == 0:
                pass
            elif diff == 2:  # 右回転
                diff_ = self_rotate_right(idx_par, lr)
                if diff_ != 0:
                    return x
            elif diff == -2:  # 左回転
                diff_ = self_rotate_left(idx_par, lr)
                if diff_ != 0:
                    return x
            else:
                return x
            diff = self_diff[idx_par] = self_diff[idx_par] + (1 if lr else -1)
            idx = idx_par
        return x

    def __getitem__(self, idx_):
        # 小さい方から idx_ 番目の要素を返す

        self_left = self.left
        self_right = self.right
        self_size_l = self.size_l

        sum_left = 0
        idx = self_right[0]
        while idx != -1:
            c = sum_left + self_size_l[idx]
            if idx_ < c:
                idx = self_left[idx]
            elif c < idx_:
                idx = self_right[idx]
                sum_left = c + 1
            else:  # c == idx_
                return self.values[idx]
        raise IndexError

    def __contains__(self, x):  # count
        # 値 x があるか

        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:
                return True  # res + self_size_l[idx]
        return False

    def bisect_left(self, x):  # lower_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x
                return res + self_size_l[idx]
        return res

    def bisect_right(self, x):  # upper_bound
        self_left = self.left
        self_right = self.right
        self_values = self.values
        self_size_l = self.size_l

        idx = self_right[0]
        res = 0
        while idx != -1:
            value = self_values[idx]
            if value < x:
                res += self_size_l[idx] + 1
                idx = self_right[idx]
            elif x < value:
                idx = self_left[idx]
            else:  # value == x:
                return res + self_size_l[idx] + 1
        return res

    def print_tree(self, idx=0, depth=0, from_="・"):
        if idx == 0:
            idx = self.right[idx]
        if idx == -1:
            return
        self.print_tree(self.left[idx], depth + 1, "┏")
        print("\t\t" * depth + from_ + " val=[" + str(self.values[idx]) +
              "] diff=[" + str(self.diff[idx]) +
              "] size_l=[" + str(self.size_l[idx]) + "]")
        self.print_tree(self.right[idx], depth + 1, "┗")

    
def main():
  n,p=map(int,sys.stdin.buffer.readline().split())

  e=[]
  for _ in range(n):
      s,t,x = map(int,sys.stdin.buffer.readline().split())
      e.append((s-x,1,x))
      e.append((t-x,-1,x))
  e.sort()
  q = deque()
  for _ in range(p):
      q.append(int(input()))
  s=AvlTree(n=len(e))

  for t,f,x in e:
      while t > q[0]:
          q.popleft()
          try:
              print(s[0])
          except IndexError:
              print(-1)
          if not q:
              sys.exit()
      if f == 1:
          s.add(x)
      else:
          s.remove(x)

  while q:
      q.pop()
      print(-1)

main()