Buggy python submission (verdict: Time Limit Exceeded):
from ctypes import *
import subprocess as sp
from operator import itemgetter
import sys
import os.path

set_code = r"""
#include <set>

std::set<int> s;

void add(int x) {
    s.insert(x);
}

bool find(int x) {
    return s.find(x) != s.end();
}

void remove(int x) {
    s.erase(x);
}

bool empty() {
	return s.empty();
}

int getMin() {
	return *s.begin();
}
"""

class CppSet:
	counter = 0

	def __init__(self):
		lib_name = './hoge{}.so'.format(CppSet.counter)

		code_file_name = "tmp.cpp"
		with open(code_file_name, "w") as f:
			f.write(set_code)

		CppSet.counter += 1
		sp.Popen(['g++', '-fPIC', '-shared', '-std=c++11', code_file_name, '-o', lib_name]).communicate()

		lib = CDLL(lib_name)
		self.add = getattr(lib, "_Z3addi")
		self.find = CFUNCTYPE(c_bool, c_int)(
						("_Z4findi", lib),
						((1, "x"), )
					)
		self.remove = getattr(lib, "_Z6removei")
		self.empty = CFUNCTYPE(c_bool)(
						("_Z5emptyv", lib),
						()
					)

		self.getMin = CFUNCTYPE(c_int)(
						("_Z6getMinv", lib),
						()
					)

def main():
	N, Q = map(int, sys.stdin.readline().split())
	tmp = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
	stx = [(s - x, 1, x) for s, t, x in tmp] + [(t - x, -1, x) for s, t, x in tmp]
	stx.sort()
	
	D = [int(sys.stdin.readline()) for _ in range(Q)] 
	ans = [-1]*Q

	idx = 0
	stx_len = len(stx)
	se = CppSet()
	for i, d in enumerate(D):
		while idx < stx_len:
			t, com, x = stx[idx]
			if t > d:
				break
			if com == 1:
				se.add(x)
			else:
				se.remove(x)
			idx += 1
		ans[i] = (-1 if se.empty() else se.getMin())

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

if __name__ == "__main__":
	main()


Fixed submission:
from bisect import bisect, bisect_left
from collections import Counter
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

import sys
input = sys.stdin.readline

def inpl(): return list(map(int, input().split()))

class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.N = N
        self.tree = [0]*(self.N + 1)
        self.n = 1
        while self.n <= N:
            self.n *= 2
        self.n //= 2

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

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.N:
            self.tree[i] += x
            i += (i & -(i))

    def lower_bound(self, val):
        if val <= 0:
            return 0
        res = 0
        k = self.n
        while k:
            if res + k <= self.N and self.tree[res + k] < val:
                val -= self.tree[res + k]
                res += k
            k //= 2
        return res + 1

class DammyMap:

    def __init__(self, counter, INF=2**32):
        if type(counter) != Counter:
            counter = Counter(counter)

        self.bit = BIT(len(counter.keys())+3)
        self.key = sorted([-INF, -INF] + sorted(counter.keys()) + [INF])
        self.val = [counter[k] for k in self.key]
        S = list(accumulate(self.val))

        for i in range(len(self.key)):
            self.bit.tree[i] = S[i] - S[i - (i&-i)]
        for i in range(len(self.key), len(self.bit.tree)):
            j = i - (i&-i)
            if j < len(S):
                self.bit.tree[i] = S[-1] - S[i - (i&-i)]


    def add(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, 1)


    def update(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            self.bit.add(ix, v)


    def remove(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            
            # 空の値を削除しないかのチェック
            # 時間が厳しそうなときはコメントアウト
            assert self.bit.sum(ix) - self.bit.sum(ix-1) > 0

            self.bit.add(ix, -v)


    def pop_vals(self, l, r):
        assert l <= r

        rix = bisect(self.key, r) - 1
        lix = bisect_left(self.key, l) - 1
        # (lix, rix]になるのに注意
        rv = self.bit.sum(rix)
        lv = self.bit.sum(lix)
        delta = rv - lv
        tv = lv+1
        tix = lix*1

        vix = 0
        rmvix = 0
        vals = [0]*delta
        rmvk = [0]*delta
        rmvv = [0]*delta
        while delta:
            OK = self.bit.lower_bound(tv)
            c = self.bit.sum(OK)
            d = c - tv + 1
            for _ in range(d):
                vals[vix] = self.key[OK]
                vix += 1
            rmvk[rmvix] = OK
            rmvv[rmvix] = d
            rmvix += 1
            tv += d
            tix = OK
            delta -= d

        for i in range(rmvix):
            self.bit.add(rmvk[i], -rmvv[i])
        return vals

N, M = inpl()
Q = sorted([inpl() for _ in range(N)], key=itemgetter(2))
D = [int(input()) for _ in range(M)]
rD = {v:i for i, v in enumerate(D)}
ans = [-1]*(M)
 
dmap = DammyMap(D)
 
for s, t, x in Q:
    val = dmap.pop_vals(s-x, t-1-x)
    for v in val:
        ans[rD[v]] = x
 
print(*ans, sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
from ctypes import *
import subprocess as sp
from operator import itemgetter
import sys

set_code = r"""
#include <set>

std::set<int> s;

void add(int x) {
    s.insert(x);
}

bool find(int x) {
    return s.find(x) != s.end();
}

void remove(int x) {
    s.erase(x);
}

bool empty() {
	return s.empty();
}

int getMin() {
	return *s.begin();
}
"""

class CppSet:
	counter = 0

	def __init__(self):
		lib_name = './hoge{}.so'.format(CppSet.counter)
		code_file_name = "tmp.cpp"
		with open(code_file_name, "w") as f:
			f.write(set_code)

		CppSet.counter += 1
		sp.Popen(['g++', '-fPIC', '-shared', '-std=c++11', code_file_name, '-o', lib_name]).communicate()

		lib = CDLL(lib_name)
		self.add = getattr(lib, "_Z3addi")
		self.find = CFUNCTYPE(c_bool, c_int)(
						("_Z4findi", lib),
						((1, "x"), )
					)
		self.remove = getattr(lib, "_Z6removei")
		self.empty = CFUNCTYPE(c_bool)(
						("_Z5emptyv", lib),
						()
					)

		self.getMin = CFUNCTYPE(c_int)(
						("_Z6getMinv", lib),
						()
					)

def main():
	N, Q = map(int, sys.stdin.readline().split())
	tmp = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
	stx = [(s - x, 1, x) for s, t, x in tmp] + [(t - x, -1, x) for s, t, x in tmp]
	stx.sort()
	
	D = [int(sys.stdin.readline()) for _ in range(Q)] 
	ans = [-1]*Q

	idx = 0
	stx_len = len(stx)
	se = CppSet()
	for i, d in enumerate(D):
		while idx < stx_len:
			t, com, x = stx[idx]
			if t > d:
				break
			if com == 1:
				se.add(x)
			else:
				se.remove(x)
			idx += 1
		ans[i] = (-1 if se.empty() else se.getMin())

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

if __name__ == "__main__":
	main()


Fixed submission:
from bisect import bisect, bisect_left
from collections import Counter
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

import sys
input = sys.stdin.readline

def inpl(): return list(map(int, input().split()))

class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.N = N
        self.tree = [0]*(self.N + 1)
        self.n = 1
        while self.n <= N:
            self.n *= 2
        self.n //= 2

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

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.N:
            self.tree[i] += x
            i += (i & -(i))

    def lower_bound(self, val):
        if val <= 0:
            return 0
        res = 0
        k = self.n
        while k:
            if res + k <= self.N and self.tree[res + k] < val:
                val -= self.tree[res + k]
                res += k
            k //= 2
        return res + 1

class DammyMap:

    def __init__(self, counter, INF=2**32):
        if type(counter) != Counter:
            counter = Counter(counter)

        self.bit = BIT(len(counter.keys())+3)
        self.key = sorted([-INF, -INF] + sorted(counter.keys()) + [INF])
        self.val = [counter[k] for k in self.key]
        S = list(accumulate(self.val))

        for i in range(len(self.key)):
            self.bit.tree[i] = S[i] - S[i - (i&-i)]
        for i in range(len(self.key), len(self.bit.tree)):
            j = i - (i&-i)
            if j < len(S):
                self.bit.tree[i] = S[-1] - S[i - (i&-i)]


    def add(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, 1)


    def update(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            self.bit.add(ix, v)


    def remove(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            
            # 空の値を削除しないかのチェック
            # 時間が厳しそうなときはコメントアウト
            assert self.bit.sum(ix) - self.bit.sum(ix-1) > 0

            self.bit.add(ix, -v)


    def pop_vals(self, l, r):
        assert l <= r

        rix = bisect(self.key, r) - 1
        lix = bisect_left(self.key, l) - 1
        # (lix, rix]になるのに注意
        rv = self.bit.sum(rix)
        lv = self.bit.sum(lix)
        delta = rv - lv
        tv = lv+1
        tix = lix*1

        vix = 0
        rmvix = 0
        vals = [0]*delta
        rmvk = [0]*delta
        rmvv = [0]*delta
        while delta:
            OK = self.bit.lower_bound(tv)
            c = self.bit.sum(OK)
            d = c - tv + 1
            for _ in range(d):
                vals[vix] = self.key[OK]
                vix += 1
            rmvk[rmvix] = OK
            rmvv[rmvix] = d
            rmvix += 1
            tv += d
            tix = OK
            delta -= d

        for i in range(rmvix):
            self.bit.add(rmvk[i], -rmvv[i])
        return vals

N, M = inpl()
Q = sorted([inpl() for _ in range(N)], key=itemgetter(2))
D = [int(input()) for _ in range(M)]
rD = {v:i for i, v in enumerate(D)}
ans = [-1]*(M)
 
dmap = DammyMap(D)
 
for s, t, x in Q:
    val = dmap.pop_vals(s-x, t-1-x)
    for v in val:
        ans[rD[v]] = x
 
print(*ans, sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect, bisect_left
from collections import Counter
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

import sys
input = sys.stdin.readline

def inpl(): return list(map(int, input().split()))

class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.N = N
        self.tree = [0]*(self.N + 1)
        self.n = 1
        while self.n <= N:
            self.n *= 2
        self.n //= 2

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

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.N:
            self.tree[i] += x
            i += (i & -(i))

    def lower_bound(self, val):
        if val <= 0:
            return 0
        res = 0
        k = self.n
        while k:
            if res + k <= self.N and self.tree[res + k] < val:
                val -= self.tree[res + k]
                res += k
            k //= 2
        return res + 1
            
class OfflineSortedSet:
	
    def __init__(self, all_vals):
        self.keys = sorted(set(all_vals))
        self.max_key = max(self.keys)
        self.key_to_index = {k:i for i, k in enumerate(self.keys, start=1)}
        self.keys_num = len(self.keys)

        self.bit = BIT(self.keys_num)
        self.hash_set = set()

        self.add_bit = self.bit.add
        self.sum_bit = self.bit.sum
        self.lower_bound_bit = self.bit.lower_bound
        self.add_hash_set = self.hash_set.add
        self.remove_hash_set = self.hash_set.remove

    def exists(self, val):
        return val in self.hash_set

    def add(self, val):
        if val in self.hash_set:
            return
        
        self.add_hash_set(val)
        self.add_bit(self.key_to_index[val], 1)

    def remove(self, val):
        if val not in self.hash_set:
            return

        self.remove_hash_set(val)
        self.add_bit(self.key_to_index[val], -1)

    def lower_bound(self, val):
        idx = bisect_left(self.keys, val)
        tar = self.sum_bit(idx)
        res = self.lower_bound_bit(tar + 1) - 1
        if res < 0 or res >= self.keys_num:
            res = self.keys_num
        return res

def main():
    N, Q = inpl()
    hoge = [inpl() for _ in range(N)]
    X = [0]*N

    v = [0]*(2*N)
    for i in range(N):
        s, t, X[i] = hoge[i]
        v[2*i] = (s - X[i], 1, X[i])
        v[2*i+1] = (t - X[i], -1, X[i])
    v = sorted(v)

    se = OfflineSortedSet(X)
    del X

    idx = 0
    D = [int(input()) for _ in range(Q)]
    ans = [0]*Q
    for i, d in enumerate(D):
        while idx < len(v):
            t, com, x = v[idx]
            if t > d:
                break
            if com == 1:
                se.add(x)
            else:
                se.remove(x)
            idx += 1
        ans[i] = -1 if len(se.hash_set) == 0 else se.keys[se.lower_bound(-10000000000)]
    print(*ans, sep="\n")
    
if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect, bisect_left
from collections import Counter
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

import sys
input = sys.stdin.readline

def inpl(): return list(map(int, input().split()))

class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.N = N
        self.tree = [0]*(self.N + 1)
        self.n = 1
        while self.n <= N:
            self.n *= 2
        self.n //= 2

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

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.N:
            self.tree[i] += x
            i += (i & -(i))

    def lower_bound(self, val):
        if val <= 0:
            return 0
        res = 0
        k = self.n
        while k:
            if res + k <= self.N and self.tree[res + k] < val:
                val -= self.tree[res + k]
                res += k
            k //= 2
        return res + 1

class DammyMap:

    def __init__(self, counter, INF=2**32):
        if type(counter) != Counter:
            counter = Counter(counter)

        self.bit = BIT(len(counter.keys())+3)
        self.key = sorted([-INF, -INF] + sorted(counter.keys()) + [INF])
        self.val = [counter[k] for k in self.key]
        S = list(accumulate(self.val))

        for i in range(len(self.key)):
            self.bit.tree[i] = S[i] - S[i - (i&-i)]
        for i in range(len(self.key), len(self.bit.tree)):
            j = i - (i&-i)
            if j < len(S):
                self.bit.tree[i] = S[-1] - S[i - (i&-i)]


    def add(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, 1)


    def update(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            self.bit.add(ix, v)


    def remove(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            
            # 空の値を削除しないかのチェック
            # 時間が厳しそうなときはコメントアウト
            assert self.bit.sum(ix) - self.bit.sum(ix-1) > 0

            self.bit.add(ix, -v)


    def pop_vals(self, l, r):
        assert l <= r

        rix = bisect(self.key, r) - 1
        lix = bisect_left(self.key, l) - 1
        # (lix, rix]になるのに注意
        rv = self.bit.sum(rix)
        lv = self.bit.sum(lix)
        delta = rv - lv
        tv = lv+1
        tix = lix*1

        vix = 0
        rmvix = 0
        vals = [0]*delta
        rmvk = [0]*delta
        rmvv = [0]*delta
        while delta:
            OK = self.bit.lower_bound(tv)
            c = self.bit.sum(OK)
            d = c - tv + 1
            for _ in range(d):
                vals[vix] = self.key[OK]
                vix += 1
            rmvk[rmvix] = OK
            rmvv[rmvix] = d
            rmvix += 1
            tv += d
            tix = OK
            delta -= d

        for i in range(rmvix):
            self.bit.add(rmvk[i], -rmvv[i])
        return vals

N, M = inpl()
Q = sorted([inpl() for _ in range(N)], key=itemgetter(2))
D = [int(input()) for _ in range(M)]
rD = {v:i for i, v in enumerate(D)}
ans = [-1]*(M)
 
dmap = DammyMap(D)
 
for s, t, x in Q:
    val = dmap.pop_vals(s-x, t-1-x)
    for v in val:
        ans[rD[v]] = x
 
print(*ans, sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect, bisect_left
from collections import Counter
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

import sys
input = sys.stdin.readline

def inpl(): return list(map(int, input().split()))

class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.N = N
        self.tree = [0]*(self.N + 1)
        self.n = 1
        while self.n <= N:
            self.n *= 2
        self.n //= 2

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

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.N:
            self.tree[i] += x
            i += (i & -(i))

    def lower_bound(self, val):
        if val <= 0:
            return 0
        res = 0
        k = self.n
        while k:
            if res + k <= self.N and self.tree[res + k] < val:
                val -= self.tree[res + k]
                res += k
            k //= 2
        return res + 1
            
class OfflineSortedSet:
	
    def __init__(self, all_vals):
        self.keys = sorted(set(all_vals))
        self.max_key = max(self.keys)
        self.key_to_index = {k:i for i, k in enumerate(self.keys, start=1)}
        self.keys_num = len(self.keys)

        self.bit = BIT(self.keys_num)
        self.hash_set = set()

        self.add_bit = self.bit.add
        self.sum_bit = self.bit.sum
        self.lower_bound_bit = self.bit.lower_bound
        self.add_hash_set = self.hash_set.add
        self.remove_hash_set = self.hash_set.remove

    def exists(self, val):
        return val in self.hash_set

    def add(self, val):
        if val in self.hash_set:
            return
        
        self.add_hash_set(val)
        self.add_bit(self.key_to_index[val], 1)

    def remove(self, val):
        if val not in self.hash_set:
            return

        self.remove_hash_set(val)
        self.add_bit(self.key_to_index[val], -1)

    def lower_bound(self, val):
        idx = bisect_left(self.keys, val)
        tar = self.sum_bit(idx)
        res = self.lower_bound_bit(tar + 1) - 1
        if res < 0 or res >= self.keys_num:
            res = self.keys_num
        return res

def main():
    N, Q = inpl()
    X = [0]*N

    v = [0]*(2*N)
    for i in range(N):
        s, t, X[i] = inpl()
        v[2*i] = (s - X[i], 1, X[i])
        v[2*i+1] = (t - X[i], -1, X[i])
    v = sorted(v)

    se = OfflineSortedSet(X)
    del X

    idx = 0
    for i in range(Q):
        d = int(input())
        while idx < len(v):
            t, com, x = v[idx]
            if t > d:
                break
            if com == 1:
                se.add(x)
            else:
                se.remove(x)
            idx += 1
        print(-1 if len(se.hash_set) == 0 else se.keys[se.lower_bound(-10000000000)])

if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect, bisect_left
from collections import Counter
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

import sys
input = sys.stdin.readline

def inpl(): return list(map(int, input().split()))

class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.N = N
        self.tree = [0]*(self.N + 1)
        self.n = 1
        while self.n <= N:
            self.n *= 2
        self.n //= 2

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

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.N:
            self.tree[i] += x
            i += (i & -(i))

    def lower_bound(self, val):
        if val <= 0:
            return 0
        res = 0
        k = self.n
        while k:
            if res + k <= self.N and self.tree[res + k] < val:
                val -= self.tree[res + k]
                res += k
            k //= 2
        return res + 1

class DammyMap:

    def __init__(self, counter, INF=2**32):
        if type(counter) != Counter:
            counter = Counter(counter)

        self.bit = BIT(len(counter.keys())+3)
        self.key = sorted([-INF, -INF] + sorted(counter.keys()) + [INF])
        self.val = [counter[k] for k in self.key]
        S = list(accumulate(self.val))

        for i in range(len(self.key)):
            self.bit.tree[i] = S[i] - S[i - (i&-i)]
        for i in range(len(self.key), len(self.bit.tree)):
            j = i - (i&-i)
            if j < len(S):
                self.bit.tree[i] = S[-1] - S[i - (i&-i)]


    def add(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, 1)


    def update(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            self.bit.add(ix, v)


    def remove(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            
            # 空の値を削除しないかのチェック
            # 時間が厳しそうなときはコメントアウト
            assert self.bit.sum(ix) - self.bit.sum(ix-1) > 0

            self.bit.add(ix, -v)


    def pop_vals(self, l, r):
        assert l <= r

        rix = bisect(self.key, r) - 1
        lix = bisect_left(self.key, l) - 1
        # (lix, rix]になるのに注意
        rv = self.bit.sum(rix)
        lv = self.bit.sum(lix)
        delta = rv - lv
        tv = lv+1
        tix = lix*1

        vix = 0
        rmvix = 0
        vals = [0]*delta
        rmvk = [0]*delta
        rmvv = [0]*delta
        while delta:
            OK = self.bit.lower_bound(tv)
            c = self.bit.sum(OK)
            d = c - tv + 1
            for _ in range(d):
                vals[vix] = self.key[OK]
                vix += 1
            rmvk[rmvix] = OK
            rmvv[rmvix] = d
            rmvix += 1
            tv += d
            tix = OK
            delta -= d

        for i in range(rmvix):
            self.bit.add(rmvk[i], -rmvv[i])
        return vals

N, M = inpl()
Q = sorted([inpl() for _ in range(N)], key=itemgetter(2))
D = [int(input()) for _ in range(M)]
rD = {v:i for i, v in enumerate(D)}
ans = [-1]*(M)
 
dmap = DammyMap(D)
 
for s, t, x in Q:
    val = dmap.pop_vals(s-x, t-1-x)
    for v in val:
        ans[rD[v]] = x
 
print(*ans, sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect, bisect_left
from collections import Counter
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

import sys
input = sys.stdin.readline

def inpl(): return list(map(int, input().split()))

class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.N = N
        self.tree = [0]*(self.N + 1)
        self.n = 1
        while self.n <= N:
            self.n *= 2
        self.n //= 2

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

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.N:
            self.tree[i] += x
            i += (i & -(i))

    def lower_bound(self, val):
        if val <= 0:
            return 0
        res = 0
        k = self.n
        while k:
            if res + k <= self.N and self.tree[res + k] < val:
                val -= self.tree[res + k]
                res += k
            k //= 2
        return res + 1
            
class OfflineSortedSet:
	
    def __init__(self, all_vals):
        self.keys = sorted(set(all_vals))
        self.max_key = max(self.keys)
        self.key_to_index = {k:i for i, k in enumerate(self.keys, start=1)}
        self.keys_num = len(self.keys)

        self.bit = BIT(self.keys_num)
        self.hash_set = set()

        self.add_bit = self.bit.add
        self.sum_bit = self.bit.sum
        self.lower_bound_bit = self.bit.lower_bound
        self.add_hash_set = self.hash_set.add
        self.remove_hash_set = self.hash_set.remove

    def exists(self, val):
        return val in self.hash_set

    def add(self, val):
        if val in self.hash_set:
            return
        
        self.add_hash_set(val)
        self.add_bit(self.key_to_index[val], 1)

    def remove(self, val):
        if val not in self.hash_set:
            return

        self.remove_hash_set(val)
        self.add_bit(self.key_to_index[val], -1)

    def lower_bound(self, val):
        idx = bisect_left(self.keys, val)
        tar = self.sum_bit(idx)
        res = self.lower_bound_bit(tar + 1) - 1
        if res < 0 or res >= self.keys_num:
            res = self.keys_num
        return res

def main():
    N, Q = inpl()
    hoge = [inpl() for _ in range(N)]
    X = [0]*N

    v = [0]*(2*N)
    for i in range(N):
        s, t, X[i] = hoge[i]
        v[2*i] = (s - X[i], 1, X[i])
        v[2*i+1] = (t - X[i], -1, X[i])
    v = sorted(v)

    se = OfflineSortedSet(X)
    del X

    idx = 0
    D = [int(input()) for _ in range(Q)]
    ans = [0]*Q
    for i, d in enumerate(D):
        while idx < len(v):
            t, com, x = v[idx]
            if t > d:
                break
            if com == 1:
                se.add(x)
            else:
                se.remove(x)
            idx += 1
        ans[i] = -1 if len(se.hash_set) == 0 else se.keys[se.lower_bound(-10000000000)]
    print(*ans, sep="\n")
    
if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect, bisect_left
from collections import Counter
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

import sys
input = sys.stdin.readline

def inpl(): return list(map(int, input().split()))

class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.N = N
        self.tree = [0]*(self.N + 1)
        self.n = 1
        while self.n <= N:
            self.n *= 2
        self.n //= 2

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

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.N:
            self.tree[i] += x
            i += (i & -(i))

    def lower_bound(self, val):
        if val <= 0:
            return 0
        res = 0
        k = self.n
        while k:
            if res + k <= self.N and self.tree[res + k] < val:
                val -= self.tree[res + k]
                res += k
            k //= 2
        return res + 1

class DammyMap:

    def __init__(self, counter, INF=2**32):
        if type(counter) != Counter:
            counter = Counter(counter)

        self.bit = BIT(len(counter.keys())+3)
        self.key = sorted([-INF, -INF] + sorted(counter.keys()) + [INF])
        self.val = [counter[k] for k in self.key]
        S = list(accumulate(self.val))

        for i in range(len(self.key)):
            self.bit.tree[i] = S[i] - S[i - (i&-i)]
        for i in range(len(self.key), len(self.bit.tree)):
            j = i - (i&-i)
            if j < len(S):
                self.bit.tree[i] = S[-1] - S[i - (i&-i)]


    def add(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, 1)


    def update(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            self.bit.add(ix, v)


    def remove(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            
            # 空の値を削除しないかのチェック
            # 時間が厳しそうなときはコメントアウト
            assert self.bit.sum(ix) - self.bit.sum(ix-1) > 0

            self.bit.add(ix, -v)


    def pop_vals(self, l, r):
        assert l <= r

        rix = bisect(self.key, r) - 1
        lix = bisect_left(self.key, l) - 1
        # (lix, rix]になるのに注意
        rv = self.bit.sum(rix)
        lv = self.bit.sum(lix)
        delta = rv - lv
        tv = lv+1
        tix = lix*1

        vix = 0
        rmvix = 0
        vals = [0]*delta
        rmvk = [0]*delta
        rmvv = [0]*delta
        while delta:
            OK = self.bit.lower_bound(tv)
            c = self.bit.sum(OK)
            d = c - tv + 1
            for _ in range(d):
                vals[vix] = self.key[OK]
                vix += 1
            rmvk[rmvix] = OK
            rmvv[rmvix] = d
            rmvix += 1
            tv += d
            tix = OK
            delta -= d

        for i in range(rmvix):
            self.bit.add(rmvk[i], -rmvv[i])
        return vals

N, M = inpl()
Q = sorted([inpl() for _ in range(N)], key=itemgetter(2))
D = [int(input()) for _ in range(M)]
rD = {v:i for i, v in enumerate(D)}
ans = [-1]*(M)
 
dmap = DammyMap(D)
 
for s, t, x in Q:
    val = dmap.pop_vals(s-x, t-1-x)
    for v in val:
        ans[rD[v]] = x
 
print(*ans, sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect, bisect_left
from collections import Counter
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

import sys
input = sys.stdin.readline

def inpl(): return list(map(int, input().split()))

class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.N = N
        self.tree = [0]*(self.N + 1)
        self.n = 1
        while self.n <= N:
            self.n *= 2
        self.n //= 2

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

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.N:
            self.tree[i] += x
            i += (i & -(i))

    def lower_bound(self, val):
        if val <= 0:
            return 0
        res = 0
        k = self.n
        while k:
            if res + k <= self.N and self.tree[res + k] < val:
                val -= self.tree[res + k]
                res += k
            k //= 2
        return res + 1
            
class OfflineSortedSet:
	
    def __init__(self, all_vals):
        self.keys = sorted(set(all_vals))
        self.max_key = max(self.keys)
        self.key_to_index = {k:i for i, k in enumerate(self.keys, start=1)}
        self.keys_num = len(self.keys)

        self.bit = BIT(self.keys_num)
        self.hash_set = set()

        self.add_bit = self.bit.add
        self.sum_bit = self.bit.sum
        self.lower_bound_bit = self.bit.lower_bound
        self.add_hash_set = self.hash_set.add
        self.remove_hash_set = self.hash_set.remove

    def exists(self, val):
        return val in self.hash_set

    def add(self, val):
        if val in self.hash_set:
            return
        
        self.add_hash_set(val)
        self.add_bit(self.key_to_index[val], 1)

    def remove(self, val):
        if val not in self.hash_set:
            return

        self.remove_hash_set(val)
        self.add_bit(self.key_to_index[val], -1)

    def lower_bound(self, val):
        idx = bisect_left(self.keys, val)
        tar = self.sum_bit(idx)
        res = self.lower_bound_bit(tar + 1) - 1
        if res < 0 or res >= self.keys_num:
            res = self.keys_num
        return res

def main():
    N, Q = inpl()
    X = [0]*N

    v = [0]*(2*N)
    for i in range(N):
        s, t, X[i] = inpl()
        v[2*i] = (s - X[i], 1, X[i])
        v[2*i+1] = (t - X[i], -1, X[i])
    v = sorted(v)

    se = OfflineSortedSet(X)
    del X

    idx = 0
    for i in range(Q):
        d = int(input())
        while idx < len(v):
            t, com, x = v[idx]
            if t > d:
                break
            if com == 1:
                se.add(x)
            else:
                se.remove(x)
            idx += 1
        print(-1 if len(se.hash_set) == 0 else se.keys[se.lower_bound(-10000000000)])

if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect, bisect_left
from collections import Counter
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

import sys
input = sys.stdin.readline

def inpl(): return list(map(int, input().split()))

class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.N = N
        self.tree = [0]*(self.N + 1)
        self.n = 1
        while self.n <= N:
            self.n *= 2
        self.n //= 2

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

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.N:
            self.tree[i] += x
            i += (i & -(i))

    def lower_bound(self, val):
        if val <= 0:
            return 0
        res = 0
        k = self.n
        while k:
            if res + k <= self.N and self.tree[res + k] < val:
                val -= self.tree[res + k]
                res += k
            k //= 2
        return res + 1

class DammyMap:

    def __init__(self, counter, INF=2**32):
        if type(counter) != Counter:
            counter = Counter(counter)

        self.bit = BIT(len(counter.keys())+3)
        self.key = sorted([-INF, -INF] + sorted(counter.keys()) + [INF])
        self.val = [counter[k] for k in self.key]
        S = list(accumulate(self.val))

        for i in range(len(self.key)):
            self.bit.tree[i] = S[i] - S[i - (i&-i)]
        for i in range(len(self.key), len(self.bit.tree)):
            j = i - (i&-i)
            if j < len(S):
                self.bit.tree[i] = S[-1] - S[i - (i&-i)]


    def add(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, 1)


    def update(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            self.bit.add(ix, v)


    def remove(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            
            # 空の値を削除しないかのチェック
            # 時間が厳しそうなときはコメントアウト
            assert self.bit.sum(ix) - self.bit.sum(ix-1) > 0

            self.bit.add(ix, -v)


    def pop_vals(self, l, r):
        assert l <= r

        rix = bisect(self.key, r) - 1
        lix = bisect_left(self.key, l) - 1
        # (lix, rix]になるのに注意
        rv = self.bit.sum(rix)
        lv = self.bit.sum(lix)
        delta = rv - lv
        tv = lv+1
        tix = lix*1

        vix = 0
        rmvix = 0
        vals = [0]*delta
        rmvk = [0]*delta
        rmvv = [0]*delta
        while delta:
            OK = self.bit.lower_bound(tv)
            c = self.bit.sum(OK)
            d = c - tv + 1
            for _ in range(d):
                vals[vix] = self.key[OK]
                vix += 1
            rmvk[rmvix] = OK
            rmvv[rmvix] = d
            rmvix += 1
            tv += d
            tix = OK
            delta -= d

        for i in range(rmvix):
            self.bit.add(rmvk[i], -rmvv[i])
        return vals

N, M = inpl()
Q = sorted([inpl() for _ in range(N)], key=itemgetter(2))
D = [int(input()) for _ in range(M)]
rD = {v:i for i, v in enumerate(D)}
ans = [-1]*(M)
 
dmap = DammyMap(D)
 
for s, t, x in Q:
    val = dmap.pop_vals(s-x, t-1-x)
    for v in val:
        ans[rD[v]] = x
 
print(*ans, sep="\n")