Buggy python submission (verdict: Runtime Error):
from heapq import heappush, heappop, merge
from collections import defaultdict
import sys
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    events = []
    for _ in range(N):
        s, t, x = map(int, line_input())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    for _ in range(Q):
        d = int(single_input)
        events.append((d, 2, d))
    events = sorted(events)

    constructions = []
    under_construction = defaultdict(bool)
    ans = ''
    for _, flag, coord in events:
        if flag == 1:
            heappush(constructions, coord)
            under_construction[coord] = True
        elif flag == -1:
            under_construction[coord] = False
        else:
            while constructions:
                x = heappop(constructions)
                if under_construction[x]: # x is the minimum coordinate under construction
                    heappush(constructions, x)
                    ans += str(x) + '\n'
                    break
            else: # no constructions
                ans += '-1\n'
    print(ans)
    
if __name__ == "__main__":
    solve()

Fixed submission:
from heapq import heappush, heappop, merge
from collections import defaultdict
import sys
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    events = []
    for _ in range(N):
        s, t, x = map(int, line_input())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    for _ in range(Q):
        d = int(single_input())
        events.append((d, 2, d))
    events = sorted(events)

    constructions = []
    under_construction = defaultdict(bool)
    ans = ''
    for _, flag, coord in events:
        if flag == 1:
            heappush(constructions, coord)
            under_construction[coord] = True
        elif flag == -1:
            under_construction[coord] = False
        else:
            while constructions:
                x = heappop(constructions)
                if under_construction[x]: # x is the minimum coordinate under construction
                    heappush(constructions, x)
                    ans += str(x) + '\n'
                    break
            else: # no constructions
                ans += '-1\n'
    print(ans)
    
if __name__ == "__main__":
    solve()

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

def solve():
    N, Q = map(int, input().split())
    events = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    for _ in range(Q):
        d = int(input())
        events.append((d, 2, d))
    events = sorted(events)

    constructions = []
    under_construction = defaultdict(bool)
    ans = ''
    for _, flag, coord in events:
        if flag == 1:
            heappush(constructions, coord)
            under_construction[coord] = True
        elif flag == -1:
            under_construction[coord] = False
        else:
            while constructions:
                x = heappop(constructions)
                if under_construction[x]: # x is the minimum coordinate under construction
                    heappush(constructions, x)
                    ans += str(x) + '\n'
                    break
            else: # no constructions
                ans += '-1\n'
    print(ans)
    
if __name__ == "__main__":
    solve()

Fixed submission:
from heapq import heappush, heappop, merge
from collections import defaultdict
import sys
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    events = []
    for _ in range(N):
        s, t, x = map(int, line_input())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    for _ in range(Q):
        d = int(single_input())
        events.append((d, 2, d))
    events = sorted(events)

    constructions = []
    under_construction = defaultdict(bool)
    ans = ''
    for _, flag, coord in events:
        if flag == 1:
            heappush(constructions, coord)
            under_construction[coord] = True
        elif flag == -1:
            under_construction[coord] = False
        else:
            while constructions:
                x = heappop(constructions)
                if under_construction[x]: # x is the minimum coordinate under construction
                    heappush(constructions, x)
                    ans += str(x) + '\n'
                    break
            else: # no constructions
                ans += '-1\n'
    print(ans)
    
if __name__ == "__main__":
    solve()

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

N, Q = map(int, input().split())
events = []
for _ in range(N):
    s, t, x = map(int, input().split())
    events.append((s-x, 1, x))
    events.append((t-x, -1, x))
for _ in range(Q):
    d = int(input())
    events.append((d, 2, d))
events = sorted(events)

constructions = []
under_construction = defaultdict(bool)
ans = ''
for _, flag, coord in events:
    if flag == 1:
        heappush(constructions, coord)
        under_construction[coord] = True
    elif flag == -1:
        under_construction[coord] = False
    else:
        while constructions:
            x = heappop(constructions)
            if under_construction[x]: # x is the minimum coordinate under construction
                heappush(constructions, x)
                ans += str(x) + '\n'
                break
        else: # no constructions
            ans += '-1\n'
print(ans)

Fixed submission:
from heapq import heappush, heappop, merge
from collections import defaultdict
import sys
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    events = []
    for _ in range(N):
        s, t, x = map(int, line_input())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    for _ in range(Q):
        d = int(single_input())
        events.append((d, 2, d))
    events = sorted(events)

    constructions = []
    under_construction = defaultdict(bool)
    ans = ''
    for _, flag, coord in events:
        if flag == 1:
            heappush(constructions, coord)
            under_construction[coord] = True
        elif flag == -1:
            under_construction[coord] = False
        else:
            while constructions:
                x = heappop(constructions)
                if under_construction[x]: # x is the minimum coordinate under construction
                    heappush(constructions, x)
                    ans += str(x) + '\n'
                    break
            else: # no constructions
                ans += '-1\n'
    print(ans)
    
if __name__ == "__main__":
    solve()

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

N, Q = map(int, input().split())
events = []
for _ in range(N):
    s, t, x = map(int, input().split())
    events.append((s-x, 1, x))
    events.append((t-x, -1, x))
events = deque(sorted(events))
D = [int(input()) for _ in range(Q)]

constructions = []
under_construction = defaultdict(bool)
ans = ''
for d in D:
    while events:
        if events[0][0] > d:
            break
        _, flag, coord = events.popleft()            
        if flag > 0:
            heappush(constructions, coord)
            under_construction[coord] = True
        else:
            under_construction[coord] = False
    while constructions:
        x = heappop(constructions)
        if under_construction[x]: # x is the minimum coordinate under construction
            heappush(constructions, x)
            ans += str(x) + '\n'
            break
    else: # no constructions
        ans += '-1\n'
print(ans)

Fixed submission:
from heapq import heappush, heappop, merge
from collections import defaultdict
import sys
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    events = []
    for _ in range(N):
        s, t, x = map(int, line_input())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    for _ in range(Q):
        d = int(single_input())
        events.append((d, 2, d))
    events = sorted(events)

    constructions = []
    under_construction = defaultdict(bool)
    ans = ''
    for _, flag, coord in events:
        if flag == 1:
            heappush(constructions, coord)
            under_construction[coord] = True
        elif flag == -1:
            under_construction[coord] = False
        else:
            while constructions:
                x = heappop(constructions)
                if under_construction[x]: # x is the minimum coordinate under construction
                    heappush(constructions, x)
                    ans += str(x) + '\n'
                    break
            else: # no constructions
                ans += '-1\n'
    print(ans)
    
if __name__ == "__main__":
    solve()

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

N, Q = map(int, input().split())
events = []
for _ in range(N):
    s, t, x = map(int, input().split())
    events.append((s-x, 1, x))
    events.append((t-x, -1, x))
events = deque(sorted(events))
D = []
for _ in range(Q):
    D.append(int(input()))

constructions = []
under_construction = defaultdict(bool)
ans = ''
for d in D:
    while events:
        if events[0][0] > d:
            break
        _, flag, coord = events.popleft()            
        if flag > 0:
            heappush(constructions, coord)
            under_construction[coord] = True
        else:
            under_construction[coord] = False
    while constructions:
        x = heappop(constructions)
        if under_construction[x]: # x is the minimum coordinate under construction
            heappush(constructions, x)
            ans += str(x) + '\n'
            break
    else: # no constructions
        ans += '-1\n'
print(ans)

Fixed submission:
from heapq import heappush, heappop, merge
from collections import defaultdict
import sys
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    events = []
    for _ in range(N):
        s, t, x = map(int, line_input())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    for _ in range(Q):
        d = int(single_input())
        events.append((d, 2, d))
    events = sorted(events)

    constructions = []
    under_construction = defaultdict(bool)
    ans = ''
    for _, flag, coord in events:
        if flag == 1:
            heappush(constructions, coord)
            under_construction[coord] = True
        elif flag == -1:
            under_construction[coord] = False
        else:
            while constructions:
                x = heappop(constructions)
                if under_construction[x]: # x is the minimum coordinate under construction
                    heappush(constructions, x)
                    ans += str(x) + '\n'
                    break
            else: # no constructions
                ans += '-1\n'
    print(ans)
    
if __name__ == "__main__":
    solve()

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

N, Q = map(int, input().split())
events = []
for _ in range(N):
    s, t, x = map(int, input().split())
    events.append((s-x, 1, x))
    events.append((t-x, -1, x))
events = deque(sorted(events))
D = []
for _ in range(Q):
    D.append(int(input()))

constructions = []
under_construction = defaultdict(bool)
i = 0
for d in D:
    while events:
        if events[0][0] > d:
            break
        _, flag, coord = events.popleft()            
        if flag > 0:
            heappush(constructions, coord)
            under_construction[coord] = True
        else:
            under_construction[coord] = False
    while constructions:
        x = heappop(constructions)
        if under_construction[x]: # x is the minimum coordinate under construction
            heappush(constructions, x)
            print(x)
            break
    else: # no constructions
        print(-1)

Fixed submission:
from heapq import heappush, heappop, merge
from collections import defaultdict
import sys
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    events = []
    for _ in range(N):
        s, t, x = map(int, line_input())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    for _ in range(Q):
        d = int(single_input())
        events.append((d, 2, d))
    events = sorted(events)

    constructions = []
    under_construction = defaultdict(bool)
    ans = ''
    for _, flag, coord in events:
        if flag == 1:
            heappush(constructions, coord)
            under_construction[coord] = True
        elif flag == -1:
            under_construction[coord] = False
        else:
            while constructions:
                x = heappop(constructions)
                if under_construction[x]: # x is the minimum coordinate under construction
                    heappush(constructions, x)
                    ans += str(x) + '\n'
                    break
            else: # no constructions
                ans += '-1\n'
    print(ans)
    
if __name__ == "__main__":
    solve()

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

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

    constructions = []
    under_construction = defaultdict(bool)
    i = 0
    for _ in range(Q):
        d = int(input())
        while i < 2*N and events[i][0] <= d:
            if events[i][1] > 0:
                heappush(constructions, events[i][2])
                under_construction[events[i][2]] = True
            else:
                under_construction[events[i][2]] = False
            i += 1
        while constructions:
            x = heappop(constructions)
            if under_construction[x]: # x is the minimum coordinate under construction
                heappush(constructions, x)
                print(x)
                break
        else: # no constructions
            print(-1)

if __name__ == "__main__":
    solve()

Fixed submission:
from heapq import heappush, heappop, merge
from collections import defaultdict
import sys
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    events = []
    for _ in range(N):
        s, t, x = map(int, line_input())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    for _ in range(Q):
        d = int(single_input())
        events.append((d, 2, d))
    events = sorted(events)

    constructions = []
    under_construction = defaultdict(bool)
    ans = ''
    for _, flag, coord in events:
        if flag == 1:
            heappush(constructions, coord)
            under_construction[coord] = True
        elif flag == -1:
            under_construction[coord] = False
        else:
            while constructions:
                x = heappop(constructions)
                if under_construction[x]: # x is the minimum coordinate under construction
                    heappush(constructions, x)
                    ans += str(x) + '\n'
                    break
            else: # no constructions
                ans += '-1\n'
    print(ans)
    
if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Runtime Error):
from heapq import heappush, heappop, merge
from collections import defaultdict

def solve():
  N, Q = map(int, input().split())
  events = []
  for _ in range(N):
    s, t, x = map(int, input().split())
    events.append((s-x, 1, x))
    events.append((t-x, -1, x))
    events = sorted(events)

    constructions = []
    under_construction = defaultdict(bool)
    i = 0
    for _ in range(Q):
      d = int(input())
      while i < 2*N and events[i][0] <= d:
        if events[i][1] > 0:
          heappush(constructions, events[i][2])
          under_construction[events[i][2]] = True
        else:
          under_construction[events[i][2]] = False
        i += 1
      while constructions:
      	x = heappop(constructions)
        if under_construction[x]: # x is the minimum coordinate under construction
          heappush(constructions, x)
          print(x)
          break
      else: # no constructions
        print(-1)
        
if __name__ == "__main__":
  solve()

Fixed submission:
from heapq import heappush, heappop, merge
from collections import defaultdict
import sys
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    events = []
    for _ in range(N):
        s, t, x = map(int, line_input())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    for _ in range(Q):
        d = int(single_input())
        events.append((d, 2, d))
    events = sorted(events)

    constructions = []
    under_construction = defaultdict(bool)
    ans = ''
    for _, flag, coord in events:
        if flag == 1:
            heappush(constructions, coord)
            under_construction[coord] = True
        elif flag == -1:
            under_construction[coord] = False
        else:
            while constructions:
                x = heappop(constructions)
                if under_construction[x]: # x is the minimum coordinate under construction
                    heappush(constructions, x)
                    ans += str(x) + '\n'
                    break
            else: # no constructions
                ans += '-1\n'
    print(ans)
    
if __name__ == "__main__":
    solve()

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

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

constructions = []
under_construction = defaultdict(bool)
i = 0
for _ in range(Q):
    d = int(input())
    while i < 2*N and events[i][0] <= d:
        if events[i][1] > 0:
            heappush(constructions, events[i][2])
            under_construction[events[i][2]] = True
        else:
            under_construction[events[i][2]] = False
        i += 1
    while constructions:
        x = heappop(constructions)
        if under_construction[x]: # x is the minimum coordinate under construction
            heappush(constructions, x)
            print(x)
            break
    else: # no constructions
        print(-1)

Fixed submission:
from heapq import heappush, heappop, merge
from collections import defaultdict
import sys
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    events = []
    for _ in range(N):
        s, t, x = map(int, line_input())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    for _ in range(Q):
        d = int(single_input())
        events.append((d, 2, d))
    events = sorted(events)

    constructions = []
    under_construction = defaultdict(bool)
    ans = ''
    for _, flag, coord in events:
        if flag == 1:
            heappush(constructions, coord)
            under_construction[coord] = True
        elif flag == -1:
            under_construction[coord] = False
        else:
            while constructions:
                x = heappop(constructions)
                if under_construction[x]: # x is the minimum coordinate under construction
                    heappush(constructions, x)
                    ans += str(x) + '\n'
                    break
            else: # no constructions
                ans += '-1\n'
    print(ans)
    
if __name__ == "__main__":
    solve()

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

N, Q = map(int, input().split())
events = []
for _ in range(N):
    s, t, x = map(int, input().split())
    events.append((s-x, 1, x))
    events.append((t-x, -1, x))
events = sorted(events)
constructions = []
i = 0
for _ in range(Q):
    d = int(input())
    while i < 2*N and events[i][0] <= d:
        if events[i][1] > 0:
            heappush(constructions, events[i][2])
        else:
            temp = []
            while constructions[0] != events[i][2]:
                heappush(temp, heappop(constructions))
            heappop(constructions)
            constructions = list(merge(temp, constructions))
        i += 1
    print(constructions[0] if constructions else -1)

Fixed submission:
from heapq import heappush, heappop, merge
from collections import defaultdict
import sys
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    events = []
    for _ in range(N):
        s, t, x = map(int, line_input())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    for _ in range(Q):
        d = int(single_input())
        events.append((d, 2, d))
    events = sorted(events)

    constructions = []
    under_construction = defaultdict(bool)
    ans = ''
    for _, flag, coord in events:
        if flag == 1:
            heappush(constructions, coord)
            under_construction[coord] = True
        elif flag == -1:
            under_construction[coord] = False
        else:
            while constructions:
                x = heappop(constructions)
                if under_construction[x]: # x is the minimum coordinate under construction
                    heappush(constructions, x)
                    ans += str(x) + '\n'
                    break
            else: # no constructions
                ans += '-1\n'
    print(ans)
    
if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Runtime Error):
from heapq import heappush, heappop, merge

N, Q = map(int, input().split())
events = []
for _ in range(N):
    s, t, x = map(int, input().split())
    events.append((s-x, 1, x))
    events.append((t-x, -1, x))
events = sorted(events)
constructions = []
i = 0
for _ in range(Q):
    d = int(input())
    while i < 2*N and events[i][0] <= d:
        if events[i][1] > 0:
            heappush(constructions, events[i][2])
        else:
            temp = []
            while constructions[0] != events[i][2]:
                heappush(temp, heappop(constructions))
            heappop(constructions)
            constructions = list(merge([temp, constructions]))
        i += 1
    print(constructions[0] if constructions else -1)

Fixed submission:
from heapq import heappush, heappop, merge
from collections import defaultdict
import sys
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    events = []
    for _ in range(N):
        s, t, x = map(int, line_input())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    for _ in range(Q):
        d = int(single_input())
        events.append((d, 2, d))
    events = sorted(events)

    constructions = []
    under_construction = defaultdict(bool)
    ans = ''
    for _, flag, coord in events:
        if flag == 1:
            heappush(constructions, coord)
            under_construction[coord] = True
        elif flag == -1:
            under_construction[coord] = False
        else:
            while constructions:
                x = heappop(constructions)
                if under_construction[x]: # x is the minimum coordinate under construction
                    heappush(constructions, x)
                    ans += str(x) + '\n'
                    break
            else: # no constructions
                ans += '-1\n'
    print(ans)
    
if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Runtime Error):
from heapq import heappush, heappop, merge

N, Q = map(int, input().split())
events = []
for _ in range(N):
    s, t, x = map(int, input().split())
    events.append((s-x, 1, x))
    events.append((t-x, -1, x))
events = sorted(events)
constructions = []
i = 0
for _ in range(Q):
    d = int(input())
    while i < 2*N and events[i][0] <= d:
        if events[i][1] > 0:
            heappush(constructions, events[i][2])
        else:
            temp = []
            while constructions[0] != events[i][2]:
                heappush(temp, heappop(constructions))
            heappop(constructions)
            merge([temp, constructions])
        i += 1
    print(constructions[0] if constructions else -1)

Fixed submission:
from heapq import heappush, heappop, merge
from collections import defaultdict
import sys
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    events = []
    for _ in range(N):
        s, t, x = map(int, line_input())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    for _ in range(Q):
        d = int(single_input())
        events.append((d, 2, d))
    events = sorted(events)

    constructions = []
    under_construction = defaultdict(bool)
    ans = ''
    for _, flag, coord in events:
        if flag == 1:
            heappush(constructions, coord)
            under_construction[coord] = True
        elif flag == -1:
            under_construction[coord] = False
        else:
            while constructions:
                x = heappop(constructions)
                if under_construction[x]: # x is the minimum coordinate under construction
                    heappush(constructions, x)
                    ans += str(x) + '\n'
                    break
            else: # no constructions
                ans += '-1\n'
    print(ans)
    
if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
events = []
for _ in range(N):
    s, t, x = map(int, input().split())
    events.append((s-x, 1, x))
    events.append((t-x, -1, x))
events = sorted(events)
constructions = set([])
i = 0
for _ in range(Q):
    d = int(input())
    while i < 2*N and events[i][0] <= d:
        if events[i][1] > 0:
            constructions |= {events[i][2]}
        else:
            constructions -= {events[i][2]}
        i += 1
    print(min(constructions) if constructions else -1)

Fixed submission:
from heapq import heappush, heappop, merge
from collections import defaultdict
import sys
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    events = []
    for _ in range(N):
        s, t, x = map(int, line_input())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    for _ in range(Q):
        d = int(single_input())
        events.append((d, 2, d))
    events = sorted(events)

    constructions = []
    under_construction = defaultdict(bool)
    ans = ''
    for _, flag, coord in events:
        if flag == 1:
            heappush(constructions, coord)
            under_construction[coord] = True
        elif flag == -1:
            under_construction[coord] = False
        else:
            while constructions:
                x = heappop(constructions)
                if under_construction[x]: # x is the minimum coordinate under construction
                    heappush(constructions, x)
                    ans += str(x) + '\n'
                    break
            else: # no constructions
                ans += '-1\n'
    print(ans)
    
if __name__ == "__main__":
    solve()