Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline
INF = float("inf")


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    D = [int(input()) for _ in range(Q)]
    ans = [INF] * Q
    for S, T, X in constructions:
        l = bisect_left(D, S-X)
        r = bisect_right(D, T-X-1)
        for idx in range(l, r):
            ans[idx] = min(X, ans[idx])
    for a in ans:
        if a == INF:
            print(-1)
        else:
            print(a)


if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    constructions.sort(key=itemgetter(2))
    D = [int(input()) for _ in range(Q)]
    ans = [-1] * Q
    nxt = list(range(1, Q+1))
    for S, T, X in constructions:
        l = bisect_left(D, S-X)
        r = bisect_right(D, T-X-1)
        idx = l
        while idx < r:
            if ans[idx] == -1:
                ans[idx] = X
            nidx = nxt[idx]
            nxt[idx] = max(nxt[idx], r)
            idx = nidx
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    D = [int(input()) for _ in range(Q)]
    ans = [-1] * Q
    for S, T, X in constructions:
        l = bisect_left(D, S-X)
        r = bisect_right(D, T-X-1)
        for idx in range(l, r):
            if ans[idx] == -1 or ans[idx] > X:
                ans[idx] = X
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    constructions.sort(key=itemgetter(2))
    D = [int(input()) for _ in range(Q)]
    ans = [-1] * Q
    nxt = list(range(1, Q+1))
    for S, T, X in constructions:
        l = bisect_left(D, S-X)
        r = bisect_right(D, T-X-1)
        idx = l
        while idx < r:
            if ans[idx] == -1:
                ans[idx] = X
            nidx = nxt[idx]
            nxt[idx] = max(nxt[idx], r)
            idx = nidx
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    DI = [(int(input()), i) for i in range(Q)]
    DI.sort(key=itemgetter(0))
    D = [0] * Q
    revD = [0] * Q
    for i in range(Q):
        D[i], revD[i] = DI[i]
    ans = [-1] * Q
    for S, T, X in constructions:
        l = bisect_left(D, S-X)
        r = bisect_right(D, T-X-1)
        for i in range(l, r):
            idx = revD[i]
            if ans[idx] == -1 or ans[idx] > X:
                ans[idx] = X
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    constructions.sort(key=itemgetter(2))
    D = [int(input()) for _ in range(Q)]
    ans = [-1] * Q
    nxt = list(range(1, Q+1))
    for S, T, X in constructions:
        l = bisect_left(D, S-X)
        r = bisect_right(D, T-X-1)
        idx = l
        while idx < r:
            if ans[idx] == -1:
                ans[idx] = X
            nidx = nxt[idx]
            nxt[idx] = max(nxt[idx], r)
            idx = nidx
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left, bisect_right
from operator import itemgetter


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    D = [(int(input()), i) for i in range(Q)]
    D.sort(key=itemgetter(0))
    ans = [-1] * Q
    for S, T, X in constructions:
        l = bisect_left(D, (S-X, -1))
        r = bisect_right(D, (T-X, -1))
        for i in range(l, r):
            idx = D[i][1]
            if ans[idx] == -1 or ans[idx] > X:
                ans[idx] = X
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    constructions.sort(key=itemgetter(2))
    D = [int(input()) for _ in range(Q)]
    ans = [-1] * Q
    nxt = list(range(1, Q+1))
    for S, T, X in constructions:
        l = bisect_left(D, S-X)
        r = bisect_right(D, T-X-1)
        idx = l
        while idx < r:
            if ans[idx] == -1:
                ans[idx] = X
            nidx = nxt[idx]
            nxt[idx] = max(nxt[idx], r)
            idx = nidx
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    D = [(int(input()), i) for i in range(Q)]
    D.sort(key=itemgetter(0))
    ans = [-1] * Q
    for S, T, X in constructions:
        l = bisect_left(D, (S-X, -1))
        r = bisect_right(D, (T-X, -1))
        for i in range(l, r):
            idx = D[i][1]
            if ans[idx] == -1 or ans[idx] > X:
                ans[idx] = X
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    constructions.sort(key=itemgetter(2))
    D = [int(input()) for _ in range(Q)]
    ans = [-1] * Q
    nxt = list(range(1, Q+1))
    for S, T, X in constructions:
        l = bisect_left(D, S-X)
        r = bisect_right(D, T-X-1)
        idx = l
        while idx < r:
            if ans[idx] == -1:
                ans[idx] = X
            nidx = nxt[idx]
            nxt[idx] = max(nxt[idx], r)
            idx = nidx
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline


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

    def insert(self, value):
        if self.root:
            self.root.insert(value)
        else:
            self.root = BinTreeNode(value)

    def exists(self, value):
        if self.root:
            return self.root.exists(value)
        else:
            return False

    def min(self):
        if self.root:
            return self.root.min()
        else:
            return None

    def max(self):
        if self.root:
            return self.root.max()
        else:
            return None

    def remove(self, value):
        if self.root:
            self.root = self.root.remove(value)

    def sort(self):
        if self.root:
            return self.__walk(self.root)
        else:
            return []

    def __walk(self, target):
        ret = []
        if target.left:
            ret += self.__walk(target.left)
        ret += [target.value]
        if target.right:
            ret += self.__walk(target.right)
        return ret


class BinTreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1

    def insert(self, value):
        if value < self.value:
            if self.left:
                self.left.insert(value)
            else:
                self.left = BinTreeNode(value)
        else:
            if self.right:
                self.right.insert(value)
            else:
                self.right = BinTreeNode(value)
        self.rebuild()

    def rebuild(self):
        lheight = BinTreeNode.height(self.left)
        rheight = BinTreeNode.height(self.right)
        if lheight - rheight >= 2:
            if BinTreeNode.height(self.left.left) < BinTreeNode.height(self.left.right):
                BinTreeNode.turn_left(self.left)
            BinTreeNode.turn_right(self)
        elif rheight - lheight >= 2:
            if BinTreeNode.height(self.right.left) > BinTreeNode.height(self.right.right):
                BinTreeNode.turn_right(self.right)
            BinTreeNode.turn_left(self)
        else:
            BinTreeNode.update_height(self)

    @classmethod
    def turn_left(cls, root):
        gl = root.right.left
        gr = root.right.right
        v = root.value
        r = root.right
        rv = r.value
        r.left = root.left
        r.right = gl
        r.value = v
        root.left = root.right
        root.value = rv
        root.right = gr
        BinTreeNode.update_height(root.right)
        BinTreeNode.update_height(root)

    @classmethod
    def turn_right(cls, root):
        gl = root.left.left
        gr = root.left.right
        v = root.value
        l = root.left
        lv = l.value
        l.right = root.right
        l.left = gr
        l.value = v
        root.right = root.left
        root.value = lv
        root.left = gl
        BinTreeNode.update_height(root.left)
        BinTreeNode.update_height(root)

    @classmethod
    def height(cls, root):
        return root.height if root is not None else 0

    @classmethod
    def update_height(cls, root):
        if root is None:
            return
        root.height = max(BinTreeNode.height(root.left),
                          BinTreeNode.height(root.right)) + 1

    def exists(self, value):
        if value == self.value:
            return True
        elif value < self.value:
            if self.left:
                return self.left.exists(value)
            else:
                return False
        elif value > self.value:
            if self.right:
                return self.right.exists(value)
            else:
                return False

    def min(self):
        if self.left:
            return self.left.min()
        else:
            return self.value

    def max(self):
        if self.right:
            return self.right.max()
        else:
            return self.value

    def __removenode(self):
        if self.left and self.right:
            value = self.left.max()
            self.value = value
            self.left = self.left.remove(value)
            return self
        elif self.left:
            return self.left
        elif self.right:
            return self.right
        else:
            return None

    def remove(self, value):
        if value == self.value:
            self = self.__removenode()
        elif value < self.value:
            self.left = self.left.remove(value)
        elif value > self.value:
            self.right = self.right.remove(value)
        if self:
            self.rebuild()
        return self


def main():
    N, Q = map(int, input().split())
    construction = [None] * N
    events = [None] * (N*2+Q)
    for i in range(N):
        S, T, X = map(int, input().split())
        events[i*2] = (S-X, 1, X)
        events[i*2+1] = (T-X, 0, X)
    for i in range(Q):
        D = int(input())
        events[N*2+i] = (D, 2, 0)
    events.sort()
    bt = BinTree()
    for t, e, x in events:
        if e == 0:
            bt.remove(x)
        elif e == 1:
            bt.insert(x)
        else:
            ans = bt.min()
            if ans is None:
                print(-1)
            else:
                print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    constructions.sort(key=itemgetter(2))
    D = [int(input()) for _ in range(Q)]
    ans = [-1] * Q
    nxt = list(range(1, Q+1))
    for S, T, X in constructions:
        l = bisect_left(D, S-X)
        r = bisect_right(D, T-X-1)
        idx = l
        while idx < r:
            if ans[idx] == -1:
                ans[idx] = X
            nidx = nxt[idx]
            nxt[idx] = max(nxt[idx], r)
            idx = nidx
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

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


def main():
    N, Q = map(int, input().split())
    construction = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        construction[i] = (S-X, T-X, X)
    construction.sort(reverse=True)
    D = [int(input()) for _ in range(Q)]
    q = []
    for i in range(Q):
        while len(construction) and construction[-1][0] <= D[i]:
            sx, tx, x = construction.pop()
            heappush(q, (x, tx))
        while len(q) and q[0][1] <= D[i]:
            heappop(q)
        if len(q):
            print(q[0][0])
        else:
            print(-1)


if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    constructions.sort(key=itemgetter(2))
    D = [int(input()) for _ in range(Q)]
    ans = [-1] * Q
    nxt = list(range(1, Q+1))
    for S, T, X in constructions:
        l = bisect_left(D, S-X)
        r = bisect_right(D, T-X-1)
        idx = l
        while idx < r:
            if ans[idx] == -1:
                ans[idx] = X
            nidx = nxt[idx]
            nxt[idx] = max(nxt[idx], r)
            idx = nidx
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

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


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

    def insert(self, value):
        if self.root:
            self.root.insert(value)
        else:
            self.root = BinTreeNode(value)

    def exists(self, value):
        if self.root:
            return self.root.exists(value)
        else:
            return False

    def min(self):
        if self.root:
            return self.root.min()
        else:
            return None

    def max(self):
        if self.root:
            return self.root.max()
        else:
            return None

    def remove(self, value):
        if self.root:
            self.root = self.root.remove(value)

    def sort(self):
        if self.root:
            return self.__walk(self.root)
        else:
            return []

    def __walk(self, target):
        ret = []
        if target.left:
            ret += self.__walk(target.left)
        ret += [target.value]
        if target.right:
            ret += self.__walk(target.right)
        return ret


class BinTreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def insert(self, value):
        if value < self.value:
            if self.left:
                self.left.insert(value)
            else:
                self.left = BinTreeNode(value)
        else:
            if self.right:
                self.right.insert(value)
            else:
                self.right = BinTreeNode(value)

    def exists(self, value):
        if value == self.value:
            return True
        elif value < self.value:
            if self.left:
                return self.left.exists(value)
            else:
                return False
        elif value > self.value:
            if self.right:
                return self.right.exists(value)
            else:
                return False

    def min(self):
        if self.left:
            return self.left.min()
        else:
            return self.value

    def max(self):
        if self.right:
            return self.right.max()
        else:
            return self.value

    def __removenode(self):
        if self.left and self.right:
            value = self.left.max()
            self.value = value
            self.left = self.left.remove(value)
            return self
        elif self.left:
            return self.left
        elif self.right:
            return self.right
        else:
            return None

    def remove(self, value, par=None):
        if value == self.value:
            return self.__removenode()
        elif value < self.value:
            self.left = self.left.remove(value, self)
        elif value > self.value:
            self.right = self.right.remove(value, self)
        return self


def main():
    N, Q = map(int, input().split())
    query = [None] * (2 * N + Q)
    for i in range(N):
        S, T, X = map(int, input().split())
        query[i*2] = (S-X, 0, X)
        query[i*2+1] = (T-X-1, 2, X)
    for i in range(Q):
        D = int(input())
        query[2*N+i] = (D, 1, 0)
    query.sort(itemgetter(0, 1))
    bt = BinTree()
    for t, q, x in query:
        if q == 0:
            bt.insert(x)
        elif q == 1:
            print(bt.min() or -1)
        elif q == 2:
            bt.remove(x)


if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    constructions.sort(key=itemgetter(2))
    D = [int(input()) for _ in range(Q)]
    ans = [-1] * Q
    nxt = list(range(1, Q+1))
    for S, T, X in constructions:
        l = bisect_left(D, S-X)
        r = bisect_right(D, T-X-1)
        idx = l
        while idx < r:
            if ans[idx] == -1:
                ans[idx] = X
            nidx = nxt[idx]
            nxt[idx] = max(nxt[idx], r)
            idx = nidx
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
class BinTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root:
            self.root.insert(value)
        else:
            self.root = BinTreeNode(value)

    def exists(self, value):
        if self.root:
            return self.root.exists(value)
        else:
            return False

    def min(self):
        if self.root:
            return self.root.min()
        else:
            return None

    def max(self):
        if self.root:
            return self.root.max()
        else:
            return None

    def remove(self, value):
        if self.root:
            self.root = self.root.remove(value)

    def sort(self):
        if self.root:
            return self.__walk(self.root)
        else:
            return []

    def __walk(self, target):
        ret = []
        if target.left:
            ret += self.__walk(target.left)
        ret += [target.value]
        if target.right:
            ret += self.__walk(target.right)
        return ret


class BinTreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def insert(self, value):
        if value < self.value:
            if self.left:
                self.left.insert(value)
            else:
                self.left = BinTreeNode(value)
        else:
            if self.right:
                self.right.insert(value)
            else:
                self.right = BinTreeNode(value)

    def exists(self, value):
        if value == self.value:
            return True
        elif value < self.value:
            if self.left:
                return self.left.exists(value)
            else:
                return False
        elif value > self.value:
            if self.right:
                return self.right.exists(value)
            else:
                return False

    def min(self):
        if self.left:
            return self.left.min()
        else:
            return self.value

    def max(self):
        if self.right:
            return self.right.max()
        else:
            return self.value

    def __removenode(self):
        if self.left and self.right:
            value = self.left.max()
            self.value = value
            self.left = self.left.remove(value)
            return self
        elif self.left:
            return self.left
        elif self.right:
            return self.right
        else:
            return None

    def remove(self, value, par=None):
        if value == self.value:
            return self.__removenode()
        elif value < self.value:
            self.left = self.left.remove(value, self)
        elif value > self.value:
            self.right = self.right.remove(value, self)
        return self


def main():
    N, Q = map(int, input().split())
    query = [None] * (2 * N + Q)
    for i in range(N):
        S, T, X = map(int, input().split())
        query[i*2] = (S-X, 0, X)
        query[i*2+1] = (T-X-1, 2, X)
    for i in range(Q):
        D = int(input())
        query[2*N+i] = (D, 1, 0)
    query.sort()
    bt = BinTree()
    for t, q, x in query:
        if q == 0:
            bt.insert(x)
        elif q == 1:
            print(bt.min() or -1)
        elif q == 2:
            bt.remove(x)


if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    constructions.sort(key=itemgetter(2))
    D = [int(input()) for _ in range(Q)]
    ans = [-1] * Q
    nxt = list(range(1, Q+1))
    for S, T, X in constructions:
        l = bisect_left(D, S-X)
        r = bisect_right(D, T-X-1)
        idx = l
        while idx < r:
            if ans[idx] == -1:
                ans[idx] = X
            nidx = nxt[idx]
            nxt[idx] = max(nxt[idx], r)
            idx = nidx
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, Q = map(int, input().split())
    query = [None] * (2 * N + Q)
    for i in range(N):
        S, T, X = map(int, input().split())
        query[i*2] = (S-X, 1, X)
        query[i*2+1] = (T-X, 0, X)
    for i in range(Q):
        D = int(input())
        query[2*N+i] = (D, 2, 0)
    query.sort()
    mn = float("inf")
    construction = set()
    for t, q, x in query:
        if q == 2:
            if mn == float("inf"):
                print(-1)
            else:
                print(mn)
        elif q == 1:
            construction.add(x)
            if x < mn:
                mn = x
        elif q == 0:
            construction.remove(x)
            if mn == x:
                if len(construction):
                    mn = min(construction)
                else:
                    mn = float("inf")


if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    constructions.sort(key=itemgetter(2))
    D = [int(input()) for _ in range(Q)]
    ans = [-1] * Q
    nxt = list(range(1, Q+1))
    for S, T, X in constructions:
        l = bisect_left(D, S-X)
        r = bisect_right(D, T-X-1)
        idx = l
        while idx < r:
            if ans[idx] == -1:
                ans[idx] = X
            nidx = nxt[idx]
            nxt[idx] = max(nxt[idx], r)
            idx = nidx
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()