Buggy python submission (verdict: Time Limit Exceeded):
import sys
from math import ceil
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class VanEmdeBoasTree:
    def __init__(self, size):
        self.universe_size = 1 << size.bit_length()
        self.minimum = -1
        self.maximum = -1
        self.summary = None
        self.cluster = {}
    
    def __high(self, x):
        return x // ceil(self.universe_size ** 0.5)
    
    def __low(self, x):
        return x % ceil(self.universe_size ** 0.5)
    
    def __generate_index(self, x, y):
        return x * ceil(self.universe_size ** 0.5) + y
    
    def __empinsert(self, key):
        self.minimum = self.maximum = key
    
    def insert(self, key):
        if self.minimum == -1:
            self.minimum = self.maximum = key
        else:
            if key < self.minimum:
                self.minimum, key = key, self.minimum
            if 2 < self.universe_size:
                if self.__high(key) not in self.cluster:
                    self.cluster[self.__high(key)] = VanEmdeBoasTree(ceil(self.universe_size ** 0.5))
                    if self.summary is None:
                        self.summary = VanEmdeBoasTree(ceil(self.universe_size ** 0.5))
                    self.summary.insert(self.__high(key))
                    self.cluster[self.__high(key)].__empinsert(self.__low(key))
                else:
                    self.cluster[self.__high(key)].insert(self.__low(key))
            if self.maximum < key:
                self.maximum = key
    
    def is_member(self, key):
        if self.minimum == key or self.maximum == key:
            return True
        elif self.universe_size == 2:
            return False
        else:
            if self.__high(key) in self.cluster:
                return self.cluster[self.__high(key)].is_member(self.__low(key))
            else:
                return False
    
    def successor(self, key):
        # バグらせてるっぽい
        if self.universe_size == 2:
            if key == 0 and self.maximum == 1:
                return 1
            else:
                return -1
        elif self.minimum != -1 and key < self.minimum:
            return self.minimum
        else:
            max_incluster = -1
            if self.__high(key) in self.cluster:
                max_incluster = self.cluster[self.__high(key)].maximum
            if max_incluster != -1 and self.__low(key) < max_incluster:
                offset = self.cluster[self.__high(key)].successor(self.__low(key))
                return self.__generate_index(self.__high(key), offset)
            else:
                succ_cluster = -1
                if self.summary.successor is not None:
                    succ_cluster = self.summary.successor(self.__high(key))
                if succ_cluster == -1:
                    return -1
                else:
                    offset = self.cluster[succ_cluster].minimum
                    return self.__generate_index(succ_cluster, offset)
    
    def predecessor(self, key):
        if self.universe_size == 2:
            if key == 1 and self.minimum == 0:
                return 0
            else:
                return -1
        elif self.maximum != -1 and self.maximum < key:
            return self.maximum
        else:
            min_incluster = -1
            if self.__high(key) in self.cluster:
                min_incluster = self.cluster[self.__high(key)].minimum
            if min_incluster != -1 and min_incluster < self.__low(key):
                offset = self.cluster[self.__high(key)].predecessor(self.__low(key))
                return self.__generate_index(self.__high(key), offset)
            else:
                pred_cluster = -1
                if self.summary is not None:
                    pred_cluster = self.summary.predecessor(self.__high(key))
                if pred_cluster == -1:
                    if self.minimum != -1 and self.minimum < key:
                        return self.minimum
                    else:
                        return -1
                else:
                    offset = self.cluster[pred_cluster].maximum
                    return self.__generate_index(pred_cluster, offset)
    
    def delete(self, key):
        if self.minimum == self.maximum:
            self.minimum = self.maximum = -1
            return True
        elif self.universe_size == 2:
            if key == 0:
                self.minimum = 1
            else:
                self.minimum = 0
            self.maximum = self.minimum
            return False
        else:
            if key == self.minimum:
                first_cluster = self.summary.minimum
                key = self.__generate_index(first_cluster, self.cluster[first_cluster].minimum)
                self.minimum = key
            flg0 = self.cluster[self.__high(key)].delete(self.__low(key))
            if flg0:
                del self.cluster[self.__high(key)]
                flg1 = self.summary.delete(self.__high(key))
                if key == self.maximum:
                    if flg1:
                        self.maximum = self.minimum
                    else:
                        max_insummary = self.summary.maximum
                        self.maximum = self.__generate_index(max_insummary, self.cluster[max_insummary].maximum)
            elif key == self.maximum:
                self.maximum = self.__generate_index(self.__high(key), self.cluster[self.__high(key)].maximum)


def solve():
    N, Q = map(int, rl().split())
    events = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        events.append((t - x, 0, x))
        events.append((s - x, 1, x))
    for _ in range(Q):
        events.append((int(rl()), 2, -1))
    events.sort(key=itemgetter(0, 1))
    
    ans = []
    veb = VanEmdeBoasTree(10 ** 9)
    for _, com, pos in events:
        if com == 0:
            veb.delete(pos)
        elif com == 1:
            veb.insert(pos)
        else:
            ans.append(veb.minimum)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()


Fixed submission:
import sys
import heapq as hq
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, Q = map(int, rl().split())
    event = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        event.append((t - x, 0, x))
        event.append((s - x, 1, x))
    for _ in range(Q):
        d = int(rl())
        event.append((d, 2, -1))
    event.sort(key=itemgetter(0, 1))
    
    pos_set = set()
    pos_hq = []
    ans = []
    for _, com, pos in event:
        if com == 0:
            pos_set.remove(pos)
        elif com == 1:
            pos_set.add(pos)
            hq.heappush(pos_hq, pos)
        else:
            while pos_hq:
                if pos_hq[0] not in pos_set:
                    hq.heappop(pos_hq)
                else:
                    break
            ans.append(pos_hq[0] if pos_hq else -1)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from math import ceil
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class VanEmdeBoasTree:
    def __init__(self, size):
        self.universe_size = 1
        while self.universe_size < size:
            self.universe_size <<= 1
        self.minimum = -1
        self.maximum = -1
        self.summary = None
        self.cluster = {}
    
    def __high(self, x):
        return x // ceil(self.universe_size ** 0.5)
    
    def __low(self, x):
        return x % ceil(self.universe_size ** 0.5)
    
    def __generate_index(self, x, y):
        return x * ceil(self.universe_size ** 0.5) + y
    
    def min(self):
        return self.minimum
    
    def max(self):
        return self.maximum
    
    def __empinsert(self, key):
        self.minimum = self.maximum = key
    
    def insert(self, key):
        if self.minimum == -1:
            self.minimum = self.maximum = key
        else:
            if key < self.minimum:
                self.minimum, key = key, self.minimum
            if 2 < self.universe_size:
                if self.__high(key) not in self.cluster:
                    self.cluster[self.__high(key)] = VanEmdeBoasTree(ceil(self.universe_size ** 0.5))
                    if self.summary is None:
                        self.summary = VanEmdeBoasTree(ceil(self.universe_size ** 0.5))
                    self.summary.insert(self.__high(key))
                    self.cluster[self.__high(key)].__empinsert(self.__low(key))
                else:
                    self.cluster[self.__high(key)].insert(self.__low(key))
            if self.maximum < key:
                self.maximum = key
    
    def is_member(self, key):
        if self.minimum == key or self.maximum == key:
            return True
        elif self.universe_size == 2:
            return False
        else:
            if self.__high(key) in self.cluster:
                return self.cluster[self.__high(key)].is_member(self.__low(key))
            else:
                return False
    
    def successor(self, key):
        # バグらせてるっぽい
        if self.universe_size == 2:
            if key == 0 and self.maximum == 1:
                return 1
            else:
                return -1
        elif self.minimum != -1 and key < self.minimum:
            return self.minimum
        else:
            max_incluster = -1
            if self.__high(key) in self.cluster:
                max_incluster = self.cluster[self.__high(key)].max()
            if max_incluster != -1 and self.__low(key) < max_incluster:
                offset = self.cluster[self.__high(key)].successor(self.__low(key))
                return self.__generate_index(self.__high(key), offset)
            else:
                succ_cluster = -1
                if self.summary.successor is not None:
                    succ_cluster = self.summary.successor(self.__high(key))
                if succ_cluster == -1:
                    return -1
                else:
                    offset = self.cluster[succ_cluster].min()
                    return self.__generate_index(succ_cluster, offset)
    
    def predecessor(self, key):
        if self.universe_size == 2:
            if key == 1 and self.minimum == 0:
                return 0
            else:
                return -1
        elif self.maximum != -1 and self.maximum < key:
            return self.maximum
        else:
            min_incluster = -1
            if self.__high(key) in self.cluster:
                min_incluster = self.cluster[self.__high(key)].min()
            if min_incluster != -1 and min_incluster < self.__low(key):
                offset = self.cluster[self.__high(key)].predecessor(self.__low(key))
                return self.__generate_index(self.__high(key), offset)
            else:
                pred_cluster = -1
                if self.summary is not None:
                    pred_cluster = self.summary.predecessor(self.__high(key))
                if pred_cluster == -1:
                    if self.minimum != -1 and self.minimum < key:
                        return self.minimum
                    else:
                        return -1
                else:
                    offset = self.cluster[pred_cluster].max()
                    return self.__generate_index(pred_cluster, offset)
    
    def delete(self, key):
        if self.minimum == self.maximum:
            self.minimum = self.maximum = -1
            return True
        elif self.universe_size == 2:
            if key == 0:
                self.minimum = 1
            else:
                self.minimum = 0
            self.maximum = self.minimum
            return False
        else:
            if key == self.minimum:
                first_cluster = self.summary.min()
                key = self.__generate_index(first_cluster, self.cluster[first_cluster].min())
                self.minimum = key
            flg0 = self.cluster[self.__high(key)].delete(self.__low(key))
            if flg0:
                del self.cluster[self.__high(key)]
                flg1 = self.summary.delete(self.__high(key))
                if key == self.maximum:
                    if flg1:
                        self.maximum = self.minimum
                    else:
                        max_insummary = self.summary.max()
                        self.maximum = self.__generate_index(max_insummary, self.cluster[max_insummary].max())
            elif key == self.maximum:
                self.maximum = self.__generate_index(self.__high(key), self.cluster[self.__high(key)].max())


def solve():
    N, Q = map(int, rl().split())
    events = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        events.append((t - x, 0, x))
        events.append((s - x, 1, x))
    for _ in range(Q):
        d = int(rl())
        events.append((d, 2, -1))
    events.sort(key=itemgetter(0, 1))
    
    ans = []
    veb = VanEmdeBoasTree(10 ** 9)
    for _, com, pos in events:
        if com == 0:
            veb.delete(pos)
        elif com == 1:
            veb.insert(pos)
        else:
            ans.append(veb.min())
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()


Fixed submission:
import sys
import heapq as hq
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, Q = map(int, rl().split())
    event = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        event.append((t - x, 0, x))
        event.append((s - x, 1, x))
    for _ in range(Q):
        d = int(rl())
        event.append((d, 2, -1))
    event.sort(key=itemgetter(0, 1))
    
    pos_set = set()
    pos_hq = []
    ans = []
    for _, com, pos in event:
        if com == 0:
            pos_set.remove(pos)
        elif com == 1:
            pos_set.add(pos)
            hq.heappush(pos_hq, pos)
        else:
            while pos_hq:
                if pos_hq[0] not in pos_set:
                    hq.heappop(pos_hq)
                else:
                    break
            ans.append(pos_hq[0] if pos_hq else -1)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from math import ceil
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def upsqrt(x):
    k = x ** 0.5
    res = 1
    while res < k:
        res <<= 1
    return res


class VanEmdeBoasTree:
    def __init__(self, size):
        self.universe_size = 1
        while self.universe_size < size:
            self.universe_size <<= 1
        self.minimum = -1
        self.maximum = -1
        self.summary = None
        self.cluster = {}
    
    def __high(self, x):
        return x // ceil(self.universe_size ** 0.5)
    
    def __low(self, x):
        return x % ceil(self.universe_size ** 0.5)
    
    def __generate_index(self, x, y):
        return x * ceil(self.universe_size ** 0.5) + y
    
    def min(self):
        return self.minimum
    
    def max(self):
        return self.maximum
    
    def __empinsert(self, key):
        self.minimum = self.maximum = key
    
    def insert(self, key):
        if self.minimum == -1:
            self.__empinsert(key)
        else:
            if key < self.minimum:
                self.minimum, key = key, self.minimum
            if 2 < self.universe_size:
                if self.__high(key) not in self.cluster:
                    self.cluster[self.__high(key)] = VanEmdeBoasTree(ceil(self.universe_size ** 0.5))
                    if self.summary is None:
                        self.summary = VanEmdeBoasTree(upsqrt(self.universe_size))
                    self.summary.insert(self.__high(key))
                    self.cluster[self.__high(key)].__empinsert(self.__low(key))
                else:
                    self.cluster[self.__high(key)].insert(self.__low(key))
            if self.maximum < key:
                self.maximum = key
    
    def is_member(self, key):
        if self.minimum == key or self.maximum == key:
            return True
        elif self.universe_size == 2:
            return False
        else:
            if self.__high(key) in self.cluster:
                return self.cluster[self.__high(key)].is_member(self.__low(key))
            else:
                return False
    
    def successor(self, key):
        # バグらせてるっぽい
        if self.universe_size == 2:
            if key == 0 and self.maximum == 1:
                return 1
            else:
                return -1
        elif self.minimum != -1 and key < self.minimum:
            return self.minimum
        else:
            max_incluster = -1
            if self.__high(key) in self.cluster:
                max_incluster = self.cluster[self.__high(key)].max()
            if max_incluster != -1 and self.__low(key) < max_incluster:
                offset = self.cluster[self.__high(key)].successor(self.__low(key))
                return self.__generate_index(self.__high(key), offset)
            else:
                succ_cluster = -1
                if self.summary.successor is not None:
                    succ_cluster = self.summary.successor(self.__high(key))
                if succ_cluster == -1:
                    return -1
                else:
                    offset = self.cluster[succ_cluster].min()
                    return self.__generate_index(succ_cluster, offset)
    
    def predecessor(self, key):
        if self.universe_size == 2:
            if key == 1 and self.minimum == 0:
                return 0
            else:
                return -1
        elif self.maximum != -1 and self.maximum < key:
            return self.maximum
        else:
            min_incluster = -1
            if self.__high(key) in self.cluster:
                min_incluster = self.cluster[self.__high(key)].min()
            if min_incluster != -1 and min_incluster < self.__low(key):
                offset = self.cluster[self.__high(key)].predecessor(self.__low(key))
                return self.__generate_index(self.__high(key), offset)
            else:
                pred_cluster = -1
                if self.summary is not None:
                    pred_cluster = self.summary.predecessor(self.__high(key))
                if pred_cluster == -1:
                    if self.minimum != -1 and self.minimum < key:
                        return self.minimum
                    else:
                        return -1
                else:
                    offset = self.cluster[pred_cluster].max()
                    return self.__generate_index(pred_cluster, offset)
    
    def delete(self, key):
        if self.minimum == self.maximum:
            self.minimum = self.maximum = -1
            return True
        elif self.universe_size == 2:
            if key == 0:
                self.minimum = 1
            else:
                self.minimum = 0
            self.maximum = self.minimum
            return False
        else:
            if key == self.minimum:
                first_cluster = self.summary.min()
                key = self.__generate_index(first_cluster, self.cluster[first_cluster].min())
                self.minimum = key
            flg0 = self.cluster[self.__high(key)].delete(self.__low(key))
            if flg0:
                del self.cluster[self.__high(key)]
                flg1 = self.summary.delete(self.__high(key))
                if key == self.maximum:
                    if flg1:
                        self.maximum = self.minimum
                    else:
                        max_insummary = self.summary.max()
                        self.maximum = self.__generate_index(max_insummary, self.cluster[max_insummary].max())
            elif key == self.maximum:
                self.maximum = self.__generate_index(self.__high(key), self.cluster[self.__high(key)].max())


def solve():
    N, Q = map(int, rl().split())
    events = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        events.append((t - x, 0, x))
        events.append((s - x, 1, x))
    for _ in range(Q):
        d = int(rl())
        events.append((d, 2, -1))
    events.sort(key=itemgetter(0, 1))
    
    ans = []
    veb = VanEmdeBoasTree(10 ** 9)
    for _, com, pos in events:
        if com == 0:
            veb.delete(pos)
        elif com == 1:
            veb.insert(pos)
        else:
            ans.append(veb.min())
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()


Fixed submission:
import sys
import heapq as hq
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, Q = map(int, rl().split())
    event = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        event.append((t - x, 0, x))
        event.append((s - x, 1, x))
    for _ in range(Q):
        d = int(rl())
        event.append((d, 2, -1))
    event.sort(key=itemgetter(0, 1))
    
    pos_set = set()
    pos_hq = []
    ans = []
    for _, com, pos in event:
        if com == 0:
            pos_set.remove(pos)
        elif com == 1:
            pos_set.add(pos)
            hq.heappush(pos_hq, pos)
        else:
            while pos_hq:
                if pos_hq[0] not in pos_set:
                    hq.heappop(pos_hq)
                else:
                    break
            ans.append(pos_hq[0] if pos_hq else -1)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def upsqrt(x):
    k = x ** 0.5
    res = 1
    while res < k:
        res <<= 1
    return res


def botsqrt(x):
    k = x ** 0.5
    res = 1
    while res <= k:
        res <<= 1
    return res >> 1


class VanEmdeBoasTree:
    def __init__(self, size):
        self.universe_size = 1
        while self.universe_size < size:
            self.universe_size <<= 1
        self.minimum = -1
        self.maximum = -1
        self.summary = None
        self.cluster = {}
    
    def __high(self, x):
        return x // botsqrt(self.universe_size)
    
    def __low(self, x):
        return x % botsqrt(self.universe_size)
    
    def __generate_index(self, x, y):
        return x * botsqrt(self.universe_size) + y
    
    def min(self):
        return self.minimum
    
    def max(self):
        return self.maximum
    
    def __empinsert(self, key):
        self.minimum = self.maximum = key
    
    def insert(self, key):
        if self.minimum == -1:
            self.__empinsert(key)
        else:
            if key < self.minimum:
                self.minimum, key = key, self.minimum
            if 2 < self.universe_size:
                if self.__high(key) not in self.cluster:
                    self.cluster[self.__high(key)] = VanEmdeBoasTree(botsqrt(self.universe_size))
                    if self.summary is None:
                        self.summary = VanEmdeBoasTree(upsqrt(self.universe_size))
                    self.summary.insert(self.__high(key))
                    self.cluster[self.__high(key)].__empinsert(self.__low(key))
                else:
                    self.cluster[self.__high(key)].insert(self.__low(key))
            if self.maximum < key:
                self.maximum = key
    
    def is_member(self, key):
        if self.minimum == key or self.maximum == key:
            return True
        elif self.universe_size == 2:
            return False
        else:
            if self.__high(key) in self.cluster:
                return self.cluster[self.__high(key)].is_member(self.__low(key))
            else:
                return False
    
    def successor(self, key):
        # バグらせてるっぽい
        if self.universe_size == 2:
            if key == 0 and self.maximum == 1:
                return 1
            else:
                return -1
        elif self.minimum != -1 and key < self.minimum:
            return self.minimum
        else:
            max_incluster = -1
            if self.__high(key) in self.cluster:
                max_incluster = self.cluster[self.__high(key)].max()
            if max_incluster != -1 and self.__low(key) < max_incluster:
                offset = self.cluster[self.__high(key)].successor(self.__low(key))
                return self.__generate_index(self.__high(key), offset)
            else:
                succ_cluster = -1
                if self.summary.successor is not None:
                    succ_cluster = self.summary.successor(self.__high(key))
                if succ_cluster == -1:
                    return -1
                else:
                    offset = self.cluster[succ_cluster].min()
                    return self.__generate_index(succ_cluster, offset)
    
    def predecessor(self, key):
        if self.universe_size == 2:
            if key == 1 and self.minimum == 0:
                return 0
            else:
                return -1
        elif self.maximum != -1 and self.maximum < key:
            return self.maximum
        else:
            min_incluster = -1
            if self.__high(key) in self.cluster:
                min_incluster = self.cluster[self.__high(key)].min()
            if min_incluster != -1 and min_incluster < self.__low(key):
                offset = self.cluster[self.__high(key)].predecessor(self.__low(key))
                return self.__generate_index(self.__high(key), offset)
            else:
                pred_cluster = -1
                if self.summary is not None:
                    pred_cluster = self.summary.predecessor(self.__high(key))
                if pred_cluster == -1:
                    if self.minimum != -1 and self.minimum < key:
                        return self.minimum
                    else:
                        return -1
                else:
                    offset = self.cluster[pred_cluster].max()
                    return self.__generate_index(pred_cluster, offset)
    
    def delete(self, key):
        if self.minimum == self.maximum:
            self.minimum = self.maximum = -1
            return True
        elif self.universe_size == 2:
            if key == 0:
                self.minimum = 1
            else:
                self.minimum = 0
            self.maximum = self.minimum
            return False
        else:
            if key == self.minimum:
                first_cluster = self.summary.min()
                key = self.__generate_index(first_cluster, self.cluster[first_cluster].min())
                self.minimum = key
            flg0 = self.cluster[self.__high(key)].delete(self.__low(key))
            if flg0:
                del self.cluster[self.__high(key)]
                flg1 = self.summary.delete(self.__high(key))
                if key == self.maximum:
                    if flg1:
                        self.maximum = self.minimum
                    else:
                        max_insummary = self.summary.max()
                        self.maximum = self.__generate_index(max_insummary, self.cluster[max_insummary].max())
            elif key == self.maximum:
                self.maximum = self.__generate_index(self.__high(key), self.cluster[self.__high(key)].max())


def solve():
    N, Q = map(int, rl().split())
    events = []
    X = set()
    for _ in range(N):
        s, t, x = map(int, rl().split())
        events.append((t - x, 0, x))
        events.append((s - x, 1, x))
        X.add(x)
    for _ in range(Q):
        d = int(rl())
        events.append((d, 2, -1))
    events.sort(key=itemgetter(0, 1))
    
    X = tuple(sorted(X))
    x_to_idx = {x: idx for idx, x in enumerate(X)}
    
    ans = []
    veb = VanEmdeBoasTree(len(X))
    for _, com, pos in events:
        if com == 0:
            veb.delete(x_to_idx[pos])
        elif com == 1:
            veb.insert(x_to_idx[pos])
        else:
            ans.append(X[veb.min()] if veb.min() != -1 else -1)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()


Fixed submission:
import sys
import heapq as hq
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, Q = map(int, rl().split())
    event = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        event.append((t - x, 0, x))
        event.append((s - x, 1, x))
    for _ in range(Q):
        d = int(rl())
        event.append((d, 2, -1))
    event.sort(key=itemgetter(0, 1))
    
    pos_set = set()
    pos_hq = []
    ans = []
    for _, com, pos in event:
        if com == 0:
            pos_set.remove(pos)
        elif com == 1:
            pos_set.add(pos)
            hq.heappush(pos_hq, pos)
        else:
            while pos_hq:
                if pos_hq[0] not in pos_set:
                    hq.heappop(pos_hq)
                else:
                    break
            ans.append(pos_hq[0] if pos_hq else -1)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def upsqrt(x):
    k = x ** 0.5
    res = 1
    while res < k:
        res <<= 1
    return res


def botsqrt(x):
    k = x ** 0.5
    res = 1
    while res <= k:
        res <<= 1
    return res >> 1


class VanEmdeBoasTree:
    def __init__(self, size):
        self.universe_size = 1
        while self.universe_size < size:
            self.universe_size <<= 1
        self.minimum = -1
        self.maximum = -1
        self.summary = None
        self.cluster = {}
    
    def __high(self, x):
        return x // botsqrt(self.universe_size)
    
    def __low(self, x):
        return x % botsqrt(self.universe_size)
    
    def __generate_index(self, x, y):
        return x * botsqrt(self.universe_size) + y
    
    def min(self):
        return self.minimum
    
    def max(self):
        return self.maximum
    
    def __empinsert(self, key):
        self.minimum = self.maximum = key
    
    def insert(self, key):
        if self.minimum == -1:
            self.__empinsert(key)
        else:
            if key < self.minimum:
                self.minimum, key = key, self.minimum
            if 2 < self.universe_size:
                if self.__high(key) not in self.cluster:
                    self.cluster[self.__high(key)] = VanEmdeBoasTree(botsqrt(self.universe_size))
                    if self.summary is None:
                        self.summary = VanEmdeBoasTree(upsqrt(self.universe_size))
                    self.summary.insert(self.__high(key))
                    self.cluster[self.__high(key)].__empinsert(self.__low(key))
                else:
                    self.cluster[self.__high(key)].insert(self.__low(key))
            if self.maximum < key:
                self.maximum = key
    
    def is_member(self, key):
        if self.minimum == key or self.maximum == key:
            return True
        elif self.universe_size == 2:
            return False
        else:
            if self.__high(key) in self.cluster:
                return self.cluster[self.__high(key)].is_member(self.__low(key))
            else:
                return False
    
    def successor(self, key):
        # バグらせてるっぽい
        if self.universe_size == 2:
            if key == 0 and self.maximum == 1:
                return 1
            else:
                return -1
        elif self.minimum != -1 and key < self.minimum:
            return self.minimum
        else:
            max_incluster = -1
            if self.__high(key) in self.cluster:
                max_incluster = self.cluster[self.__high(key)].max()
            if max_incluster != -1 and self.__low(key) < max_incluster:
                offset = self.cluster[self.__high(key)].successor(self.__low(key))
                return self.__generate_index(self.__high(key), offset)
            else:
                succ_cluster = -1
                if self.summary.successor is not None:
                    succ_cluster = self.summary.successor(self.__high(key))
                if succ_cluster == -1:
                    return -1
                else:
                    offset = self.cluster[succ_cluster].min()
                    return self.__generate_index(succ_cluster, offset)
    
    def predecessor(self, key):
        if self.universe_size == 2:
            if key == 1 and self.minimum == 0:
                return 0
            else:
                return -1
        elif self.maximum != -1 and self.maximum < key:
            return self.maximum
        else:
            min_incluster = -1
            if self.__high(key) in self.cluster:
                min_incluster = self.cluster[self.__high(key)].min()
            if min_incluster != -1 and min_incluster < self.__low(key):
                offset = self.cluster[self.__high(key)].predecessor(self.__low(key))
                return self.__generate_index(self.__high(key), offset)
            else:
                pred_cluster = -1
                if self.summary is not None:
                    pred_cluster = self.summary.predecessor(self.__high(key))
                if pred_cluster == -1:
                    if self.minimum != -1 and self.minimum < key:
                        return self.minimum
                    else:
                        return -1
                else:
                    offset = self.cluster[pred_cluster].max()
                    return self.__generate_index(pred_cluster, offset)
    
    def delete(self, key):
        if self.minimum == self.maximum:
            self.minimum = self.maximum = -1
            return True
        elif self.universe_size == 2:
            if key == 0:
                self.minimum = 1
            else:
                self.minimum = 0
            self.maximum = self.minimum
            return False
        else:
            if key == self.minimum:
                first_cluster = self.summary.min()
                key = self.__generate_index(first_cluster, self.cluster[first_cluster].min())
                self.minimum = key
            flg0 = self.cluster[self.__high(key)].delete(self.__low(key))
            if flg0:
                del self.cluster[self.__high(key)]
                flg1 = self.summary.delete(self.__high(key))
                if key == self.maximum:
                    if flg1:
                        self.maximum = self.minimum
                    else:
                        max_insummary = self.summary.max()
                        self.maximum = self.__generate_index(max_insummary, self.cluster[max_insummary].max())
            elif key == self.maximum:
                self.maximum = self.__generate_index(self.__high(key), self.cluster[self.__high(key)].max())


def solve():
    N, Q = map(int, rl().split())
    events = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        events.append((t - x, 0, x))
        events.append((s - x, 1, x))
    for _ in range(Q):
        d = int(rl())
        events.append((d, 2, -1))
    events.sort(key=itemgetter(0, 1))
    
    ans = []
    veb = VanEmdeBoasTree(10 ** 9)
    for _, com, pos in events:
        if com == 0:
            veb.delete(pos)
        elif com == 1:
            veb.insert(pos)
        else:
            ans.append(veb.min())
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()


Fixed submission:
import sys
import heapq as hq
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, Q = map(int, rl().split())
    event = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        event.append((t - x, 0, x))
        event.append((s - x, 1, x))
    for _ in range(Q):
        d = int(rl())
        event.append((d, 2, -1))
    event.sort(key=itemgetter(0, 1))
    
    pos_set = set()
    pos_hq = []
    ans = []
    for _, com, pos in event:
        if com == 0:
            pos_set.remove(pos)
        elif com == 1:
            pos_set.add(pos)
            hq.heappush(pos_hq, pos)
        else:
            while pos_hq:
                if pos_hq[0] not in pos_set:
                    hq.heappop(pos_hq)
                else:
                    break
            ans.append(pos_hq[0] if pos_hq else -1)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class SegmentTree:
    def __init__(self, n: int, segfunc, ide_ele):
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
    
    def build(self, init_value: list):
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    def update(self, k: int, x):
        k += self.N0 - 1
        ################################################################
        self.data[k] = x
        ################################################################
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        ################################################################
        
        while L < R:
            if L & 1:
                res = self.segfunc(res, self.data[L - 1])
                L += 1
            if R & 1:
                R -= 1
                res = self.segfunc(res, self.data[R - 1])
            L >>= 1
            R >>= 1
        
        ################################################################
        return res


def solve():
    N, Q = map(int, rl().split())
    events = []
    xs = set()
    for _ in range(N):
        s, t, x = map(int, rl().split())
        events.append((t - x, 0, x))
        events.append((s - x, 1, x))
        xs.add(x)
    for _ in range(Q):
        d = int(rl())
        events.append((d, 2, -1))
    events.sort(key=itemgetter(0, 1))
    
    x_to_idx = {x: idx for idx, x in enumerate(sorted(xs))}
    M = len(xs)
    ide_ele = 10 ** 10
    seg_tree = SegmentTree(M, min, ide_ele)
    
    ans = []
    for _, com, pos in events:
        if com == 0:
            seg_tree.update(x_to_idx[pos], ide_ele)
        elif com == 1:
            seg_tree.update(x_to_idx[pos], pos)
        else:
            tmp = seg_tree.data[0]
            ans.append(tmp if tmp != ide_ele else -1)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()


Fixed submission:
import sys
import heapq as hq
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, Q = map(int, rl().split())
    event = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        event.append((t - x, 0, x))
        event.append((s - x, 1, x))
    for _ in range(Q):
        d = int(rl())
        event.append((d, 2, -1))
    event.sort(key=itemgetter(0, 1))
    
    pos_set = set()
    pos_hq = []
    ans = []
    for _, com, pos in event:
        if com == 0:
            pos_set.remove(pos)
        elif com == 1:
            pos_set.add(pos)
            hq.heappush(pos_hq, pos)
        else:
            while pos_hq:
                if pos_hq[0] not in pos_set:
                    hq.heappop(pos_hq)
                else:
                    break
            ans.append(pos_hq[0] if pos_hq else -1)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappush, heappop
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, Q = map(int, rl().split())
    events = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        events.append((t - x, 0, x))
        events.append((s - x, 1, x))
    for _ in range(Q):
        d = int(rl())
        events.append((d, 2, -1))
    events.sort(key=itemgetter(0, 1))
    
    pos_set = set()
    pos_hq = []
    ans = []
    for _, com, pos in events:
        if com == 0:
            pos_set.remove(pos)
        elif com == 1:
            pos_set.add(pos)
            heappush(pos_hq, pos)
        else:
            while pos_hq:
                if pos_hq[0] not in pos_set:
                    heappop(pos_hq)
                else:
                    break
            ans.append(pos_hq[0] if pos_hq else -1)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()


Fixed submission:
import sys
import heapq as hq
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, Q = map(int, rl().split())
    event = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        event.append((t - x, 0, x))
        event.append((s - x, 1, x))
    for _ in range(Q):
        d = int(rl())
        event.append((d, 2, -1))
    event.sort(key=itemgetter(0, 1))
    
    pos_set = set()
    pos_hq = []
    ans = []
    for _, com, pos in event:
        if com == 0:
            pos_set.remove(pos)
        elif com == 1:
            pos_set.add(pos)
            hq.heappush(pos_hq, pos)
        else:
            while pos_hq:
                if pos_hq[0] not in pos_set:
                    hq.heappop(pos_hq)
                else:
                    break
            ans.append(pos_hq[0] if pos_hq else -1)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq as hq
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, Q = map(int, rl().split())
    event = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        event.append((t - x, 0, x))
        event.append((s - x, 1, x))
    for _ in range(Q):
        d = int(rl())
        event.append((d, 2, -1))
    event.sort(key=itemgetter(0, 1))
    
    pos_set = set()
    pos_hq = []
    ans = []
    for _, com, pos in event:
        if com == 0:
            pos_set.remove(pos)
        elif com == 1:
            pos_set.add(pos)
            hq.heappush(pos_hq, pos)
        else:
            while pos_hq:
                if pos_hq[0] not in pos_set:
                    hq.heappop(pos_hq)
                else:
                    break
            ans.append(pos_hq[0] if pos_hq else -1)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()


Fixed submission:
import sys
import heapq as hq
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, Q = map(int, rl().split())
    event = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        event.append((t - x, 0, x))
        event.append((s - x, 1, x))
    for _ in range(Q):
        d = int(rl())
        event.append((d, 2, -1))
    event.sort(key=itemgetter(0, 1))
    
    pos_set = set()
    pos_hq = []
    ans = []
    for _, com, pos in event:
        if com == 0:
            pos_set.remove(pos)
        elif com == 1:
            pos_set.add(pos)
            hq.heappush(pos_hq, pos)
        else:
            while pos_hq:
                if pos_hq[0] not in pos_set:
                    hq.heappop(pos_hq)
                else:
                    break
            ans.append(pos_hq[0] if pos_hq else -1)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()