Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from heapq import heappush, heappop
N, Q = map(int, input().split())
E = []

for i in range(N):
    s, t, x = map(int, input().split())
    E.append((0, t - x, x, i))
    E.append((1, s - x, x, i))

D = [int(input()) for _ in range(Q)]

E.sort(key=lambda a: a[1], reverse=True)

ans = []
que = [(10**18, -1)]
V = set()
for d in D:
    while E and E[-1][1] <= d:
        f, _, x, i = E.pop()
        if f == 0:
            V.add(i)
        else:
            heappush(que, (x, i))
    while que[0][1] in V:
        heappop(que)
    ans.append(que[0][0])

ans = [a if a < 10**18 else -1 for a in ans]
print(*ans, sep='\n')


Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

N, Q = map(int, input().split())
INF = float('inf')

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, 0, X))
    events.append((T - X, 1, X))

for _ in range(Q):
    events.append((int(input()), 2, 0))

events.sort()

cnt = defaultdict(int)
cnt[INF] += 1
que = [INF]

for t, flag, x in events:
    if flag == 0:
        if cnt[x] == 0:
            heappush(que, x)
        cnt[x] += 1
    elif flag == 1:
        cnt[x] -= 1
    else:
        while cnt[que[0]] == 0:
            heappop(que)
        print(que[0] if que[0] != INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
INF = float('inf')

class MinSegTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size):
        self.size = 1 << (size.bit_length())  # 完全二分木にする
        self.data = [INF] * (2 * self.size - 1)

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in range(self.size - 1)[:: -1]:
            self.data[i] = min(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = min(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = INF
        while L < R:
            if R & 1:
                R -= 1
                ret = min(ret, self.data[R - 1])
            if L & 1:
                ret = min(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

N, Q = map(int, input().split())

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, 0, i, X))
    events.append((T - X, 1, i, X))

for _ in range(Q):
    events.append((int(input()), 2, 0, 0))
events.sort()

tree = MinSegTree(N)

ans = []
for t, flag, index, x in events:
    if flag == 0:
        tree.update(index, x)
    elif flag == 1:
        tree.update(index, INF)
    else:
        print(tree.data[0] if tree.data[0] != INF else -1)


Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

N, Q = map(int, input().split())
INF = float('inf')

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, 0, X))
    events.append((T - X, 1, X))

for _ in range(Q):
    events.append((int(input()), 2, 0))

events.sort()

cnt = defaultdict(int)
cnt[INF] += 1
que = [INF]

for t, flag, x in events:
    if flag == 0:
        if cnt[x] == 0:
            heappush(que, x)
        cnt[x] += 1
    elif flag == 1:
        cnt[x] -= 1
    else:
        while cnt[que[0]] == 0:
            heappop(que)
        print(que[0] if que[0] != INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
INF = float('inf')

class MinSegTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size):
        self.size = 1 << (size.bit_length())  # 完全二分木にする
        self.data = [INF] * (2 * self.size - 1)

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in range(self.size - 1)[:: -1]:
            self.data[i] = min(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = min(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = INF
        while L < R:
            if R & 1:
                R -= 1
                ret = min(ret, self.data[R - 1])
            if L & 1:
                ret = min(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

N, Q = map(int, input().split())

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, 0, i, X))
    events.append((T - X, 1, i, X))

for _ in range(Q):
    events.append((int(input()), 2, 0, 0))
events.sort()

tree = MinSegTree(N)

ans = []
for t, flag, index, x in events:
    if flag == 0:
        tree.update(index, x)
    elif flag == 1:
        tree.update(index, INF)
    else:
        print(tree.data[0] if tree.data[0] != INF else -1)


Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

N, Q = map(int, input().split())
INF = float('inf')

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, 0, X))
    events.append((T - X, 1, X))

for _ in range(Q):
    events.append((int(input()), 2, 0))

events.sort()

cnt = defaultdict(int)
cnt[INF] += 1
que = [INF]

for t, flag, x in events:
    if flag == 0:
        if cnt[x] == 0:
            heappush(que, x)
        cnt[x] += 1
    elif flag == 1:
        cnt[x] -= 1
    else:
        while cnt[que[0]] == 0:
            heappop(que)
        print(que[0] if que[0] != INF else -1)

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

N, Q = map(int, input().split())
INF = float('inf')

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, 0, X))
    events.append((T - X, 1, X))

for _ in range(Q):
    events.append((int(input()), 2, 0))

events.sort()

cnt = defaultdict(int)
cnt[INF] += 1
que = [INF]

for t, flag, x in events:
    if flag == 0:
        if cnt[x] == 0:
            heappush(que, x)
        cnt[x] += 1
    elif flag == 1:
        cnt[x] -= 1
    else:
        while cnt[que[0]] == 0:
            heappop(que)
        print(que[0] if que[0] != INF else -1)



Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

N, Q = map(int, input().split())
INF = float('inf')

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, 0, X))
    events.append((T - X, 1, X))

for _ in range(Q):
    events.append((int(input()), 2, 0))

events.sort()

cnt = defaultdict(int)
cnt[INF] += 1
que = [INF]

for t, flag, x in events:
    if flag == 0:
        if cnt[x] == 0:
            heappush(que, x)
        cnt[x] += 1
    elif flag == 1:
        cnt[x] -= 1
    else:
        while cnt[que[0]] == 0:
            heappop(que)
        print(que[0] if que[0] != INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
INF = float('inf')

class MinSegTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size):
        self.size = 1 << (size.bit_length())  # 完全二分木にする
        self.data = [INF] * (2 * self.size - 1)

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in range(self.size - 1)[:: -1]:
            self.data[i] = min(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = min(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = INF
        while L < R:
            if R & 1:
                R -= 1
                ret = min(ret, self.data[R - 1])
            if L & 1:
                ret = min(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

N, Q = map(int, input().split())

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, 0, i, X))
    events.append((T - X, 1, i, X))

for _ in range(Q):
    events.append((int(input()), 2, 0, 0))
events.sort()

tree = MinSegTree(N)

ans = []
for t, flag, index, x in events:
    if flag == 0:
        tree.update(index, x)
    elif flag == 1:
        tree.update(index, INF)
    else:
        ans.append(tree.data[0])

for a in ans:
    print(-1 if a == INF else a)


Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

N, Q = map(int, input().split())
INF = float('inf')

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, 0, X))
    events.append((T - X, 1, X))

for _ in range(Q):
    events.append((int(input()), 2, 0))

events.sort()

cnt = defaultdict(int)
cnt[INF] += 1
que = [INF]

for t, flag, x in events:
    if flag == 0:
        if cnt[x] == 0:
            heappush(que, x)
        cnt[x] += 1
    elif flag == 1:
        cnt[x] -= 1
    else:
        while cnt[que[0]] == 0:
            heappop(que)
        print(que[0] if que[0] != INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
INF = float('inf')

class MinSegTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size):
        self.size = 1 << (size.bit_length())  # 完全二分木にする
        self.data = [INF] * (2 * self.size - 1)

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in range(self.size - 1)[:: -1]:
            self.data[i] = min(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = min(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = INF
        while L < R:
            if R & 1:
                R -= 1
                ret = min(ret, self.data[R - 1])
            if L & 1:
                ret = min(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

N, Q = map(int, input().split())

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, True, i, X))
    events.append((T - X, False, i, X))
events.sort()

tree = MinSegTree(N)

D = [int(input()) for _ in range(Q)]
M = len(events)
now = 0
ans = []
for d in D:
    while now < M and events[now][0] <= d:
        _, isStart, i, x = events[now]
        if isStart:
            tree.update(i, x)
        else:
            tree.update(i, INF)
        now += 1
    ans.append(tree.data[0])

for a in ans:
    print(-1 if a == INF else a)


Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

N, Q = map(int, input().split())
INF = float('inf')

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, 0, X))
    events.append((T - X, 1, X))

for _ in range(Q):
    events.append((int(input()), 2, 0))

events.sort()

cnt = defaultdict(int)
cnt[INF] += 1
que = [INF]

for t, flag, x in events:
    if flag == 0:
        if cnt[x] == 0:
            heappush(que, x)
        cnt[x] += 1
    elif flag == 1:
        cnt[x] -= 1
    else:
        while cnt[que[0]] == 0:
            heappop(que)
        print(que[0] if que[0] != INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
INF = float('inf')

class MinSegTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size):
        self.size = 1 << (size.bit_length())  # 完全二分木にする
        self.data = [INF] * (2 * self.size - 1)

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in range(self.size - 1)[:: -1]:
            self.data[i] = min(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = min(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = INF
        while L < R:
            if R & 1:
                R -= 1
                ret = min(ret, self.data[R - 1])
            if L & 1:
                ret = min(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

N, Q = map(int, input().split())

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, True, i, X))
    events.append((T - X, False, i, X))
events.sort()

tree = MinSegTree(N)

D = [int(input()) for _ in range(Q)]
M = len(events)
now = 0
ans = []
for d in D:
    while now < M and events[now][0] <= d:
        _, isStart, i, x = events[now]
        if isStart:
            tree.update(i, x)
        else:
            tree.update(i, INF)
        now += 1
    ans.append(tree.query(0, N))

for a in ans:
    print(-1 if a == INF else a)


Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

N, Q = map(int, input().split())
INF = float('inf')

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, 0, X))
    events.append((T - X, 1, X))

for _ in range(Q):
    events.append((int(input()), 2, 0))

events.sort()

cnt = defaultdict(int)
cnt[INF] += 1
que = [INF]

for t, flag, x in events:
    if flag == 0:
        if cnt[x] == 0:
            heappush(que, x)
        cnt[x] += 1
    elif flag == 1:
        cnt[x] -= 1
    else:
        while cnt[que[0]] == 0:
            heappop(que)
        print(que[0] if que[0] != INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
INF = float('inf')

class MinSegTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size):
        self.size = 1 << (size.bit_length())  # 完全二分木にする
        self.data = [INF] * (2 * self.size - 1)

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in range(self.size - 1)[:: -1]:
            self.data[i] = min(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = min(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = INF
        while L < R:
            if R & 1:
                R -= 1
                ret = min(ret, self.data[R - 1])
            if L & 1:
                ret = min(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

N, Q = map(int, input().split())

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, True, i, X))
    events.append((T - X, False, i, X))
events.sort()

tree = MinSegTree(N)

D = [int(input()) for _ in range(Q)]
M = len(events)
now = 0
ans = []
for d in D:
    while now < M and events[now][0] <= d:
        _, isStart, i, x = events[now]
        if isStart:
            tree.update(i, x)
        else:
            tree.update(i, INF)
        now += 1
    ans.append(tree.query(0, N))

for a in ans:
    print(-1 if a == INF else a)


Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

N, Q = map(int, input().split())
INF = float('inf')

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, 0, X))
    events.append((T - X, 1, X))

for _ in range(Q):
    events.append((int(input()), 2, 0))

events.sort()

cnt = defaultdict(int)
cnt[INF] += 1
que = [INF]

for t, flag, x in events:
    if flag == 0:
        if cnt[x] == 0:
            heappush(que, x)
        cnt[x] += 1
    elif flag == 1:
        cnt[x] -= 1
    else:
        while cnt[que[0]] == 0:
            heappop(que)
        print(que[0] if que[0] != INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())

STX = [tuple(map(int, input().split())) for _ in range(N)]
STX.sort(key=lambda A: A[2])

ans = []
for _ in range(Q):
    D = int(input())
    for s, t, x in STX:
        if s - x <= D < t - x:
            ans.append(x)
            break
    else:
        ans.append(-1)

print(*ans, sep='\n')

Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

N, Q = map(int, input().split())
INF = float('inf')

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, 0, X))
    events.append((T - X, 1, X))

for _ in range(Q):
    events.append((int(input()), 2, 0))

events.sort()

cnt = defaultdict(int)
cnt[INF] += 1
que = [INF]

for t, flag, x in events:
    if flag == 0:
        if cnt[x] == 0:
            heappush(que, x)
        cnt[x] += 1
    elif flag == 1:
        cnt[x] -= 1
    else:
        while cnt[que[0]] == 0:
            heappop(que)
        print(que[0] if que[0] != INF else -1)

Buggy python submission (verdict: Runtime Error):
N , Q = map(int,input().split())

D = [0]*Q
Input = []
length = [-1]*Q

for i in range(N):
    Input.append(list(map(int,input().split())))

# 距離順でソート
dist = lambda A : A[2]
Input.sort(key=dist)

for i in range(Q):
    D[i] = [i,int(input())]

# 出発時刻でソート
time = lambda A : A[1]
D.sort(key=time)

# i番目の人の座標を計算
skip = 0
for start in D:
    for j in range(N-skip):
        if(Input[j][1] <= start[1]): # 工事終了時刻 <= 出発時刻
            Input.pop(j)
            skip += 1
            continue

        stopTime = Input[j][2] + start[1] # 出発時刻 + 距離/速度

        if(stopTime >= Input[j][0] - 0.5 and stopTime <= Input[j][1] - 0.5): # 工事期間内
            length[start[0]] = Input[j][2]
            break

for i in range(Q):
    print(length[i])


Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

N, Q = map(int, input().split())
INF = float('inf')

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, 0, X))
    events.append((T - X, 1, X))

for _ in range(Q):
    events.append((int(input()), 2, 0))

events.sort()

cnt = defaultdict(int)
cnt[INF] += 1
que = [INF]

for t, flag, x in events:
    if flag == 0:
        if cnt[x] == 0:
            heappush(que, x)
        cnt[x] += 1
    elif flag == 1:
        cnt[x] -= 1
    else:
        while cnt[que[0]] == 0:
            heappop(que)
        print(que[0] if que[0] != INF else -1)

Buggy python submission (verdict: Runtime Error):
N , Q = map(int,input().split())

D = [0]*Q
Input = []
length = [-1]*Q

for i in range(N):
    Input.append(list(map(int,input().split())))

# 距離順でソート
dist = lambda A : A[2]
Input.sort(key=dist)

for i in range(Q):
    D[i] = [i,int(input())]

# 出発時刻でソート
time = lambda A : A[1]
D.sort(key=time)

# i番目の人の座標を計算
skip = 0
for start in D:
    for j in range(N):
        if(Input[j][1] <= start[1]): # 工事終了時刻 <= 出発時刻
            Input.pop(j)
            continue

        stopTime = Input[j][2] + start[1] # 出発時刻 + 距離/速度

        if(stopTime >= Input[j][0] - 0.5 and stopTime <= Input[j][1] - 0.5): # 工事期間内
            length[start[0]] = Input[j][2]
            break

for i in range(Q):
    print(length[i])


Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

N, Q = map(int, input().split())
INF = float('inf')

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, 0, X))
    events.append((T - X, 1, X))

for _ in range(Q):
    events.append((int(input()), 2, 0))

events.sort()

cnt = defaultdict(int)
cnt[INF] += 1
que = [INF]

for t, flag, x in events:
    if flag == 0:
        if cnt[x] == 0:
            heappush(que, x)
        cnt[x] += 1
    elif flag == 1:
        cnt[x] -= 1
    else:
        while cnt[que[0]] == 0:
            heappop(que)
        print(que[0] if que[0] != INF else -1)

Buggy python submission (verdict: Time Limit Exceeded):
N , Q = map(int,input().split())

D = [0]*Q
Input = []
length = [-1]*Q

for i in range(N):
    Input.append(list(map(int,input().split())))

dist = lambda A : A[2]
Input.sort(key=dist)

for i in range(Q):
    D[i] = int(input())

# i番目の人の座標を計算
for i in range(Q):
    for j in range(N):
        if(Input[j][1] <= D[i]): # 工事終了時刻 <= 出発時刻
            continue

        stopTime = Input[j][2] + D[i] # 出発時刻 + 距離/速度

        if(stopTime >= Input[j][0] - 0.5 and stopTime <= Input[j][1] - 0.5):
            length[i] = Input[j][2]
            break

for l in length:
    print(l)


Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

N, Q = map(int, input().split())
INF = float('inf')

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, 0, X))
    events.append((T - X, 1, X))

for _ in range(Q):
    events.append((int(input()), 2, 0))

events.sort()

cnt = defaultdict(int)
cnt[INF] += 1
que = [INF]

for t, flag, x in events:
    if flag == 0:
        if cnt[x] == 0:
            heappush(que, x)
        cnt[x] += 1
    elif flag == 1:
        cnt[x] -= 1
    else:
        while cnt[que[0]] == 0:
            heappop(que)
        print(que[0] if que[0] != INF else -1)