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


class LazySegmentTree():

    def __init__(self, n):
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [0] * (2*self.size - 1)
        self.lazy = [0] * (2*self.size - 1)
        self.is_lazy = [False] * (2*self.size - 1)

       
    def lazy_eval(self, k, l, r):
        if self.is_lazy[k]:
            self.node[k] = self.lazy[k]
            if r - l > 1:
                self.lazy[2*k+1] = self.lazy[k]
                self.lazy[2*k+2] = self.lazy[k]
                self.is_lazy[2*k+1] = True
                self.is_lazy[2*k+2] = True
            self.is_lazy[k] = False

    def update(self, begin, end, val, k=0, l=0, r=-1):
        if r < 0:
            r = self.size
        self.lazy_eval(k, l, r)
        if r <= begin or end <= l:
            return
        if begin <= l and r <= end:
            self.lazy[k] = val
            self.is_lazy[k] = True
            self.lazy_eval(k, l, r)
        else:
            self.update(begin, end, val, 2*k+1, l, (l+r)//2)
            self.update(begin, end, val, 2*k+2, (l+r)//2, r) 
            self.node[k] = self.node[2*k+1] + self.node[2*k+2] 

    def get_sum(self, begin, end, k=0, l=0, r=-1):
        if r < 0:
            r = self.size
        self.lazy_eval(k, l, r)
        if r <= begin or end <= l:
            return 0
        if begin <= l and r <= end:
            return self.node[k]
        vl = self.get_sum(begin, end, 2*k+1, l, (l+r)//2)
        vr = self.get_sum(begin, end, 2*k+2, (l+r)//2, r)
        return vl + vr


#座標圧縮したリストを返す
def compress(list1):
    list2 = sorted(set(list1))
    memo = {value : index for index, value in enumerate(list2)}
    return list2, memo, len(list2)


n, q = map(int, input().split())
info = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
info = sorted(info, key = itemgetter(2), reverse = True)
d = [int(sys.stdin.readline()) for i in range(q)]

coord_li = []
for i in range(n):
    a, b = info[i][0] - info[i][2] , info[i][1] - info[i][2]
    coord_li += [a, b]
list1, compressed_memo, len_memo = compress(coord_li)

st = LazySegmentTree(len_memo + 1)

for i in range(n):
    a, b = info[i][0] - info[i][2] , info[i][1] - info[i][2]
    st.update(compressed_memo[a], compressed_memo[b], i+1)

for i in range(q):
    num = bisect.bisect_right(list1, d[i])
    if st.get_sum(num-1, num) == 0:
        print(-1)
    else:
        print(info[st.get_sum(num-1, num)-1][2])


Fixed submission:
import sys
import bisect


class DualSegmentTree():

    def __init__(self, n):
        INF = float("inf")
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [INF] * (2*self.size - 1)

    def update(self, begin, end, val):
        begin += (self.size - 1)
        end += (self.size - 1)
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                self.node[end] = min(val, self.node[end])
            if (begin - 1) & 1:
                self.node[begin] = min(val, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2

    def get_val(self, i):
        i += (self.size - 1)
        val = self.node[i]
        while i > 0:
            i = (i - 1) // 2
            val = min(val, self.node[i])
        return val

n, q = map(int, input().split())
info = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
d = [int(sys.stdin.readline()) for i in range(q)]
INF = float("inf")

st = DualSegmentTree(len(d)+1)

for i in range(n):
    a, b = info[i][0] - info[i][2], info[i][1] - info[i][2]  
    l = bisect.bisect_left(d, a)
    r = bisect.bisect_left(d, b)
    st.update(l, r, info[i][2])

for i in range(q):
    tmp = st.get_val(i)
    if tmp == float("inf"):
        print(-1)
    else:
        print(tmp)

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


class DualSegmentTree():

    def __init__(self, n):
        INF = float("inf")
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [INF] * (2*self.size - 1)

    def update(self, begin, end, val):
        begin += (self.size - 1)
        end += (self.size - 1)
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                self.node[end] = min(val, self.node[end])
            if (begin - 1) & 1:
                self.node[begin] = min(val, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2

    def get_val(self, i):
        i += (self.size - 1)
        val = self.node[i]
        while i > 0:
            i = (i - 1) // 2
            val = min(val, self.node[i])
        return val

n, q = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]
d = [int(input()) for i in range(q)]
INF = float("inf")

st = DualSegmentTree(len(d)+1)

for i in range(n):
    a, b = info[i][0] - info[i][2], info[i][1] - info[i][2]  
    l = bisect.bisect_left(d, a)
    r = bisect.bisect_left(d, b)
    st.update(l, r, info[i][2])

for i in range(q):
    tmp = st.get_val(i)
    if tmp == float("inf"):
        print(-1)
    else:
        print(tmp)

Fixed submission:
import sys
import bisect


class DualSegmentTree():

    def __init__(self, n):
        INF = float("inf")
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [INF] * (2*self.size - 1)

    def update(self, begin, end, val):
        begin += (self.size - 1)
        end += (self.size - 1)
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                self.node[end] = min(val, self.node[end])
            if (begin - 1) & 1:
                self.node[begin] = min(val, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2

    def get_val(self, i):
        i += (self.size - 1)
        val = self.node[i]
        while i > 0:
            i = (i - 1) // 2
            val = min(val, self.node[i])
        return val

n, q = map(int, input().split())
info = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
d = [int(sys.stdin.readline()) for i in range(q)]
INF = float("inf")

st = DualSegmentTree(len(d)+1)

for i in range(n):
    a, b = info[i][0] - info[i][2], info[i][1] - info[i][2]  
    l = bisect.bisect_left(d, a)
    r = bisect.bisect_left(d, b)
    st.update(l, r, info[i][2])

for i in range(q):
    tmp = st.get_val(i)
    if tmp == float("inf"):
        print(-1)
    else:
        print(tmp)

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


class DualSegmentTree():
 
    def __init__(self, n):
        INF = float("inf")
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [INF] * (2*self.size - 1)
 
    def update(self, begin, end, val, k=0, l=0, r=-1):
        if 2*self.size - 1 <= k:
            return
        if r < 0:
            r = self.size
        if begin <= l and r <= end:
            self.node[k] = min(val, self.node[k])
        self.update(begin, end, val, 2*k+1, l, (l+r)//2)
        self.update(begin, end, val, 2*k+2, (l+r)//2, r)

    def get_val(self, i):
        i += (self.size - 1)
        val = self.node[i]
        while i > 0:
            i = (i - 1) // 2
            val = min(val, self.node[i])
        return val

n, q = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]
d = [int(input()) for i in range(q)]
INF = float("inf")

st = DualSegmentTree(len(d)+1)

for i in range(n):
    a, b = info[i][0] - info[i][2], info[i][1] - info[i][2]  
    l = bisect.bisect_left(d, a)
    r = bisect.bisect_left(d, b)
    st.update(l, r, info[i][2])

for i in range(q):
    tmp = st.get_val(i)
    if tmp == float("inf"):
        print(-1)
    else:
        print(tmp)

Fixed submission:
import sys
import bisect


class DualSegmentTree():

    def __init__(self, n):
        INF = float("inf")
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [INF] * (2*self.size - 1)

    def update(self, begin, end, val):
        begin += (self.size - 1)
        end += (self.size - 1)
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                self.node[end] = min(val, self.node[end])
            if (begin - 1) & 1:
                self.node[begin] = min(val, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2

    def get_val(self, i):
        i += (self.size - 1)
        val = self.node[i]
        while i > 0:
            i = (i - 1) // 2
            val = min(val, self.node[i])
        return val

n, q = map(int, input().split())
info = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
d = [int(sys.stdin.readline()) for i in range(q)]
INF = float("inf")

st = DualSegmentTree(len(d)+1)

for i in range(n):
    a, b = info[i][0] - info[i][2], info[i][1] - info[i][2]  
    l = bisect.bisect_left(d, a)
    r = bisect.bisect_left(d, b)
    st.update(l, r, info[i][2])

for i in range(q):
    tmp = st.get_val(i)
    if tmp == float("inf"):
        print(-1)
    else:
        print(tmp)

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


class DualSegmentTree():
 
    def __init__(self, n):
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [0] * (2*self.size - 1)
 
    def update(self, begin, end, val, k=0, l=0, r=-1):
        if 2*self.size - 1 <= k:
            return
        if r < 0:
            r = self.size
        if begin <= l and r <= end:
            self.node[k] = max(val, self.node[k])
        self.update(begin, end, val, 2*k+1, l, (l+r)//2)
        self.update(begin, end, val, 2*k+2, (l+r)//2, r)

    def get_val(self, i):
        i += (self.size - 1)
        val = self.node[i]
        while i > 0:
            i = (i - 1) // 2
            val = max(val, self.node[i])
        return val


#座標圧縮したリストを返す
def compress(list1):
    list2 = sorted(set(list1))
    memo = {value : index for index, value in enumerate(list2)}
    return list2, memo, len(list2)


n, q = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]
info = sorted(info, key = itemgetter(2), reverse = True)
d = [int(input()) for i in range(q)]

coord_li = [info[i][0] - info[i][2] for i in range(n)] + [info[i][1] - info[i][2] for i in range(n)]
list1, compressed_memo, len_memo = compress(coord_li)

#番兵を置くために+1しておく
st = DualSegmentTree(len_memo + 1)

for i in range(n):
    a, b = info[i][0] - info[i][2], info[i][1] - info[i][2]
    st.update(compressed_memo[a], compressed_memo[b], i+1)

for i in range(q):
    num = bisect.bisect_right(list1, d[i])
    tmp = st.get_val(num-1)
    if tmp == 0:
        print(-1)
    else:
        print(info[tmp-1][2])

Fixed submission:
import sys
import bisect


class DualSegmentTree():

    def __init__(self, n):
        INF = float("inf")
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [INF] * (2*self.size - 1)

    def update(self, begin, end, val):
        begin += (self.size - 1)
        end += (self.size - 1)
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                self.node[end] = min(val, self.node[end])
            if (begin - 1) & 1:
                self.node[begin] = min(val, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2

    def get_val(self, i):
        i += (self.size - 1)
        val = self.node[i]
        while i > 0:
            i = (i - 1) // 2
            val = min(val, self.node[i])
        return val

n, q = map(int, input().split())
info = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
d = [int(sys.stdin.readline()) for i in range(q)]
INF = float("inf")

st = DualSegmentTree(len(d)+1)

for i in range(n):
    a, b = info[i][0] - info[i][2], info[i][1] - info[i][2]  
    l = bisect.bisect_left(d, a)
    r = bisect.bisect_left(d, b)
    st.update(l, r, info[i][2])

for i in range(q):
    tmp = st.get_val(i)
    if tmp == float("inf"):
        print(-1)
    else:
        print(tmp)

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


class DualSegmentTree():
 
    def __init__(self, n):
        self.size = 1
        INF = float("inf")
        while self.size < n:
            self.size *= 2
        self.node = [0] * (2*self.size - 1)
 
    def update(self, begin, end, val, k=0, l=0, r=-1):
        if 2*self.size - 1 <= k:
            return
        if r < 0:
            r = self.size
        if r <= begin or end <= l:
            pass
        if begin <= l and r <= end:
            self.node[k] = val
        self.update(begin, end, val, 2*k+1, l, (l+r)//2)
        self.update(begin, end, val, 2*k+2, (l+r)//2, r)


    def get_val(self, i):
        i += (self.size - 1)
        val = self.node[i]
        while i > 0:
            i = (i - 1) // 2
            val = max(val, self.node[i])
        return val


#座標圧縮したリストを返す
def compress(list1):
    list2 = sorted(set(list1))
    memo = {value : index for index, value in enumerate(list2)}
    return list2, memo, len(list2)


n, q = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]
info = sorted(info, key = itemgetter(2), reverse = True)
d = [int(input()) for i in range(q)]

coord_li = []
for i in range(n):
    a, b = info[i][0] - info[i][2] , info[i][1] - info[i][2]
    coord_li += [a, b]
list1, compressed_memo, len_memo = compress(coord_li)

#番兵を置くために+1しておく
st = DualSegmentTree(len_memo + 1)

for i in range(n):
    a, b = info[i][0] - info[i][2] , info[i][1] - info[i][2]
    st.update(compressed_memo[a], compressed_memo[b], i+1)

for i in range(q):
    num = bisect.bisect_right(list1, d[i])
    if st.get_val(num-1) == 0:
        print(-1)
    else:
        print(info[st.get_val(num-1)-1][2])

Fixed submission:
import sys
import bisect


class DualSegmentTree():

    def __init__(self, n):
        INF = float("inf")
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [INF] * (2*self.size - 1)

    def update(self, begin, end, val):
        begin += (self.size - 1)
        end += (self.size - 1)
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                self.node[end] = min(val, self.node[end])
            if (begin - 1) & 1:
                self.node[begin] = min(val, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2

    def get_val(self, i):
        i += (self.size - 1)
        val = self.node[i]
        while i > 0:
            i = (i - 1) // 2
            val = min(val, self.node[i])
        return val

n, q = map(int, input().split())
info = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
d = [int(sys.stdin.readline()) for i in range(q)]
INF = float("inf")

st = DualSegmentTree(len(d)+1)

for i in range(n):
    a, b = info[i][0] - info[i][2], info[i][1] - info[i][2]  
    l = bisect.bisect_left(d, a)
    r = bisect.bisect_left(d, b)
    st.update(l, r, info[i][2])

for i in range(q):
    tmp = st.get_val(i)
    if tmp == float("inf"):
        print(-1)
    else:
        print(tmp)

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


class LazySegmentTree():

    def __init__(self, n):
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [0] * (2*self.size - 1)
        self.lazy = [0] * (2*self.size - 1)
        self.is_lazy = [False] * (2*self.size - 1)

       
    def lazy_eval(self, k, l, r):
        if self.is_lazy[k]:
            self.node[k] = self.lazy[k]
            if r - l > 1:
                self.lazy[2*k+1] = self.lazy[k]
                self.lazy[2*k+2] = self.lazy[k]
                self.is_lazy[2*k+1] = True
                self.is_lazy[2*k+2] = True
            self.is_lazy[k] = False

    def update(self, begin, end, val, k=0, l=0, r=-1):
        if r < 0:
            r = self.size
        self.lazy_eval(k, l, r)
        if r <= begin or end <= l:
            return
        if begin <= l and r <= end:
            self.lazy[k] = val
            self.is_lazy[k] = True
            self.lazy_eval(k, l, r)
        else:
            self.update(begin, end, val, 2*k+1, l, (l+r)//2)
            self.update(begin, end, val, 2*k+2, (l+r)//2, r) 
            self.node[k] = self.node[2*k+1] + self.node[2*k+2] 

    def get_sum(self, begin, end, k=0, l=0, r=-1):
        if r < 0:
            r = self.size
        self.lazy_eval(k, l, r)
        if r <= begin or end <= l:
            return 0
        if begin <= l and r <= end:
            return self.node[k]
        vl = self.get_sum(begin, end, 2*k+1, l, (l+r)//2)
        vr = self.get_sum(begin, end, 2*k+2, (l+r)//2, r)
        return vl + vr


#座標圧縮したリストを返す
def compress(list1):
    list2 = sorted(set(list1))
    memo = {value : index for index, value in enumerate(list2)}
    return list2, memo, len(list2)


n, q = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]
info = sorted(info, key = itemgetter(2), reverse = True)
d = [int(input()) for i in range(q)]

coord_li = []
for i in range(n):
    a, b = info[i][0] - info[i][2] , info[i][1] - info[i][2]
    coord_li += [a, b]
list1, compressed_memo, len_memo = compress(coord_li)

#番兵を置くために+1しておく
st = LazySegmentTree(len_memo + 1)

for i in range(n):
    a, b = info[i][0] - info[i][2] , info[i][1] - info[i][2]
    st.update(compressed_memo[a], compressed_memo[b], i+1)
for i in range(q):
    num = bisect.bisect_right(list1, d[i])
    if st.get_sum(num-1, num) == 0:
        print(-1)
    else:
        print(info[st.node[st.size-1+num-1]-1][2])

Fixed submission:
import sys
import bisect


class DualSegmentTree():

    def __init__(self, n):
        INF = float("inf")
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [INF] * (2*self.size - 1)

    def update(self, begin, end, val):
        begin += (self.size - 1)
        end += (self.size - 1)
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                self.node[end] = min(val, self.node[end])
            if (begin - 1) & 1:
                self.node[begin] = min(val, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2

    def get_val(self, i):
        i += (self.size - 1)
        val = self.node[i]
        while i > 0:
            i = (i - 1) // 2
            val = min(val, self.node[i])
        return val

n, q = map(int, input().split())
info = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
d = [int(sys.stdin.readline()) for i in range(q)]
INF = float("inf")

st = DualSegmentTree(len(d)+1)

for i in range(n):
    a, b = info[i][0] - info[i][2], info[i][1] - info[i][2]  
    l = bisect.bisect_left(d, a)
    r = bisect.bisect_left(d, b)
    st.update(l, r, info[i][2])

for i in range(q):
    tmp = st.get_val(i)
    if tmp == float("inf"):
        print(-1)
    else:
        print(tmp)

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


class LazySegmentTree():

    def __init__(self, n):
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [0] * (2*self.size - 1)
        self.lazy = [0] * (2*self.size - 1)
        self.is_lazy = [False] * (2*self.size - 1)

       
    def lazy_eval(self, k, l, r):
        if self.is_lazy[k]:
            self.node[k] = self.lazy[k]
            if r - l > 1:
                self.lazy[2*k+1] = self.lazy[k]
                self.lazy[2*k+2] = self.lazy[k]
                self.is_lazy[2*k+1] = True
                self.is_lazy[2*k+2] = True
            self.is_lazy[k] = False

    def update(self, begin, end, val, k=0, l=0, r=-1):
        if r < 0:
            r = self.size
        self.lazy_eval(k, l, r)
        if r <= begin or end <= l:
            return
        if begin <= l and r <= end:
            self.lazy[k] = val
            self.is_lazy[k] = True
            self.lazy_eval(k, l, r)
        else:
            self.update(begin, end, val, 2*k+1, l, (l+r)//2)
            self.update(begin, end, val, 2*k+2, (l+r)//2, r) 
            self.node[k] = self.node[2*k+1] + self.node[2*k+2] 

    def get_sum(self, begin, end, k=0, l=0, r=-1):
        if r < 0:
            r = self.size
        self.lazy_eval(k, l, r)
        if r <= begin or end <= l:
            return 0
        if begin <= l and r <= end:
            return self.node[k]
        vl = self.get_sum(begin, end, 2*k+1, l, (l+r)//2)
        vr = self.get_sum(begin, end, 2*k+2, (l+r)//2, r)
        return vl + vr


#座標圧縮したリストを返す
def compress(list1):
    list2 = sorted(set(list1))
    memo = {value : index for index, value in enumerate(list2)}
    return list2, memo, len(list2)


n, q = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]
info = sorted(info, key = itemgetter(2), reverse = True)
d = [int(input()) for i in range(q)]

coord_li = []
for i in range(n):
    a, b = info[i][0] - info[i][2] , info[i][1] - info[i][2]
    coord_li += [a, b]
list1, compressed_memo, len_memo = compress(coord_li)

#番兵を置くために+1しておく
st = LazySegmentTree(len_memo + 1)

for i in range(n):
    a, b = info[i][0] - info[i][2] , info[i][1] - info[i][2]
    st.update(compressed_memo[a], compressed_memo[b], i+1)

for i in range(q):
    num = bisect.bisect_right(list1, d[i])
    if st.get_sum(num-1, num) == 0:
        print(-1)
    else:
        print(info[st.get_sum(num-1, num)-1][2])

Fixed submission:
import sys
import bisect


class DualSegmentTree():

    def __init__(self, n):
        INF = float("inf")
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [INF] * (2*self.size - 1)

    def update(self, begin, end, val):
        begin += (self.size - 1)
        end += (self.size - 1)
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                self.node[end] = min(val, self.node[end])
            if (begin - 1) & 1:
                self.node[begin] = min(val, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2

    def get_val(self, i):
        i += (self.size - 1)
        val = self.node[i]
        while i > 0:
            i = (i - 1) // 2
            val = min(val, self.node[i])
        return val

n, q = map(int, input().split())
info = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
d = [int(sys.stdin.readline()) for i in range(q)]
INF = float("inf")

st = DualSegmentTree(len(d)+1)

for i in range(n):
    a, b = info[i][0] - info[i][2], info[i][1] - info[i][2]  
    l = bisect.bisect_left(d, a)
    r = bisect.bisect_left(d, b)
    st.update(l, r, info[i][2])

for i in range(q):
    tmp = st.get_val(i)
    if tmp == float("inf"):
        print(-1)
    else:
        print(tmp)