Buggy python submission (verdict: Time Limit Exceeded):
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)

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

    def getmin(self):
        t = self.root
        while t is not None:
            ans = t.key
            t = t.lst
        return ans

    # マップが空なら 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())

###############################################################################
# 作業メソッド
###############################################################################

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)

mx = 10**9 + 1

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, q = map(int, input().split())
event = []
for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s - x - 0.5, 1, x))
    event.append((t - x - 0.5, -1, x))
for i in range(q):
    event.append((int(input()), 0, i))

event.sort()

# stop = set()
stop = AVLMap()
ans = {}
for t, e, x in event:
    if e > 0:
        stop.insert(x, 0)
    elif e < 0:
        stop.delete(x)
    else:
        if stop.size() != 0:
            ans[x] = stop.getmin()
        else:
            ans[x] = -1
for i in range(q):
    print(ans[i])


Fixed submission:
import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

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

Buggy python submission (verdict: Time Limit Exceeded):
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)

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

    def getmin(self):
        t = self.root
        while t is not None:
            ans = t.key
            t = t.lst
        return ans

    # マップが空なら 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())

###############################################################################
# 作業メソッド
###############################################################################

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)

mx = 10**9 + 1

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, q = map(int, input().split())
event = []
for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s - x - 0.5, 1, x))
    event.append((t - x - 0.5, -1, x))
for i in range(q):
    event.append((int(input()), 0, i))

event.sort()

# stop = set()
stop = AVLMap()
ans = {}
for t, e, x in event:
    if e > 0:
        stop.insert(x, 0)
    elif e < 0:
        stop.delete(x)
    else:
        if stop.size() != 0:
            ans[x] = stop.getmin()
        else:
            ans[x] = -1
for i in range(q):
    print(ans[i])


Fixed submission:
import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, q = map(int, input().split())
event = []
for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s - x - 0.5, 1, x))
    event.append((t - x - 0.5, -1, x))
for i in range(q):
    event.append((int(input()), 0, i))

event.sort()

stop = set()

ans = {}
for t, e, x in event:
    if e > 0:
        stop.add(x)
    elif e < 0:
        stop.remove(x)
    else:
        if len(stop) != 0:
            ans[x] = min(stop)
        else:
            ans[x] = -1

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


Fixed submission:
import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

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

Buggy python submission (verdict: Time Limit Exceeded):
import random


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

    def median(self):
        s = self.size()
        if s == 0: return 0
        result = 0
        if s % 2 == 1:
            result = self.find_kth(s / 2 + 1).key
        else:
            result = (self.find_kth(s / 2).key + self.find_kth(s / 2 + 1).key) / 2.0
        if result == int(result): result = int(result)
        return result

    def _traverse(self, node):
        if node == None: return
        self._traverse(node.left)
        self._traverse(node.right)

    def traverse(self):
        self._traverse(self.root)

    def __repr__(self):
        return str(self.root)

import sys
sys.setrecursionlimit(10**7)
n, q = map(int, input().split())
event = []
for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s - x - 0.5, 1, x))
    event.append((t - x - 0.5, -1, x))
for i in range(q):
    event.append((int(input()), 0, i))

event.sort()

stop = Treap()

ans = {}
for t, e, x in event:
    if e > 0:
        stop.insert(x)
    elif e < 0:
        stop.delete(x)
    else:
        if stop.root is not None:
            ans[x] = stop.find_kth(1).key
        else:
            ans[x] = -1

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


Fixed submission:
import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

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

Buggy python submission (verdict: Time Limit Exceeded):
import random


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

    def median(self):
        s = self.size()
        if s == 0: return 0
        result = 0
        if s % 2 == 1:
            result = self.find_kth(s / 2 + 1).key
        else:
            result = (self.find_kth(s / 2).key + self.find_kth(s / 2 + 1).key) / 2.0
        if result == int(result): result = int(result)
        return result

    def _traverse(self, node):
        if node == None: return
        self._traverse(node.left)
        self._traverse(node.right)

    def traverse(self):
        self._traverse(self.root)

    def __repr__(self):
        return str(self.root)

import sys
sys.setrecursionlimit(10**7)
n, q = map(int, input().split())
event = []
for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s - x - 0.5, 1, x))
    event.append((t - x - 0.5, -1, x))
for i in range(q):
    event.append((int(input()), 0, i))

event.sort()

stop = Treap()

ans = {}
for t, e, x in event:
    if e > 0:
        stop.insert(x)
    elif e < 0:
        stop.delete(x)
    else:
        if stop.root is not None:
            ans[x] = stop.find_kth(1).key
        else:
            ans[x] = -1

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


Fixed submission:
import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

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

Buggy python submission (verdict: Time Limit Exceeded):
import queue


class Node(object):
    """docstring for Node"""

    def __init__(self, data=None):
        super(Node, self).__init__()
        self.data = data
        self.left = None
        self.right = None


class BST(object):
    """docstring for BST"""

    def __init__(self):
        super(BST, self).__init__()
        self.root = None

    '''Inorder Traversal'''

    def inorder(self, root):
        res = []
        if root:
            res = self.inorder(root.left)
            res.append(root.data)
            res = res + self.inorder(root.right)
        return res

    '''Finding an element in BST'''

    def find(self, data):
        if self.root is None:
            return 0
        curr = self.root
        while curr:
            if data == curr.data:
                return 1
            elif data < curr.data:
                curr = curr.left
            else:
                curr = curr.right
        return 0

    '''Finding min element in BST'''

    def findMin(self, root):
        if root is None:
            return 0
        root = self.root
        while root.left is not None:
            root = root.left
        return root.data

    '''Finding max element in BST'''

    def findMax(self, root):
        if root == None:
            return 0
        while root.right is not None:
            root = root.right
        return root.data

    '''Inserting an element in BST'''

    def insert(self, root, data):
        if root == None:
            root = Node(data)
        else:
            if data < root.data:
                root.left = self.insert(root.left, data)
            else:
                root.right = self.insert(root.right, data)
        return root

    '''Deleting an element in BST'''

    def delete(self, root, data):
        if root == None:
            return None
        elif data < root.data:
            root.left = self.delete(root.left, data)
        elif data > root.data:
            root.right = self.delete(root.right, data)
        else:
            # Node has two children
            if (root.left is not None) and (root.right is not None):
                temp = self.findMax(root.left)
                root.data = temp
                root.left = self.delete(root.left, root.data)
            else:
                if root.left:  # only left child
                    root = root.left
                elif root.right:  # only right child
                    root = root.right
                else:  # no child
                    root = None
        return root


n, q = map(int, input().split())
event = []
for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s - x - 0.5, 1, x))
    event.append((t - x - 0.5, -1, x))
for i in range(q):
    event.append((int(input()), 0, i))

event.sort()

stop = BST()

ans = {}
for t, e, x in event:
    if e > 0:
        stop.root = stop.insert(stop.root, x)
    elif e < 0:
        stop.root = stop.delete(stop.root, x)
    else:
        if stop.root is not None:
            ans[x] = stop.findMin(stop.root)
        else:
            ans[x] = -1

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


Fixed submission:
import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

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

Buggy python submission (verdict: Time Limit Exceeded):
import sys;input=sys.stdin.readline

n, q = map(int, input().split())
event = []
for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s-x-0.5, 1, x))
    event.append((t-x-0.5, -1, x))
for i in range(q):
    event.append((int(input()), 0, i))

event.sort()
stop = set()
ans = []
idx = []

for t,e,x in event:
    if e > 0:
        stop.add(x)
    elif e < 0:
        stop.remove(x)
    else:
        idx.append(x)
        if len(stop) > 0:
            ans.append(min(stop))
        else:
            ans.append(-1)

import numpy as np
ans = np.array(ans)[idx]
for i in range(q):
    print(ans[i])

Fixed submission:
import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

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

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)

debug = True
#debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

class Event:
    def __repr__(self):
            return str(self.__dict__)

class User:
    def __repr__(self):
            return str(self.__dict__)

def solve():
    n, q = map(int, input().split())
    l_event = []
    for i in range(n):
        s, t, x = map(int, input().split())

        # 追加イベント
        e = Event()
        e.time = s-x
        e.type = 1 # add
        e.pos = x
        l_event.append(e)

        # 削除イベント
        e = Event()
        e.time = t-x
        e.type = -1 # delete
        e.pos = x
        l_event.append(e)

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

        # ユーザ評価イベント
        u = User()
        u.time = d + 0.5 # ユーザが出発する時刻までのイベントを先に処理したいので、0.5ずらす
        u.idx = i
        l_user.append(u)

    # リストを時刻でソート O(NlogN)
    l_event = sorted(l_event, key=lambda e: e.time)

    # ユーザも時刻でソート O(QlogQ)
    l_user = sorted(l_user, key=lambda e: e.time)


    ans = []
    s_stop = set()
    current_user_idx = 0

    # リストを順に処理する 全体 O(N + Qlog(2N))
    for e in l_event: # 中身が O(1) なら O(N)

        # 次処理するイベントの時刻より前のユーザをすべて処理する
        while(True): # この while 文は最大Q回しか回らないので、全体 O(Qlog(2N))
            u = l_user[current_user_idx]
            if u.time < e.time:
                if len(s_stop) != 0:
                    ans.append(min(s_stop))
                else:
                    ans.append(-1)

                current_user_idx += 1 # 次のユーザへ
                if current_user_idx >= q:  # 人の処理が終わっている場合、終わり
                    break
            else:
                # 次のイベントを処理
                break

        if e.type == 1: # add
            s_stop.add(e.pos)
        else: # delete
            s_stop.remove(e.pos)

    ans += [-1] * (q - current_user_idx)

    import numpy as np
    arg = [u.idx for u in l_user]
    ans = np.array(ans)[arg]
    for i in range(q):
        print(ans[i])

solve()

Fixed submission:
import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

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

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)

debug = True
#debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

class Event:
    def __repr__(self):
            return str(self.__dict__)

class User:
    def __repr__(self):
            return str(self.__dict__)

def solve():
    n, q = map(int, input().split())
    l_event = []
    for i in range(n):
        s, t, x = map(int, input().split())

        # 追加イベント
        e = Event()
        e.time = s-x
        e.type = 1 # add
        e.pos = x
        l_event.append(e)

        # 削除イベント
        e = Event()
        e.time = t-x
        e.type = -1 # delete
        e.pos = x
        l_event.append(e)

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

        # ユーザ評価イベント
        u = User()
        u.time = d + 0.5 # ユーザが出発する時刻までのイベントを先に処理したいので、0.5ずらす
        u.idx = i
        l_user.append(u)

    # リストを時刻でソート O(NlogN)
    l_event = sorted(l_event, key=lambda e: e.time)

    # ユーザも時刻でソート O(QlogQ)
    l_user = sorted(l_user, key=lambda e: e.time)


    ans = {i:-1 for i in range(q)} # 答えの配列
    s_stop = set()
    current_user_idx = 0

    # リストを順に処理する 全体 O(N + Qlog(2N))
    for e in l_event: # 中身が O(1) なら O(N)

        # 次処理するイベントの時刻より前のユーザをすべて処理する
        while(True): # この while 文は最大Q回しか回らないので、全体 O(Qlog(2N))
            u = l_user[current_user_idx]
            if u.time < e.time:
                if len(s_stop) != 0:
                    ans[u.idx] = min(s_stop)

                current_user_idx += 1 # 次のユーザへ
                if current_user_idx >= len(l_user):  # 人の処理が終わっている場合、終わり
                    break
            else:
                break

        if e.type == 1: # add
            s_stop.add(e.pos)
        else: # delete
            s_stop.remove(e.pos)

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

solve()

Fixed submission:
import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

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

Buggy python submission (verdict: Time Limit Exceeded):
import sys;input=sys.stdin.readline

n, q = map(int, input().split())
event = []
for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s-x-0.5, 1, x))
    event.append((t-x-0.5, -1, x))
for i in range(q):
    event.append((int(input()), 0, i))

event.sort()
stop = set()
ans={}
for t,e,x in event:
    if e > 0:
        stop.add(x)
    elif e < 0:
        stop.remove(x)
    else:
        if len(stop) > 0:
            ans[x] = min(stop)
        else:
            ans[x] = -1

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

Fixed submission:
import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

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

Buggy python submission (verdict: Time Limit Exceeded):
import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
stop=set()
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
    elif e<0:
        stop.remove(x)
    elif len(stop)>0:
        ans[x]=min(stop)

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

Fixed submission:
import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)

debug = True
#debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

class Event:
    def __repr__(self):
            return str(self.__dict__)

def solve():
    n, q = map(int, input().split())
    l_event = []
    for i in range(n):
        s, t, x = map(int, input().split())

        # 追加イベント
        e = Event()
        e.time = s-x
        e.type = 1 # add
        e.pos = x
        l_event.append(e)

        # 削除イベント
        e = Event()
        e.time = t-x
        e.type = -1 # delete
        e.pos = x
        l_event.append(e)

    for i in range(q):
        d = int(input())

        # ユーザ評価イベント
        e = Event()
        e.time = d + 0.5 # ユーザが出発する時刻までのイベントを先に処理したいので、0.5ずらす
        e.type = 0 # evaluate
        e.pos = None
        e.idx = i
        l_event.append(e)

    # リストを時刻でソート O((N+Q)log(N+Q))
    l_event = sorted(l_event, key=lambda e: e.time)

    ans = [-1]*q # 答えの配列
    s_stop = set()

    minstop = 10**9 + 1

    # リストを順に処理する
    for e in l_event: #O(N+Q)
        if e.type == 1: # add
            s_stop.add(e.pos)
            if e.pos < minstop:
                minstop = e.pos
        elif e.type == -1: # delete
            s_stop.remove(e.pos)
            if minstop == e.pos:
                minstop = -1 # unknown state
        else: #evaluate
            if minstop == -1 or minstop == 10**9 + 1:
                if len(s_stop) != 0:
                    minstop = min(s_stop)
                    ans[e.idx] = minstop
            else:
                ans[e.idx] = minstop

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

solve()

Fixed submission:
import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

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

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)

class Event:
    def __repr__(self):
            return str(self.__dict__)

class User:
    def __repr__(self):
            return str(self.__dict__)

def solve():
    n, q = map(int, input().split())
    l_event = []
    for i in range(n):
        s, t, x = map(int, input().split())

        # 追加イベント
        e = Event()
        e.time = s-x
        e.type = 1 # add
        e.pos = x
        l_event.append(e)

        # 削除イベント
        e = Event()
        e.time = t-x
        e.type = -1 # delete
        e.pos = x
        l_event.append(e)

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

        # ユーザ評価イベント
        u = User()
        u.time = d + 0.5 # ユーザが出発する時刻までのイベントを先に処理したいので、0.5ずらす
        u.idx = i
        l_user.append(u)

    # リストを時刻でソート O(NlogN)
    l_event = sorted(l_event, key=lambda e: e.time)

    # ユーザも時刻でソート O(QlogQ)
    l_user = sorted(l_user, key=lambda e: e.time)

    ans = [-1]*q # 答えの配列
    s_stop = set()
    minstop = 10**9 + 1

    current_user_idx = 0

    # リストを順に処理する 全体 O(N + Qlog(2N))
    for e in l_event: # 中身が O(1) なら O(N)


        # 次処理するイベントの時刻より前のユーザをすべて処理する
        while(True): # この while 文は最大Q回しか回らないので、全体 O(Qlog(2N))
            u = l_user[current_user_idx]
            if u.time < e.time:
                if len(s_stop) != 0:
                    if minstop == -1 or minstop == 10**9 + 1:
                        minstop = min(s_stop) # O(log(2N))
                    ans[u.idx] = minstop

                current_user_idx += 1 # 次のユーザへ
                if current_user_idx >= len(l_user):  # 人の処理が終わっている場合、終わり
                    break
            else:
                break

        if e.type == 1: # add
            s_stop.add(e.pos)
            if minstop > e.pos:
                e.pos = minstop # update minstop in advance

        else: # delete
            s_stop.remove(e.pos)
            if minstop == e.pos:
                minstop = -1 # unknown

    print("\n".join([str(a) for a in ans]))

solve()

Fixed submission:
import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)

debug = True
#debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

class Event:
    def __repr__(self):
            return str(self.__dict__)

class User:
    def __repr__(self):
            return str(self.__dict__)

def solve():
    n, q = map(int, input().split())
    l_event = []
    for i in range(n):
        s, t, x = map(int, input().split())

        # 追加イベント
        e = Event()
        e.time = s-x
        e.type = 1 # add
        e.pos = x
        l_event.append(e)

        # 削除イベント
        e = Event()
        e.time = t-x
        e.type = -1 # delete
        e.pos = x
        l_event.append(e)

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

        # ユーザ評価イベント
        u = User()
        u.time = d + 0.5 # ユーザが出発する時刻までのイベントを先に処理したいので、0.5ずらす
        u.idx = i
        l_user.append(u)

    # リストを時刻でソート O(NlogN)
    l_event = sorted(l_event, key=lambda e: e.time)

    # ユーザも時刻でソート O(QlogQ)
    l_user = sorted(l_user, key=lambda e: e.time)

    ans = [-1]*q # 答えの配列
    s_stop = set()

    current_user_idx = 0

    # リストを順に処理する 全体 O(N + Qlog(2N))
    for e in l_event: # 中身が O(1) なら O(N)

        # 次処理するイベントの時刻より前のユーザをすべて処理する
        while(True): # この while 文は最大Q回しか回らないので、全体 O(Qlog(2N))
            if current_user_idx >= len(l_user):
                break
            u = l_user[current_user_idx]
            if u.time < e.time:
                if len(s_stop) != 0:
                    ans[u.idx] = min(s_stop) # O(log(2N))
                current_user_idx += 1
            else:
                break

        if e.type == 1: # add
            s_stop.add(e.pos)
        else: # delete
            s_stop.remove(e.pos)

    print("\n".join([str(a) for a in ans]))

solve()

Fixed submission:
import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

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

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)

class Event:
    def __repr__(self):
            return str(self.__dict__)

class User:
    def __repr__(self):
            return str(self.__dict__)

def solve():
    n, q = map(int, input().split())
    l_event = []
    for i in range(n):
        s, t, x = map(int, input().split())

        # 追加イベント
        e = Event()
        e.time = s-x
        e.type = 1 # add
        e.pos = x
        l_event.append(e)

        # 削除イベント
        e = Event()
        e.time = t-x
        e.type = -1 # delete
        e.pos = x
        l_event.append(e)

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

        # ユーザ評価イベント
        u = User()
        u.time = d + 0.5 # ユーザが出発する時刻までのイベントを先に処理したいので、0.5ずらす
        u.idx = i
        l_user.append(u)

    # リストを時刻でソート O(NlogN)
    l_event = sorted(l_event, key=lambda e: e.time)

    # ユーザも時刻でソート O(QlogQ)
    l_user = sorted(l_user, key=lambda e: e.time)

    ans = [-1]*q # 答えの配列
    s_stop = set()

    current_user_idx = 0

    # リストを順に処理する
    for e in l_event: #O(N+Q)

        # 次処理するイベントの時刻より前のユーザをすべて処理する
        while(True):
            u = l_user[current_user_idx]
            if u.time < e.time:
                if len(s_stop) != 0:
                    ans[u.idx] = min(s_stop)
                current_user_idx += 1
            else:
                break

        if e.type == 1: # add
            s_stop.add(e.pos)
        else: # delete
            s_stop.remove(e.pos)

    print("\n".join([str(a) for a in ans]))

solve()

Fixed submission:
import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)

class Event:
    def __repr__(self):
            return str(self.__dict__)

def solve():
    n, q = map(int, input().split())
    l_event = []
    for i in range(n):
        s, t, x = map(int, input().split())

        # 追加イベント
        e = Event()
        e.time = s-x
        e.type = 1 # add
        e.pos = x
        l_event.append(e)

        # 削除イベント
        e = Event()
        e.time = t-x
        e.type = -1 # delete
        e.pos = x
        l_event.append(e)

    for i in range(q):
        d = int(input())

        # ユーザ評価イベント
        e = Event()
        e.time = d + 0.5 # ユーザが出発する時刻までのイベントを先に処理したいので、0.5ずらす
        e.type = 0 # evaluate
        e.pos = None
        e.idx = i
        l_event.append(e)

    # リストを時刻でソート O((N+Q)log(N+Q))
    l_event = sorted(l_event, key=lambda e: e.time)

    ans = [-1]*q # 答えの配列
    s_stop = set()

    # リストを順に処理する
    for e in l_event: #O(N+Q)
        if e.type == 1: # add
            s_stop.add(e.pos)
        elif e.type == -1: # delete
            s_stop.remove(e.pos)
        else: #evaluate
            if len(s_stop) != 0:
                ans[e.idx] = min(s_stop) # O(logN)
            else:
                pass

    print("\n".join([str(a) for a in ans]))

solve()

Fixed submission:
import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)
import numpy as np
# n = int(input())
# a, b = map(int, input().split())
# int_list = list(map(int, input().split()))
# l = list(input().split())

def solve():
    s_list = []
    t_list = []
    x_list = []
    d_list = []
    n, q = map(int, input().split())
    dict_x_by_d = {}
    for i in range(n):
        s, t, x = map(int, input().split())

        s_list.append(s)
        t_list.append(t)
        x_list.append(x)
        for d in range(s-x, (t-1)-x+1):
            if d in dict_x_by_d:
                dict_x_by_d[d] = min(x, dict_x_by_d[d])
            else:
                dict_x_by_d[d] = x
    for i in range(q):
        d = int(input())
        d_list.append(d)
        if d in dict_x_by_d:
            print(dict_x_by_d[d])
        else:
            print(-1)

solve()

Fixed submission:
import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

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