Buggy python submission (verdict: Time Limit Exceeded):
class BIT:
    def __init__(self, N):
        self.tree = [0] * (N + 1)  # 1-indexed
        self.N = N

    def add(self, i, x):
        """tree[i]と関連個所にxを加える"""
        tree = self.tree
        N = self.N
        while i <= N:
            tree[i] += x
            i += i & (-i)

    def sum(self, i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & (-i)
        return s

    def binary_search(self, x):
        """区間和 >=x となる最小のindex"""
        tree = self.tree
        N = self.N
        i = 0
        step = 1 << (N.bit_length() - 1)
        while step:
            if i + step <= N and tree[i + step] < x:
                i += step
                x -= tree[i]
            step >>= 1
        return i + 1


def main():
    from collections import deque, namedtuple
    from operator import attrgetter
    import sys

    input = sys.stdin.readline
    Event = namedtuple('Event', 'time position')

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

    go = []
    stop = []
    xs = set()
    for _ in range(N):
        s, t, x = map(int, input().split())
        stop.append(Event(time=s - x, position=x))
        go.append(Event(time=t - x, position=x))
        xs.add(x)

    xs = sorted(xs)

    stop.sort(key=attrgetter('time'))
    go.sort(key=attrgetter('time'))

    stop = deque(stop)
    go = deque(go)

    compress = {x: i for i, x in enumerate(xs, 1)}
    decompress = {i: x for i, x in enumerate(xs, 1)}

    ans = []
    b = BIT(N)
    for _ in range(Q):
        d = int(input())
        while go and go[0].time <= d:
            e = go.popleft()
            p = compress[e.position]
            b.add(p, -1)
        while stop and stop[0].time <= d:
            e = stop.popleft()
            p = compress[e.position]
            b.add(p, 1)

        compressed_ind = b.binary_search(1)
        ind = decompress.get(compressed_ind, -1)
        ans.append(ind)

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


if __name__ == '__main__':
    main()


Fixed submission:
# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')

Buggy python submission (verdict: Time Limit Exceeded):
class BIT:
    def __init__(self, N):
        self.tree = [0] * (N + 1)  # 1-indexed
        self.N = N

    def add(self, i, x):
        """tree[i]と関連個所にxを加える"""
        tree = self.tree
        N = self.N
        while i <= N:
            tree[i] += x
            i += i & (-i)

    def sum(self, i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & (-i)
        return s

    def binary_search(self, x):
        """区間和 >=x となる最小のindex"""
        tree = self.tree
        N = self.N
        i = 0
        step = 1 << (N.bit_length() - 1)
        while step:
            if i + step <= N and tree[i + step] < x:
                i += step
                x -= tree[i]
            step >>= 1
        return i + 1


def main():
    from collections import deque, namedtuple
    from operator import attrgetter
    import sys

    input = sys.stdin.readline
    Event = namedtuple('Event', 'time typ position')

    GO = 0
    STOP = 1

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

    works = []
    xs = set()
    for _ in range(N):
        s, t, x = map(int, input().split())
        e1 = Event(time=s - x, typ=STOP, position=x)
        e2 = Event(time=t - x, typ=GO, position=x)
        works.append(e1)
        works.append(e2)
        xs.add(x)

    xs = sorted(xs)

    works.sort(key=attrgetter('time', 'typ'))
    works = deque(works)

    compress = {x: i for i, x in enumerate(xs, 1)}
    decompress = {i: x for i, x in enumerate(xs, 1)}

    ans = []
    b = BIT(N)
    for _ in range(Q):
        d = int(input())
        while works and works[0].time <= d:
            e = works.popleft()
            p = compress[e.position]
            if e.typ == GO:
                b.add(p, -1)
            else:
                # STOP
                b.add(p, 1)

        compressed_ind = b.binary_search(1)
        ind = decompress.get(compressed_ind, -1)
        ans.append(ind)

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


if __name__ == '__main__':
    main()


Fixed submission:
# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')

Buggy python submission (verdict: Time Limit Exceeded):
class BIT:
    def __init__(self, N):
        self.tree = [0] * (N + 1)  # 1-indexed
        self.N = N

    def add(self, i, x):
        """tree[i]と関連個所にxを加える"""
        tree = self.tree
        N = self.N
        while i <= N:
            tree[i] += x
            i += i & (-i)

    def sum(self, i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & (-i)
        return s

    def binary_search(self, x):
        """区間和 >=x となる最小のindex"""
        tree = self.tree
        N = self.N
        i = 0
        step = 1 << (N.bit_length() - 1)
        while step:
            if i + step <= N and tree[i + step] < x:
                i += step
                x -= tree[i]
            step >>= 1
        return i + 1


def main():
    from collections import deque, namedtuple
    from operator import attrgetter
    import sys

    input = sys.stdin.readline
    Event = namedtuple('Event', 'time typ position')

    GO = 0
    STOP = 1

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

    works = []
    xs = set()
    for _ in range(N):
        s, t, x = map(int, input().split())
        e1 = Event(time=s - x, typ=STOP, position=x)
        e2 = Event(time=t - x, typ=GO, position=x)
        works.append(e1)
        works.append(e2)
        xs.add(x)

    xs = sorted(xs)

    works.sort(key=attrgetter('time', 'typ'))
    works = deque(works)

    compress = {x: i for i, x in enumerate(xs, 1)}
    decompress = {i: x for i, x in enumerate(xs, 1)}

    ans = []
    b = BIT(N)
    for _ in range(Q):
        d = int(input())
        while works and works[0].time <= d:
            e = works.popleft()
            p = compress[e.position]
            if e.typ == GO:
                b.add(p, -1)
            else:
                # STOP
                b.add(p, 1)

        compressed_ind = b.binary_search(1)
        ind = decompress.get(compressed_ind, -1)
        ans.append(ind)

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


if __name__ == '__main__':
    main()


Fixed submission:
# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')

Buggy python submission (verdict: Runtime Error):
# https://atcoder.jp/contests/abc128/submissions/8312583
# 写経

def solve():
    from heapq import heappush, heappop
    from collections import defaultdict
    from operator import itemgetter
    import sys

    input = sys.stdin.readline

    inf = 1 << 31

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

    S = [0] * n
    T = [0] * n
    X = [0] * n
    for i in range(n):
        S[i], T[i], X[i] = map(int, input().split())

    e = [*((t - x, 0, x) for t, x in zip(T, X)),
         *((s - x, 1, x) for s, x in zip(S, X)),
         *((int(input()), 2, idx) for idx in range(q))
         ]
    e.sort(key=itemgetter(0))
    # 安定ソートなので、0,1,2順になる（はず

    cnt = defaultdict(int)
    cnt[inf] = 1
    h = [inf]
    ret = [-1] * q
    for time, type, x in e:
        if type == 0:
            cnt[x] -= 1
        elif type == 1:
            heappush(h, x)
            cnt[x] += 1
        else:
            while not (cnt[h[0]]):
                heappop(h)
            curr = h[0]
            if curr != inf:
                ret[x] = curr

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


if __name__ == '__main__':
    solve()


Fixed submission:
# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')

Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc128/submissions/8312583
# 写経

def solve():
    from heapq import heappush, heappop
    from collections import defaultdict
    from operator import itemgetter
    import sys

    input = sys.stdin.readline

    inf = 1 << 31

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

    e = []  # 通行止めと解除にクエリ分割
    for _ in range(n):
        s, t, x = map(int, input().split())
        # 区間[s, t)に通行止め
        e.append((t - x, 0, x))  # 通行止め解除/0にすることで、解除と開始が同時刻の場合、先に解除される
        e.append((s - x, 1, x))  # 通行止め開始/1にすることで、同上

    for i in range(q):
        d = int(input())
        e.append((d, 2, i))  # 求値クエリ/2にすることで、通行止めの設定解除の反映後に到着する

    e.sort(key=itemgetter(0, 1))

    cnt = defaultdict(int)
    cnt[inf] = 1
    h = [inf]

    ret = [-1] * q
    for time, type, x in e:
        if type == 0:
            cnt[x] -= 1
        elif type == 1:
            heappush(h, x)
            cnt[x] += 1
        else:
            while not (cnt[h[0]]):
                heappop(h)
            curr = h[0]
            if curr != inf:
                ret[x] = curr

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


if __name__ == '__main__':
    solve()


Fixed submission:
# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')

Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    from collections import defaultdict
    from operator import itemgetter
    import sys

    input = sys.stdin.readline

    inf = 1 << 31

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

    e = []  # 通行止めと解除にクエリ分割
    for _ in range(n):
        s, t, x = map(int, input().split())
        # 区間[s, t)に通行止め
        e.append((t - x, 0, x))  # 通行止め解除/0にすることで、解除と開始が同時刻の場合、先に解除される
        e.append((s - x, 1, x))  # 通行止め開始/1にすることで、同上

    for _ in range(q):
        d = int(input())
        e.append((d, 2, -1))  # 求値クエリ/2にすることで、通行止めの設定解除の反映後に到着する

    e.sort(key=itemgetter(0, 1))

    stop_cnt = defaultdict(int)
    stop_cnt[inf] = 1
    stop_set = {inf}
    curr = inf

    ret = []
    for time, type, x in e:
        if type == 0:
            stop_cnt[x] -= 1
            if not stop_cnt[x]:
                stop_set.discard(x)
                if curr == x:
                    curr = min(stop_set)
        elif type == 1:
            stop_cnt[x] += 1
            if stop_cnt[x] == 1:
                stop_set.add(x)
            if x < curr:
                curr = x
        else:
            if curr == inf:
                ret.append(-1)
            else:
                ret.append(curr)

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


if __name__ == '__main__':
    solve()


Fixed submission:
# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')

Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    from collections import defaultdict, namedtuple
    from operator import attrgetter
    import sys

    input = sys.stdin.readline
    Event = namedtuple('Event', 'time type x_coordinate')

    inf = 1 << 31

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

    e = []  # 通行止めと解除にクエリ分割
    for _ in range(n):
        s, t, x = map(int, input().split())
        # 区間[s, t)に通行止め
        e.append(Event(t - x, 0, x))  # 通行止め解除/0にすることで、解除と開始が同時刻の場合、先に解除される
        e.append(Event(s - x, 1, x))  # 通行止め開始/1にすることで、同上

    for _ in range(q):
        d = int(input())
        e.append(Event(d, 2, -1))  # 求値クエリ/2にすることで、通行止めの設定解除の反映後に到着する

    e.sort(key=attrgetter('time', 'type'))

    stop_cnt = defaultdict(int)
    stop_cnt[inf] = 1
    stop_set = {inf}
    curr = inf

    for evt in e:
        if evt.type == 0:
            stop_cnt[evt.x_coordinate] -= 1
            if not stop_cnt[evt.x_coordinate]:
                stop_set.discard(evt.x_coordinate)
                if curr == evt.x_coordinate:
                    curr = min(stop_set)
        elif evt.type == 1:
            stop_cnt[evt.x_coordinate] += 1
            if stop_cnt[evt.x_coordinate] == 1:
                stop_set.add(evt.x_coordinate)
            if evt.x_coordinate < curr:
                curr = evt.x_coordinate
        else:
            if curr == inf:
                print(-1)
            else:
                print(curr)


if __name__ == '__main__':
    solve()


Fixed submission:
# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')

Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    from collections import defaultdict, namedtuple
    from operator import attrgetter
    import sys

    input = sys.stdin.readline
    Event = namedtuple('Event', 'time type x_coordinate')

    inf = 1 << 31

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

    e = []  # 通行止めと解除にクエリ分割
    for _ in range(n):
        s, t, x = map(int, input().split())
        # 区間[s, t)に通行止め
        e.append(Event(t - x, 0, x))  # 通行止め解除/0にすることで、解除と開始が同時刻の場合、先に解除される
        e.append(Event(s - x, 1, x))  # 通行止め開始/1にすることで、同上

    for _ in range(q):
        d = int(input())
        e.append(Event(d, 2, -1))  # 求値クエリ/2にすることで、通行止めの設定解除の反映後に到着する

    e.sort(key=attrgetter('time', 'type'))

    stop_cnt = defaultdict(int)
    stop_cnt[inf] = 1
    stop_set = {inf}
    curr = inf

    for evt in e:
        if evt.type == 0:
            stop_cnt[evt.x_coordinate] -= 1
            if not stop_cnt[evt.x_coordinate]:
                stop_set.discard(evt.x_coordinate)
                if curr == evt.x_coordinate:
                    curr = min(stop_set)
        elif evt.type == 1:
            stop_cnt[evt.x_coordinate] += 1
            if stop_cnt[evt.x_coordinate] == 1:
                stop_set.add(evt.x_coordinate)
            if evt.x_coordinate < curr:
                curr = evt.x_coordinate
        else:
            if curr == inf:
                print(-1)
            else:
                print(curr)


if __name__ == '__main__':
    solve()


Fixed submission:
# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')

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

input = sys.stdin.readline

inf = float('inf')

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

es = []
for _ in range(N):
    s, t, x = map(int, input().split())
    es.append((s - x, 1, x))
    es.append((t - x, 0, x))

for _ in range(Q):
    es.append((int(input()), 2, -1))

es.sort(key=lambda x: (x[0], x[1]))
st = set()
cur_min_stop = inf
check_needed = True
d_cnt = 0
for time, typ, pos in es:
    if typ == 1:
        st.add(pos)
        if pos < cur_min_stop:
            cur_min_stop = pos
    elif typ == 0:
        st.remove(pos)
        if pos == cur_min_stop:
            check_needed = True
    else:
        if check_needed:
            if st:
                cur_min_stop = min(st)
            else:
                cur_min_stop = inf
            check_needed = False
        print(cur_min_stop if cur_min_stop < inf else -1)
        d_cnt += 1
        if d_cnt == Q:
            break


Fixed submission:
# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')

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

input = sys.stdin.readline

inf = float('inf')

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

es = []
for _ in range(N):
    s, t, x = map(int, input().split())
    es.append((s - x, 1, x))
    es.append((t - x, 0, x))

for _ in range(Q):
    es.append((int(input()), 2, -1))

es.sort(key=lambda x: (x[0], x[1]))
st = set()
cur_min_stop = inf
check_needed = True
d_cnt = 0
for i, (time, typ, pos) in enumerate(es):
    # print(es)
    # print(st)
    # print(i, (time, typ, pos))
    if typ == 1:
        st.add(pos)
        if pos < cur_min_stop:
            cur_min_stop = pos
    elif typ == 0:
        st.remove(pos)
        if pos == cur_min_stop:
            check_needed = True
    else:
        if check_needed:
            if st:
                cur_min_stop = min(st)
            else:
                cur_min_stop = inf
            check_needed = False
        print(cur_min_stop if cur_min_stop < inf else -1)
        d_cnt += 1
        if d_cnt == Q:
            break


Fixed submission:
# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')

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

input = sys.stdin.readline

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

es = []
for _ in range(N):
    s, t, x = map(int, input().split())
    es.append((s - x, 1, x))
    es.append((t - x, 0, x))

for _ in range(Q):
    d = int(input())
    es.append((d, 2, -1))

es.sort(key=lambda x: (x[0], x[1]))
st = set()
cur_min_stop = -1
check_needed = True
d_cnt = 0
for i, (time, typ, pos) in enumerate(es):
    # print(es)
    # print(st)
    # print(i, (time, typ, pos))
    if typ == 1:
        st.add(pos)
        if cur_min_stop == -1 or pos < cur_min_stop:
            cur_min_stop = pos
    elif typ == 0:
        st.remove(pos)
        if pos == cur_min_stop:
            check_needed = True
    else:
        if check_needed:
            if st:
                cur_min_stop = min(st)
            else:
                cur_min_stop = -1
            check_needed = False
        print(cur_min_stop)
        d_cnt += 1
        if d_cnt == Q:
            break


Fixed submission:
# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')

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

input = sys.stdin.readline

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

es = []
for _ in range(N):
    s, t, x = map(int, input().split())
    es.append((s - x, 1, x))
    es.append((t - x, 0, x))

for _ in range(Q):
    d = int(input())
    es.append((d, 2, -1))

es.sort(key=lambda x: (x[0], x[1]))
st = set()
cur_min_stop = -1
check_needed = True
for i, (time, typ, pos) in enumerate(es):
    # print(es)
    # print(st)
    # print(i, (time, typ, pos))
    if typ == 1:
        st.add(pos)
        if cur_min_stop == -1 or pos < cur_min_stop:
            cur_min_stop = pos
    elif typ == 0:
        st.remove(pos)
        if pos == cur_min_stop:
            check_needed = True
    else:
        if check_needed:
            if st:
                cur_min_stop = min(st)
            else:
                cur_min_stop = -1
            check_needed = False
        print(cur_min_stop)


Fixed submission:
# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')

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

es = []
for _ in range(N):
    s, t, x = map(int, input().split())
    es.append((s - x, 1, x))
    es.append((t - x, 0, x))

for _ in range(Q):
    d = int(input())
    es.append((d, 2, -1))

es.sort(key=lambda x: (x[0], x[1]))
st = set()
cur_min_stop = -1
check_needed = True
for i, (time, typ, pos) in enumerate(es):
    # print(es)
    # print(st)
    # print(i, (time, typ, pos))
    if typ == 1:
        st.add(pos)
        if cur_min_stop == -1 or pos < cur_min_stop:
            cur_min_stop = pos
    elif typ == 0:
        st.remove(pos)
        if pos == cur_min_stop:
            check_needed = True
    else:
        if check_needed:
            if st:
                cur_min_stop = min(st)
            else:
                cur_min_stop = -1
            check_needed = False
        print(cur_min_stop)


Fixed submission:
# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')

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

input = sys.stdin.readline

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

events = []

for _ in range(N):
    s, t, x = map(int, input().split())
    add_event = (s - x, 1, x)
    remove_event = (t - x, -1, x)
    events.append(add_event)
    events.append(remove_event)

events.sort(key=itemgetter(0))  # イベント処理時刻昇順ソート

under_construction = set()

cur = 0
for _ in range(Q):
    d = int(input())
    # print('d', d)
    while cur < N * 2 and events[cur][0] <= d:
        exec_time, event_type, under_construction_x = events[cur]
        # print(cur, exec_time, event_type, under_construction_x)
        if event_type == 1:
            # add_event
            under_construction.add(under_construction_x)
        else:
            # remove_event
            under_construction.discard(under_construction_x)
        cur += 1
    # print('cur', cur, 'events', events)
    # print('uc', under_construction)
    print(min(under_construction) if under_construction else -1)

    # print()


Fixed submission:
# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')

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

input = sys.stdin.readline

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

events = []

for _ in range(N):
    s, t, x = map(int, input().split())
    add_event = (s - x, 1, x)
    remove_event = (t - x, -1, x)
    events.append(add_event)
    events.append(remove_event)

events.sort(key=itemgetter(0))  # イベント処理時刻昇順ソート

under_construction = set()

cur = 0
for _ in range(Q):
    d = int(input())
    # print('d', d)
    while cur < N * 2 and events[cur][0] <= d:
        exec_time, event_type, under_construction_x = events[cur]
        # print(cur, exec_time, event_type, under_construction_x)
        if event_type == 1:
            # add_event
            under_construction.add(under_construction_x)
        else:
            # remove_event
            under_construction.discard(under_construction_x)
        cur += 1
    # print('cur', cur, 'events', events)
    # print('uc', under_construction)
    print(min(under_construction) if under_construction else -1)

    # print()


Fixed submission:
# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')

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

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

events = []

for _ in range(N):
    s, t, x = map(int, input().split())
    add_event = (s - x, 1, x)
    remove_event = (t - x, -1, x)
    events.append(add_event)
    events.append(remove_event)

events.sort(key=itemgetter(0))  # イベント処理時刻昇順ソート

under_construction = set()

cur = 0
for _ in range(Q):
    d = int(input())
    # print('d', d)
    while cur < N * 2 and events[cur][0] <= d:
        exec_time, event_type, under_construction_x = events[cur]
        # print(cur, exec_time, event_type, under_construction_x)
        if event_type == 1:
            # add_event
            under_construction.add(under_construction_x)
        else:
            # remove_event
            under_construction.discard(under_construction_x)
        cur += 1
    # print('cur', cur, 'events', events)
    # print('uc', under_construction)
    print(min(under_construction) if under_construction else -1)

    # print()


Fixed submission:
# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')