Problem:


Score : 500 points

Problem Statement

There is an infinitely long street that runs west to east, which we consider as a number line.

There are N roadworks scheduled on this street.
The i-th roadwork blocks the point at coordinate X_i from time S_i - 0.5 to time T_i - 0.5.

Q people are standing at coordinate 0. The i-th person will start the coordinate 0 at time D_i, continue to walk with speed 1 in the positive direction and stop walking when reaching a blocked point.

Find the distance each of the Q people will walk.

Constraints

All values in input are integers.

1 \leq N, Q \leq 2 \times 10^5

0 \leq S_i < T_i \leq 10^9

1 \leq X_i \leq 10^9

0 \leq D_1 < D_2 < ... < D_Q \leq 10^9

If i \neq j and X_i = X_j, the intervals [S_i, T_i) and [S_j, T_j) do not overlap.

Input

Input is given from Standard Input in the following format:

N Q
S_1 T_1 X_1
:
S_N T_N X_N
D_1
:
D_Q

Output

Print Q lines. The i-th line should contain the distance the i-th person will walk or -1 if that person walks forever.

Sample Input 1

4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8

Sample Output 1

2
2
10
-1
13
-1

The first person starts coordinate 0 at time 0 and stops walking at coordinate 2 when reaching a point blocked by the first roadwork at time 2.

The second person starts coordinate 0 at time 1 and reaches coordinate 2 at time 3. The first roadwork has ended, but the fourth roadwork has begun, so this person also stops walking at coordinate 2.

The fourth and sixth persons encounter no roadworks while walking, so they walk forever. The output for these cases is -1.



Sample input:
4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8


Sample output:
2
2
10
-1
13
-1

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7
INF = (1<<31) - 1
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from bisect import bisect_left

class LazySegmentTree():
    fx = min
    fa = min
    fm = min

    unit_x = INF
    unit_m = INF

    def __init__(self,array):
        self.N = len(array)
        self.tree = [self.unit_x]*(2*self.N)
        self.lazy = [self.unit_m]*(2*self.N)
        #self._build(array)
    
    def _build(self,array):
        for i,value in enumerate(array,self.N):
            self.tree[i] = value
        for i in range(self.N - 1,0,-1):
            self.tree[i] = self.fx(self.tree[i << 1],self.tree[i << 1|1])
   
    def _evaluate(self,K):#Kの上の遅延配列を評価する
        H = K.bit_length() - 1
        for i in range(H,0,-1):
            h = K >> i
            if self.lazy[h] == self.unit_x:
                continue
            self.tree[h] = self.fa(self.tree[h],self.lazy[h])
            self.lazy[h << 1] = self.fm(self.lazy[h << 1],self.lazy[h])
            self.lazy[h << 1|1] = self.fm(self.lazy[h << 1|1],self.lazy[h])
            self.lazy[h] = self.unit_m
    
    def _caluculate(self,K):#Kより上を計算する
        while K > 1:
            K >>= 1
            a = self.fa(self.tree[K << 1],self.lazy[K << 1])
            b = self.fa(self.tree[K << 1|1],self.lazy[K << 1|1])
            self.tree[K] = self.fx(a,b)

    def range_update(self,L,R,M):#[L,R)にMを作用
        L += self.N
        R += self.N
        L0 = L//(L & -L)
        R0 = R//(R & -R) - 1
        self._evaluate(L0)
        self._evaluate(R0)
        while L < R:
            if L&1:
                self.lazy[L] = self.fm(self.lazy[L],M)
                L += 1
            if R&1:
                R -= 1
                self.lazy[R] = self.fm(self.lazy[R],M)
            L >>= 1
            R >>= 1
        #print("L0 R0 {} {}\n".format(L0,R0))
        self._caluculate(L0)
        self._caluculate(R0)
    
    def range_query(self,L,R):#[L,R)を計算する
        L += self.N
        R += self.N
        L0 = L//(L & -L)
        R0 = R//(R & -R) - 1
        self._evaluate(L0)
        self._evaluate(R0)
        vl = self.unit_x
        vr = self.unit_x
        while L < R:
            if L&1:
                vl = self.fx(vl,self.fa(self.tree[L],self.lazy[L]))
                L += 1
            if R&1:
                R -= 1
                vr = self.fx(self.fa(self.tree[R],self.lazy[R]),vr)
            L >>= 1
            R >>= 1
        return self.fx(vl,vr)
    '''
    def __str__(self):
        return '\n'.join(' '.join(str(v) for v in self.tree[1<<i:1<<(i + 1)]) for i in range((2*self.N).bit_length()))
    '''
    def debug(self):
        print(self.lazy)
        print(self.tree)
    
    def __str__(self):
        for i in range(self.N):
            self.tree[i] = self.fa(self.tree[i],self.lazy[i])
            self.lazy[i << 1] = self.fm(self.lazy[i << 1],self.lazy[i])
            self.lazy[i << 1|1] = self.fm(self.lazy[i << 1|1],self.lazy[i])
            self.lazy[i] = self.unit_m
        for i in range(self.N,self.N*2):
            self.tree[i] = self.fa(self.tree[i],self.lazy[i])
        return '\n'.join(map(str,[k if k < INF else -1 for k in self.tree[self.N:]]))


N,Q = map(int,input().split())
roadwork = [tuple(map(int,input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]
st = LazySegmentTree([INF] * Q)

for s,t,x in roadwork:
    l = bisect_left(D,s - x)
    r = bisect_left(D,t - x)
    st.range_update(l,r,x)
print(str(st))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
from bisect import bisect_left, insort_left

def main():
    N, Q = list(map(int, input().split()))
    STX = [list(map(int, input().split())) for i in range(N)]
    D = [int(input()) for i in range(Q)]
    event = [None] * (2*N+Q)
    ans = [-1] * Q
    
    i = 0
    for s, t, x in STX:
        event[i] = (s-x-0.5, 0, x)
        event[i+1] = (t-x-0.5, 1, x)
        i += 2
        
    for i, d in enumerate(D):
        event[2*N+i] = (d, 2, i)
        i += 1
        
    event.sort()
    nums = []
    
    for s, m, x in event:
        if m == 0: insort_left(nums, x)
        
        elif m == 1: nums.pop(bisect_left(nums, x))
            
        else:
            if nums: ans[x] = nums[0]
            Q -= 1
            if not Q: break
    
    print('\n'.join(list(map(str, ans))))        
            
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
road=[]
Ans=[]
for i in range(N):
    s,t,x=map(int,input().split())
    road.append((x,s-0.5-x,t-0.5-x))
road.sort()
for i in range(Q):
    s=int(input())
    ans=-1
    for i in range(N):
        if road[i][1]<=s<=road[i][2]:
            ans=road[i][0]
            break
    Ans.append(ans)
for i in range(Q):
    print(Ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def BinarySearch(x,array):
    left=0
    right=len(array)-1

    while right-left>=0:
        mid=(left+right)//2
        if array[mid]==x:
            return mid
        elif array[mid]>x:
            right=mid-1
        else:
            left=mid+1
    return False


def main():
    ConstNum,PersonNum=map(int,input().split())

    S=[]
    T=[]
    X=[]
    for i in range(ConstNum):
        s,t,x=map(int,input().split())

        S.append(s-0.5)
        T.append(t-0.5)
        X.append(x)

    STX=zip(S,T,X)
    STX=sorted(STX)
    S,T,X=zip(*STX)

    S=deque(S)
    T=deque(T)
    X=deque(X)

    PersonsDistance=[]
    for i in range(PersonNum):
        d=int(input())
        PersonsDistance.insert(0,-1*d)

    res=[]

    time=0

    PersonsIndexes=[i for i in range(PersonNum-1,-1,-1)]

    while len(PersonsIndexes)>0 and len(X)>0:
        start=S.popleft()
        end=T.popleft()
        x=X.popleft()


        if start<time<end:
            underPerson=BinarySearch(x,PersonsDistance)
            if underPerson!=False:
                res.append((PersonsIndexes.pop(underPerson),PersonsDistance.pop(underPerson)))
            S.appendleft(start)
            T.appendleft(end)
            X.appendleft(x)
        elif start>time:
            S.appendleft(start)
            T.appendleft(end)
            X.appendleft(x)
        else:
            continue

        time+=1
        PersonsDistance=list(map(lambda x:x+1,PersonsDistance))

    for i in PersonsIndexes:
        res.append((i,-1))

    res=sorted(res)

    for i in res:
        print(i[1])

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    ConstNum,PersonNum=map(int,input().split())

    ConstInfo={}
    for i in range(ConstNum):
        S,T,X=map(int,input().split())

        if (X in ConstInfo):
            ConstInfo[X].append((S,T))
        else:
            ConstInfo[X]=[(S,T)]

        #ConstInfo=>{X:[(S,T),(S,T)],X:[(S,T)],...}

    ConstPlace=ConstInfo.keys()
    MaxConstPlace=max(ConstPlace)

    DepartureTime=[]
    for i in range(PersonNum):
        d=int(input())
        DepartureTime.append(d)

    res=[]

    for i in range(PersonNum):
        distance=0
        time=DepartureTime[i]

        underConst=False
        while distance<MaxConstPlace and underConst==False:
            time += 1
            distance += 1
            if (distance in ConstPlace):
                for const_time in ConstInfo[distance]:
                    if time>=const_time[0]-0.5 and time<=const_time[1]-0.5:
                        underConst=True
                        break



        if underConst:
            res.append(distance)
        else:
            res.append(-1)

    for i in res:
        print(i)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
def main():
    N, Q = map(int, input().split())
    W = [tuple(map(int, input().split())) for _ in range(N)]
    W.sort(key=lambda x:x[2])
    
    D = [int(input()) for _ in range(Q)]
    ans = [-1]*Q
    skip = [-1]*Q
    for s, t, x in W:
        l = bisect_left(D, s-x)
        r = bisect_left(D, t-x)
        while l < r:
            if skip[l] == -1:
                ans[l] = x
                skip[l] = r
                l+=1
            else:
                l = skip[l]
    for a in ans:
        print(a)
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.stdin.readline
n,p=map(int,input().split())

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
e.sort()
q = deque()
for _ in range(p):
    q.append(int(input()))
s = set()
removed = set()
s_min = None

for t,f,x in e:
    while t > q[0]:
        q.popleft()
        if s:
            if s_min is None:
              s_min = min(s)
            print(s_min)
        else:
            print(-1)
        if not q:
            sys.exit()
    if f == 1:
        s.add(x)
        if s_min is not None and s_min > x:
          s_min = x
    else:
        s.remove(x)
        if x == s_min:
          s_min = None

        
while q:
    q.pop()
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left
    from bisect import bisect_right
    from sys import stdin
    input=stdin.readline

    n,q=map(int,input().split())
    stx=[list(map(int,input().split())) for _ in [0]*n]
    d=[int(input()) for _ in [0]*q]
    stx=[[s-x,t-x-1,x] for s,t,x in stx]
    stx=[[bisect_left(d,s),bisect_right(d,t),x] for s,t,x in stx]

    #セグ木の要素数（num）および深さ（depth）を計算
    basesize=q
    num,depth=1,1
    while num<basesize:
        num*=2
        depth+=1
    num-=1
    #セグ木を構築
    treesize=num+basesize
    tree=[10**9+1]*treesize
    
    #半開区間[lower,upper)について更新の準備をする関数
    def range_update_pre(lower,upper,new_value):
        q=[[0,1]]  #インデックス、階層
        while q:
            i,f=q.pop()
            #popしたインデックスと階層から、求める下限と上限を算出する
            #幅
            width=pow(2,depth-f)
            #下限と中央と上限
            kagen=(i-pow(2,f-1)+1)*width
            chuo=kagen+width//2
            jogen=kagen+width
            k=2*i+1
            if lower<=kagen and jogen<=upper:
                tree[i]=min(new_value,tree[i])
                continue
            if k<treesize:
                if lower<=kagen and chuo<=upper:tree[k]=min(new_value,tree[k])
                elif lower<=chuo:q.append([k,f+1])
            if k+1<treesize:
                if lower<=chuo and jogen<=upper:tree[k+1]=min(new_value,tree[k+1])
                elif chuo<=upper:q.append([k+1,f+1])

    for s,t,x in stx:
        if s<t:
            range_update_pre(s,t,x)

    for i in range(1,treesize):
        tree[i]=min(tree[i],tree[(i-1)//2])

    ans=[i for i in tree[treesize-basesize:]]
    for i in ans:
        if i==10**9+1:
            print(-1)
        else:
            print(i)
main()

Submission status: Time Limit Exceeded

Solution code:
import random
from collections import deque
import sys
sys.stdin.readline

import random
class Treap:
    def __init__(self):
        self.node = None  # root

    def __str__(self):
        L = []
        def recursiveSearch(node):
            if node.left is not None:
                recursiveSearch(node.left)
            L.append((node.val, node.priority))
            if node.right is not None:
                recursiveSearch(node.right)
        recursiveSearch(self.node)
        return str(L)

    def add(self, x):
        i = self.bisect(x)
        self.node = self.insert(self.node, i, x)

    def remove(self, x):
        i = self.bisect(x)
        self.node = self.erase(self.node, i)

    def bisect(self, x):  # bisect_left
        def recursiveSearch(node):
            if node is None:
                return 0
            res = 0
            if x <= node.val:
                if node.left is not None:
                    return recursiveSearch(node.left)
                else:
                    return 0
            else:
                res += self.count(node.left) + 1
                if node.right is not None:
                    return res + recursiveSearch(node.right)
                else:
                    return res
        return recursiveSearch(self.node)

    def min(self):
        t = self.node
        while t.left is not None:
          t = t.left
        return t.val

    class Node:
        def __init__(self, x):
            self.val = x
            self.priority = random.randint(0, 1<<30)
            self.left = None
            self.right = None
            self.cnt = 1
        def __str__(self):
            return str(self.val)

    def count(self, t: Node):
        return 0 if t is None else t.cnt

    def update(self, t: Node):
        t.cnt = self.count(t.left) + self.count(t.right) + 1
        return t

    def merge(self, l: Node, r: Node):
        if l is None: return r
        if r is None: return l
        if l.priority > r.priority:
            l.right = self.merge(l.right, r)
            return self.update(l)
        else:
            r.left = self.merge(l, r.left)
            return self.update(r)

    def split(self, t: Node, k: int) -> (Node, Node):  # [0,k),[k,n)
        if t is None: return None, None
        if k <= self.count(t.left):
            s = self.split(t.left, k)
            t.left = s[1]
            return s[0], self.update(t)
        else:
            s = self.split(t.right, k - self.count(t.left) - 1)
            t.right = s[0]
            return self.update(t), s[1]

    def insert(self, t: Node, k: int, x):
        l, r = self.split(t, k)
        return self.merge(self.merge(l, self.Node(x)), r)

    def erase(self, t: Node, k):
        l, r = self.split(t, k)
        _, r = self.split(r, 1)
        return self.merge(l, r)

    
def main():
  n,p=map(int,sys.stdin.buffer.readline().split())

  e=[]
  for _ in range(n):
      s,t,x = map(int,sys.stdin.buffer.readline().split())
      e.append((s-x,1,x))
      e.append((t-x,-1,x))
  e.sort()
  q = deque()
  for _ in range(p):
      q.append(int(input()))
  s=Treap()

  for t,f,x in e:
      while t > q[0]:
          q.popleft()
          if s.node:
              print(s.min())
          else:
              print(-1)
          if not q:
              sys.exit()
      if f == 1:
          s.add(x)
      else:
          s.remove(x)

  while q:
      q.pop()
      print(-1)

main()

Submission status: Time Limit Exceeded

Solution code:
import random
from collections import deque
import sys
sys.stdin.readline

import random
class Treap:
    def __init__(self):
        self.node = None  # root

    def __str__(self):
        L = []
        def recursiveSearch(node):
            if node.left is not None:
                recursiveSearch(node.left)
            L.append((node.val, node.priority))
            if node.right is not None:
                recursiveSearch(node.right)
        recursiveSearch(self.node)
        return str(L)

    def add(self, x):
        i = self.bisect(x)
        self.node = self.insert(self.node, i, x)

    def remove(self, x):
        i = self.bisect(x)
        self.node = self.erase(self.node, i)

    def bisect(self, x):  # bisect_left
        def recursiveSearch(node):
            if node is None:
                return 0
            res = 0
            if x <= node.val:
                if node.left is not None:
                    return recursiveSearch(node.left)
                else:
                    return 0
            else:
                res += self.count(node.left) + 1
                if node.right is not None:
                    return res + recursiveSearch(node.right)
                else:
                    return res
        return recursiveSearch(self.node)

    def __getitem__(self, k, t=None):
        if t is None: t = self.node
        if k < self.count(t.left):
            if t.left is None:
                return t.val
            return self.__getitem__(k, t.left)
        elif k == self.count(t.left):
            return t.val
        else:
            if t.right is None:
                return t.val
            return self.__getitem__(k - self.count(t.left) - 1, t.right)

    class Node:
        def __init__(self, x):
            self.val = x
            self.priority = random.randint(0, 1<<30)
            self.left = None
            self.right = None
            self.cnt = 1
        def __str__(self):
            return str(self.val)

    def count(self, t: Node):
        return 0 if t is None else t.cnt

    def update(self, t: Node):
        t.cnt = self.count(t.left) + self.count(t.right) + 1
        return t

    def merge(self, l: Node, r: Node):
        if l is None: return r
        if r is None: return l
        if l.priority > r.priority:
            l.right = self.merge(l.right, r)
            return self.update(l)
        else:
            r.left = self.merge(l, r.left)
            return self.update(r)

    def split(self, t: Node, k: int) -> (Node, Node):  # [0,k),[k,n)
        if t is None: return None, None
        if k <= self.count(t.left):
            s = self.split(t.left, k)
            t.left = s[1]
            return s[0], self.update(t)
        else:
            s = self.split(t.right, k - self.count(t.left) - 1)
            t.right = s[0]
            return self.update(t), s[1]

    def insert(self, t: Node, k: int, x):
        l, r = self.split(t, k)
        return self.merge(self.merge(l, self.Node(x)), r)

    def erase(self, t: Node, k):
        l, r = self.split(t, k)
        _, r = self.split(r, 1)
        return self.merge(l, r)

    
def main():
  n,p=map(int,sys.stdin.buffer.readline().split())

  e=[]
  for _ in range(n):
      s,t,x = map(int,sys.stdin.buffer.readline().split())
      e.append((s-x,1,x))
      e.append((t-x,-1,x))
  e.sort()
  q = deque()
  for _ in range(p):
      q.append(int(input()))
  s=Treap()

  for t,f,x in e:
      while t > q[0]:
          q.popleft()
          if s.node:
              print(s[0])
          else:
              print(-1)
          if not q:
              sys.exit()
      if f == 1:
          s.add(x)
      else:
          s.remove(x)

  while q:
      q.pop()
      print(-1)

main()

Submission status: Time Limit Exceeded

Solution code:
import random
from collections import deque
import sys
sys.stdin.readline

import random
class Treap:
    def __init__(self):
        self.node = None  # root

    def __str__(self):
        L = []
        def recursiveSearch(node):
            if node.left is not None:
                recursiveSearch(node.left)
            L.append((node.val, node.priority))
            if node.right is not None:
                recursiveSearch(node.right)
        recursiveSearch(self.node)
        return str(L)

    def add(self, x):
        i = self.bisect(x)
        self.node = self.insert(self.node, i, x)

    def remove(self, x):
        i = self.bisect(x)
        self.node = self.erase(self.node, i)

    def bisect(self, x):  # bisect_left
        def recursiveSearch(node):
            if node is None:
                return 0
            res = 0
            if x <= node.val:
                if node.left is not None:
                    return recursiveSearch(node.left)
                else:
                    return 0
            else:
                res += self.count(node.left) + 1
                if node.right is not None:
                    return res + recursiveSearch(node.right)
                else:
                    return res
        return recursiveSearch(self.node)

    def __getitem__(self, k, t=None):
        if t is None: t = self.node
        if k < self.count(t.left):
            if t.left is None:
                return t.val
            return self.__getitem__(k, t.left)
        elif k == self.count(t.left):
            return t.val
        else:
            if t.right is None:
                return t.val
            return self.__getitem__(k - self.count(t.left) - 1, t.right)

    class Node:
        def __init__(self, x):
            self.val = x
            self.priority = random.randint(0, 1<<30)
            self.left = None
            self.right = None
            self.cnt = 1
        def __str__(self):
            return str(self.val)

    def count(self, t: Node):
        return 0 if t is None else t.cnt

    def update(self, t: Node):
        t.cnt = self.count(t.left) + self.count(t.right) + 1
        return t

    def merge(self, l: Node, r: Node):
        if l is None: return r
        if r is None: return l
        if l.priority > r.priority:
            l.right = self.merge(l.right, r)
            return self.update(l)
        else:
            r.left = self.merge(l, r.left)
            return self.update(r)

    def split(self, t: Node, k: int) -> (Node, Node):  # [0,k),[k,n)
        if t is None: return None, None
        if k <= self.count(t.left):
            s = self.split(t.left, k)
            t.left = s[1]
            return s[0], self.update(t)
        else:
            s = self.split(t.right, k - self.count(t.left) - 1)
            t.right = s[0]
            return self.update(t), s[1]

    def insert(self, t: Node, k: int, x):
        l, r = self.split(t, k)
        return self.merge(self.merge(l, self.Node(x)), r)

    def erase(self, t: Node, k):
        l, r = self.split(t, k)
        _, r = self.split(r, 1)
        return self.merge(l, r)

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

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
e.sort()
q = deque()
for _ in range(p):
    q.append(int(input()))
s=Treap()

for t,f,x in e:
    while t > q[0]:
        q.popleft()
        if s.node:
            print(s[0])
        else:
            print(-1)
        if not q:
            sys.exit()
    if f == 1:
        s.add(x)
    else:
        s.remove(x)
        
while q:
    q.pop()
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import random
from collections import deque
import sys
sys.stdin.readline


class Node: # ノードの型
    def __init__(self, height, key, x):
        self.height = height # そのノードを根とする部分木の高さ
        self.key    = key    # そのノードのキー
        self.value  = x      # そのノードの値
        self.lst    = None   # 左部分木
        self.rst    = None   # 右部分木

# 部分木 t の高さを返す
def height(t): return 0 if t is None else t.height

# 左右の部分木の高さの差を返す。左が高いと正、右が高いと負
def bias(t): return height(t.lst) - height(t.rst)

# 左右の部分木の高さから、その木の高さを計算して修正する
def modHeight(t): t.height = 1 + max(height(t.lst), height(t.rst))

def rotateL(v): # ２分探索木 v の左回転。回転した木を返す
    u = v.rst; t2 = u.lst
    u.lst = v; v.rst = t2
    modHeight(u.lst)
    modHeight(u)
    return u
def rotateR(u): # ２分探索木 u の右回転。回転した木を返す
    v = u.lst; t2 = v.rst
    v.rst = u; u.lst = t2
    modHeight(v.rst)
    modHeight(v)
    return v
def rotateLR(t): # ２分探索木 t の二重回転(左回転 -> 右回転)。回転した木を返す
    t.lst = rotateL(t.lst)
    return rotateR(t)
def rotateRL(t): # ２分探索木 t の二重回転(右回転 -> 左回転)。回転した木を返す
    t.rst = rotateR(t.rst)
    return rotateL(t)

###############################################################################
# AVL木マップクラス
###############################################################################

class AVLMap:
    def __init__(self):
        self.root   = None  # AVL木の根。Node 型
        self.change = False # 修正が必要かを示すフラグ(True:必要, False:不要)
        self.lmax   = None  # 左部分木のキーの最大値
        self.value  = None  # lmax に対応する値

    ###########################################################################
    # バランス回復
    ###########################################################################

    # 挿入時の修正(balanceLi:左部分木への挿入, balanceRi:右部分木への挿入)
    def balanceLi(self, t): return self.balanceL(t)
    def balanceRi(self, t): return self.balanceR(t)

    # 削除時の修正(balanceLd:左部分木での削除, balanceRd:右部分木での削除)
    def balanceLd(self, t): return self.balanceR(t)
    def balanceRd(self, t): return self.balanceL(t)

    # 部分木 t のバランスを回復して戻り値で返す
    # 左部分木への挿入に伴うAVL木の修正
    # 右部分木での削除に伴うAVL木の修正
    def balanceL(self, t):
        if not self.change: return t
        h = height(t)
        if bias(t) == 2:
            if bias(t.lst) >= 0:
                t = rotateR(t)
            else:
                t = rotateLR(t)
        else: modHeight(t)
        self.change = (h != height(t))
        return t

    # 部分木 t のバランスを回復して戻り値で返す
    # 右部分木への挿入に伴うAVL木の修正
    # 左部分木での削除に伴うAVL木の修正
    def balanceR(self, t):
        if not self.change: return t
        h = height(t)
        if bias(t) == -2:
            if bias(t.rst) <= 0:
                t = rotateL(t)
            else:
                t = rotateRL(t)
        else: modHeight(t)
        self.change = (h != height(t))
        return t

    ###########################################################################
    # insert(挿入)
    ###########################################################################

    # エントリー(key, x のペア)を挿入する
    def insert(self, key, x): self.root = self.insert_sub(self.root, key, x)

    def insert_sub(self, t, key, x):
        if t is None:
            self.change = True
            return Node(1, key, x)
        elif key < t.key:
            t.lst = self.insert_sub(t.lst, key, x)
            return self.balanceLi(t)
        elif key > t.key:
            t.rst = self.insert_sub(t.rst, key, x)
            return self.balanceRi(t)
        else:
            self.change = False
            t.value = x
            return t

    ###########################################################################
    # delete(削除)
    ###########################################################################

    # key で指すエントリー(ノード)を削除する
    def delete(self, key): self.root = self.delete_sub(self.root, key)

    def delete_sub(self, t, key):
        if t is None:
            self.change = False
            return None
        elif key < t.key:
            t.lst = self.delete_sub(t.lst, key)
            return self.balanceLd(t)
        elif key > t.key:
            t.rst = self.delete_sub(t.rst, key)
            return self.balanceRd(t)
        else:
            if t.lst is None:
                self.change = True
                return t.rst # 右部分木を昇格させる
            else:
                t.lst = self.delete_max(t.lst) # 左部分木の最大値を削除する
                t.key = self.lmax # 左部分木の削除した最大値で置き換える
                t.value = self.value
                return self.balanceLd(t)

    # 部分木 t の最大値のノードを削除する
    # 戻り値は削除により修正された部分木
    # 削除した最大値を lmax に保存する
    def delete_max(self, t):
        if t.rst is not None:
            t.rst = self.delete_max(t.rst)
            return self.balanceRd(t)
        else:
            self.change = True
            self.lmax = t.key # 部分木のキーの最大値を保存
            self.value = t.value
            return t.lst # 左部分木を昇格させる

    ###########################################################################
    # member(検索)等
    ###########################################################################

    # キーの検索。ヒットすれば True、しなければ False
    def member(self, key):
        t = self.root
        while t is not None:
            if key < t.key:
                t = t.lst
            elif key > t.key:
                t = t.rst
            else:
                return True
        return False

    # キーから値を得る。キーがヒットしない場合は None を返す
    def lookup(self, key):
        t = self.root
        while t is not None:
            if key < t.key:
                t = t.lst
            elif key > t.key:
                t = t.rst
            else:
                return t.value
        return None

    # マップが空なら True、空でないなら False
    def isEmpty(self): return self.root is None

    # マップを空にする
    def clear(self): self.root = None

    # キーのリスト
    def keys(self): return keys_sub(self.root)

    # 値のリスト
    def values(self): return values_sub(self.root)

    # エントリーのリスト
    def items(self): return items_sub(self.root)

    # マップのサイズ
    def size(self): return len(self.keys())

    def __contains__(self, key): self.member(key)
    def __getitem__(self, key): return self.lookup(key)
    def __setitem__(self, key, x): return self.insert(key, x)
    def __delitem__(self, key): self.delete(key)
    def __bool__(self): return not self.isEmpty()
    def __len__(self): return self.size()
    def __iter__(self): return iter(self.keys())

    ###########################################################################
    # Debug 用メソッド
    ###########################################################################

    # AVL木をグラフ文字列に変換する
    def __str__(self): return toGraph("", "", self.root).rstrip()

    # AVL木のバランスが取れているか確認する
    def balanced(self): return balanced(self.root)

    # ２分探索木になっているか確認する
    def bstValid(self): return bstValid(self.root)
      
      
def keys_sub(t):
    if t is None: return []
    return keys_sub(t.lst) + [t.key] + keys_sub(t.rst)

def values_sub(t):
    if t is None: return []
    return values_sub(t.lst) + [t.value] + values_sub(t.rst)

def items_sub(t):
    if t is None: return []
    return items_sub(t.lst) + [(t.key, t.value)] + items_sub(t.rst)

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

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
e.sort()
q = deque()
for _ in range(p):
    q.append(int(input()))
s=AVLMap()

for t,f,x in e:
    while t > q[0]:
        q.popleft()
        if s:
            print(next(iter(s)))
        else:
            print(-1)
        if not q:
            sys.exit()
    if f == 1:
        s.insert(x, 1)
    else:
        s.delete(x)
        
while q:
    q.pop()
    print(-1)