Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict


MAX_INT = 2**62-1
sys.setrecursionlimit(10**6)

input = sys.stdin.readline


N = 2 * (10**5) + 1
MOD = 10**9 + 7

fact = [1] * N
fact_inv = [0] * N

for i in range(1, 2 * (10**5)+1):
    fact[i] = fact[i-1] * i % MOD
    fact_inv[i] = pow(fact[i], MOD-2, MOD)


def solve(g):
    def dfs(pre, cur):
        if (pre, cur) in memo:
            return memo[pre,cur]

        num, ways = 1, 1

        for nxt in g[cur]:
            if nxt == pre:
                continue
            n, w = dfs(cur, nxt)
            num += n
            ways = ways * w % m * fi[n] % m

        ways = ways * f[num-1] % m
        memo[pre, cur] = num, ways
        return num, ways

    m = MOD
    memo = {}
    f, fi = fact, fact_inv

    stack = [(None, 1)]
    while stack:
        pre, cur = stack.pop()
        dfs(None, cur)

        for nxt in g[cur]:
            if nxt == pre:
                continue
            stack.append((cur, nxt))

    print(*[memo[None, i][1] for i in range(1, len(g))], sep='\n')


def main():
    n = int(input())
    g = [[] for _ in range(n+1)]

    for _ in range(n-1):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)

    solve(g)


if __name__ == "__main__":

    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from functools import reduce

MAX_INT = 2**62-1
sys.setrecursionlimit(10**7)

input = sys.stdin.readline

# @profile
MOD = 10**9 + 7


def mul_mod(*args, mod=MOD):
    return reduce(lambda a, b: a * b % mod, args)


def solve(g, f, fi, m):
    mul = mul_mod

    stack = [(0, 1)]
    pre_order = []
    n = len(g) - 1

    while stack:
        pre, cur = stack.pop()
        pre_order.append((pre, cur))

        for nxt in g[cur]:
            if nxt == pre:
                continue
            stack.append((cur, nxt))

    size = [1] * (n+1)
    dp = [1] * (n+1)

    for pre, cur in reversed(pre_order):
        dp[cur] = mul(dp[cur], f[size[cur]-1])
        dp[pre] = mul(dp[pre], dp[cur], fi[size[cur]])
        size[pre] += size[cur]

    ans = [1] * (n+1)
    ans[1] = dp[1]

    for pre, cur in pre_order[1:]:
        i = size[cur]
        temp = mul(ans[pre], f[n-i-1], fi[n-1], f[i], pow(dp[cur], m-2, m))
        ans[cur] = mul(f[n-1], temp, fi[n-i], dp[cur], fi[i-1])
    print(*ans[1:], sep='\n')


# @profile
def main():
    mul = mul_mod
    mod = MOD
    n = int(input())
    g = [[] for _ in range(n+1)]

    fact = [1] * (n+1)
    fact_inv = [0] * (n+1)

    for i in range(1, n+1):
        fact[i] = mul(fact[i-1], i)

    fact_inv[-1] = pow(fact[-1], mod-2, mod)

    for i in range(n)[::-1]:
        fact_inv[i] = mul(fact_inv[i+1], (i+1))

    for _ in range(n-1):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)

    solve(g, fact, fact_inv, mod)


if __name__ == "__main__":

    main()
### BUGGY CODE ###

P = int(input())
A = [int(_) for _ in input().split()]


class Factorial:
    def __init__(self, max_fact, mod):
        #mod should be prime number
        #using homogeneous_product(n,r), max_fact ≧ max(n+r-1)
        f = [1] * (max_fact + 1)
        for idx in range(2, max_fact + 1):
            f[idx] = f[idx - 1] * idx
            f[idx] %= mod
        fi = [pow(f[-1], mod - 2, mod)]
        for idx in range(max_fact, 0, -1):
            fi += [fi[-1] * idx % mod]
        fi = fi[::-1]
        self.mod = mod
        self.f = f
        self.fi = fi

    def factorial(self, n):
        return self.f[n]

    def factorial_inverse(self, n):
        return self.fi[n]

    def combination(self, n, r):
        f = self.f
        fi = self.fi
        return f[n] * fi[r] * fi[n - r] % self.mod

    def permutation(self, n, r):
        return self.f[n] * self.fi[n - r] % self.mod

    def homogeneous_product(self, n, r):
        f = self.f
        fi = self.fi
        return f[n + r - 1] * fi[r] * fi[n - 1] % self.mod


max_fact = P - 1
mod = P
fact_instance = Factorial(max_fact, mod)
comb = fact_instance.combination
perm = fact_instance.permutation
combrep = fact_instance.homogeneous_product

ans = [0] * P
for i, a in enumerate(A):
    if a:
        #1-(x-i)^(P-1)
        ans[0] += 1
        for r in range(P):
            ans[r] -= comb(P - 1, r) * pow(-i, P - 1 - r, P)
print(*[j % P for j in ans])


### FIXED CODE ###

P = int(input())
A = [int(_) for _ in input().split()]


class Factorial:
    def __init__(self, max_fact, mod):
        #mod should be prime number
        #using homogeneous_product(n,r), max_fact ≧ max(n+r-1)
        f = [1] * (max_fact + 1)
        for idx in range(2, max_fact + 1):
            f[idx] = f[idx - 1] * idx
            f[idx] %= mod
        fi = [pow(f[-1], mod - 2, mod)]
        for idx in range(max_fact, 0, -1):
            fi += [fi[-1] * idx % mod]
        fi = fi[::-1]
        self.mod = mod
        self.f = f
        self.fi = fi

    def factorial(self, n):
        return self.f[n]

    def factorial_inverse(self, n):
        return self.fi[n]

    def combination(self, n, r):
        f = self.f
        fi = self.fi
        return f[n] * fi[r] * fi[n - r] % self.mod

    def permutation(self, n, r):
        return self.f[n] * self.fi[n - r] % self.mod

    def homogeneous_product(self, n, r):
        f = self.f
        fi = self.fi
        return f[n + r - 1] * fi[r] * fi[n - 1] % self.mod


max_fact = P - 1
mod = P
fact_instance = Factorial(max_fact, mod)
comb = fact_instance.combination
perm = fact_instance.permutation
combrep = fact_instance.homogeneous_product

ans = [0] * P
for i, a in enumerate(A):
    if a:
        #1-(x-i)^(P-1)
        ans[0] += 1
        for r in range(P):
            ans[r] -= comb(P - 1, r) * pow(-i, P - 1 - r, P)
            ans[r] %= mod
print(*ans)
### BUGGY CODE ###

class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n+1)]  #親のノード番号
        self.rank = [0]*(n+1)
    def find(self,x):  #xの根のノード番号
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def same_check(self,x,y):  #x,yが同じグループか否か
        return self.find(x) == self.find(y)
    def union(self,x,y):  #x,yの属するグループの併合
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            self.rank[x] += 1

N,K,L = map(int,input().split())
A = [list(map(int,input().split())) for i in range(K)]
B = [list(map(int,input().split())) for i in range(L)]

road = UnionFind(N)
train = UnionFind(N)

for i in range(K):
    road.union(A[i][0],A[i][1])
for i in range(L):
    train.union(B[i][0],B[i][1])

pair = [(road.find(i),train.find(i)) for i in range(1,N+1)]

from collections import Counter

#根が同じなら道路or鉄道でつなげる

c = Counter(pair)
ans = str(c[(road.find(1),train.find(1))])
for i in range(2,N+1):
    ans = ans + ' ' + str(c[(road.find(i),train.find(i))])

print(ans)

### FIXED CODE ###

class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n+1)]  #親のノード番号
        self.rank = [0]*(n+1)
    def find(self,x):  #xの根のノード番号
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def same_check(self,x,y):  #x,yが同じグループか否か
        return self.find(x) == self.find(y)
    def union(self,x,y):  #x,yの属するグループの併合
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            self.rank[x] += 1

N,K,L = map(int,input().split())
A = [list(map(int,input().split())) for i in range(K)]
B = [list(map(int,input().split())) for i in range(L)]

road = UnionFind(N)
train = UnionFind(N)

for i in range(K):
    road.union(A[i][0],A[i][1])
for i in range(L):
    train.union(B[i][0],B[i][1])

pair = [(road.find(i),train.find(i)) for i in range(1,N+1)]

from collections import Counter

#根が同じなら道路or鉄道でつなげる

c = Counter(pair)
print(*[c[i] for i in pair])
### BUGGY CODE ###

def main():
    s = input()
    flag = True
    l = [""]
    ans = 0
    sm = [i for i in range(0,len(s)+1)]
    for i in range(1,len(sm)):
        sm[i] = sm[i-1]+sm[i]
    for i in range(len(s)):
        if flag:
            l[-1] = l[-1] + s[i]
        else:
            l.append(s[i])
        if i < len(s)-1:
            if s[i] == "<" and s[i+1] == ">":
                flag = False
            else:
                flag = True
    xlist = []
    ylist = []
    for i in l:
        x = 0
        y = 0
        for j in list(i):
            if j == ">":
                x += 1
            else:
                y += 1
        xlist.append(x)
        ylist.append(y)
    for i in range(1,len(l)):
        if ylist[i-1] <= xlist[i]:
            ylist[i-1] = max([0,ylist[i-1]-1])
        else:
          xlist[i] = max([0,xlist[i]-1])
    for i in xlist:
        ans += sm[i]
    for i in ylist:
        ans += sm[i]
    print(ans)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    s = input()
    f1 = False
    f2 = False
    l = [1]
    if s[0] == "<":
        f1 = True
        l.insert(0,0)
    if s[-1] == ">":
        f2 = True
    sm = [i for i in range(0,len(s)+1)]
    for i in range(1,len(sm)):
        sm[i] = sm[i-1]+sm[i]
    lap = l.append
    for i in range(1,len(s)):
        if s[i] == s[i-1]:
            l[-1] += 1
        else:
            lap(1)
    dlist = []
    plist = []
    dap = dlist.append
    pap = plist.append
    if f2:
        l.append(0)
    for i in range(len(l)//2):
        dap(l[2*i])
        pap(l[2*i+1])   
    for i in range(1,len(dlist)):
        x = dlist[i]
        y = plist[i-1]
        if y <= x:
            dlist[i] = sm[x]
            plist[i-1] = sm[max([0,y-1])]
        else:
          dlist[i] = sm[max([0,x-1])]
          plist[i-1] = sm[y]
    dlist[0] = sm[dlist[0]]
    plist[-1] = sm[plist[-1]]
    print(sum(dlist)+sum(plist))
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n=int(input())
h=list(map(int,input().split()))
a=0
i=1


while True:
    for i in range(n):
        for j in range(i-1):
            if h[i]<h[j]:
                break
        a+=1

print(a)

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
a=1

for i in range(1,n):
    for j in range(i):
        if h[i]<h[j]:break
        elif j==i-1:
            a+=1

print(a)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
bidx = 0
cidx = 0
abnums = [0] * (N+1)
bcnums = [0] * (N+1)
idx = 0
for i, a in enumerate(A):
    abnums[i+1] = abnums[i]
    if abnums[i+1] == N:
        continue
    for j, b in enumerate(B[idx:]):
        if a < b:
            abnums[i+1] += 1
        else:
            idx = j + idx
            break

idx = 0
for i, b in enumerate(B):
    bcnums[i+1] = bcnums[i]
    if bcnums[i+1] == N:
        continue
    for j, c in enumerate(C[idx:]):
        if b < c:
            bcnums[i+1] += 1
        else:
            idx = j + idx
            break

for i in range(1, N+1):
    bcnums[i] += bcnums[i-1]

ans = 0
for n in abnums[1:]:
    ans += bcnums[n]
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()
idxa = 0
idxc = 0
ans = 0
for b in range(N):
    while idxa < N and A[idxa] < B[b]:
        idxa += 1
    while idxc < N and B[b] >= C[idxc]:
        idxc += 1
    ans += idxa * (N - idxc)
print(ans)
### BUGGY CODE ###

n= int(input())

v = list(map(int,input().split()))
c = list(map(int,input().split()))


x_y = 0
for i in range(2**n):

    tmp_x_y = 0
    tmp_cost=0
    tmp_value=0

    for j in range(n):
        if (i>>j) &1:
            tmp_cost+=c[j]
            tmp_value+=v[j]

    tmp_x_y = tmp_value - tmp_cost

    x_y = max(x_y,tmp_x_y)

print(x_y)

### FIXED CODE ###

n= int(input())

v = list(map(int,input().split()))
c = list(map(int,input().split()))


x_y = 0
for i in range(2**n):

    tmp_x_y = 0
    tmp_cost=0
    tmp_value=0

    for j in range(n):
        if (i>>j) &1:
            tmp_cost+=c[j]
            tmp_value+=v[j]

    tmp_x_y = tmp_value - tmp_cost

    x_y = max(x_y,tmp_x_y)

print(x_y)
### BUGGY CODE ###

s = input()[::-1]
l = len(s)
x = [0 for _ in range(2019)]
x[0] += 1
p = ''
for si in s:
    p = si + p
    k = int(p) % 2019
    x[k] += 1

ans = 0
for xi in x:
    ans += max(0, xi * (xi - 1) // 2)
print(ans)


### FIXED CODE ###

s = input()[::-1]
l = len(s)
x = [0 for _ in range(2019)]
x[0] += 1
k = 0
p = 1
for si in s:
    k += int(si) * p % 2019
    k %= 2019
    x[k] += 1
    p *= 10
    p %= 2019

ans = 0
for xi in x:
    ans += max(0, xi * (xi - 1) // 2)
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()

n += 1
s += "#"

ans = 0
for i in range(1, n):
    cnt = 0
    for j in range(n-i):
        if s[i+j] == s[j]:
            cnt += 1
        else:
            ans = max(ans, min(cnt, i))
            cnt = 0

print(ans)


### FIXED CODE ###

n = int(input())
s = input()

n += 1
s += "#"

ans = 0
for i in range(1, n):
    cnt = 0
    for j in range(n-i):
        if s[i+j] == s[j]:
            cnt += 1
        else:
            ans = max(ans, min(cnt, i))
            cnt = 0

print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
f = True

if N%2==0:
  for i in range(1,N,2):
    if A.count(i)!=2:
      f = False
else:
  for i in range(2,N,2):
    if A.count(i)!=2:
      f = False

if f:
  print(2**(N//2))
else:
  print(0)

### FIXED CODE ###

N = int(input())
A = sorted(list(map(int,input().split())))

if N%2==0:
  B = [2*(i//2)+1 for i in range(N)]
else:
  B = [2*(i//2) for i in range(1,N+1)]

if A==B:
  print(pow(2,N//2,10**9+7))
else:
  print(0)
### BUGGY CODE ###

# encoding: utf-8
N, M = list(map(int, input().split()))

# TLE
# Amod = [A for A in map(lambda x: int(x) % M , input().split())]
# ans = 0
# for l in range(len(Amod)):
#     acm = 0
#     for r in range(l, len(Amod)):
#         acm = (acm + Amod[r]) % M
#         if acm == 0: ans += 1

# Asym = []
# sym = 0
# for A in map(int, input().split()):
#     sym = (sym + A) % M
#     Asym.append(sym)
# print(Asym)
    
# ans = Asym.count(0)
# for sym in set(Asym):
#     cnt = Asym.count(sym)
#     ans +=  int(cnt * (cnt -  1) / 2)

# print(ans)

Acnt = [0 for i in range(M)]
sym = 0
for A in map(int, input().split()):
    sym = (sym + A) % M
    Acnt[sym] += 1

print(int(Acnt[0] + sum([cnt * (cnt - 1) for cnt in Acnt]) / 2))


### FIXED CODE ###

# encoding: utf-8
N, M = list(map(int, input().split()))

d_sym = {}
sym = 0

# refresh

ans = 0
for A in map(int, input().split()):
    sym = (sym + A) % M
    #
    if sym == 0: ans += 1
    # 
    if str(sym) in d_sym.keys(): d_sym[str(sym)] += 1
    else: d_sym[str(sym)] = 1

print(int(ans + sum([val * (val - 1) / 2 for val in d_sym.values()])))
### BUGGY CODE ###

number,money=input().rstrip().split()
number=int(number)
money=int(money)
bill=[0,0,0]

for i in range(number+1):
    bill=[0,0,0]
    mass=money-10000*i
    bill[0]=i
    if mass==0 and sum(bill)==number:
        break
    elif mass<0:
        break
    else:
        for j in range(number+1):
            if j!=0:
                mass=mass-5000
            bill[1]=j
            if mass==0 and sum(bill)==number:
                break
            elif mass<0:
                break
            else:
                k=int(mass/1000)
                bill[2]=k
                if sum(bill)==number:
                    break
    if sum(bill)==number:
        mass=0
        if mass==0:
            break
                
if mass==0:
    print(str(bill[0])+' '+str(bill[1])+' '+str(bill[2]))
else:
    print(str(-1)+' '+str(-1)+' '+str(-1))


### FIXED CODE ###

number,money=input().rstrip().split()
number=int(number)
money=int(money)
bill=[0,0,0]

for i in range(number+1):
    bill=[0,0,0]
    mass=money-10000*i
    bill[0]=i
    if mass==0 and sum(bill)==number:
        break
    elif mass<0:
        break
    else:
        for j in range(number+1-i):
            if j!=0:
                mass=mass-5000
            bill[1]=j
            if mass==0 and sum(bill)==number:
                break
            elif mass<0:
                break
            else:
                k=int(mass/1000)
                bill[2]=k
                if sum(bill)==number:
                    break
    if sum(bill)==number:
        mass=0
        break
                
if mass==0:
    print(str(bill[0])+' '+str(bill[1])+' '+str(bill[2]))
else:
    print(str(-1)+' '+str(-1)+' '+str(-1))
### BUGGY CODE ###



N = int(input())

S = [input() for _ in range(N)]

"""
あるA,Bを決めたときに、A+1,B+1と比べると、全ての文字が右下にずれるので、(A,B)と(A+1,B+1)の結果は同じになる
"""

cnt = 0
for a in range(N):
    S2 = [["" for _ in range(N)]  for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if 0 <= i + a <= N-1:
                y = i + a
            else:
                y = (i + a) - N
            S2[y][j] = S[i][j]
    
    flag = True
    for i in range(N):
        if not flag:
            break
        for j in range(N):
            if i == j:
                continue
            if S2[i][j] != S2[j][i]:
                flag = False
                break
    if flag:
        cnt += 1

print(cnt * N)


### FIXED CODE ###




def main():
        
    N = int(input())

    S = [input() for _ in range(N)]

    """
    あるA,Bを決めたときに、A+1,B+1と比べると、全ての文字が右下にずれるので、(A,B)と(A+1,B+1)の結果は同じになる
    """
    S2 = [["" for _ in range(N)]  for _ in range(N)]
    cnt = 0
    for a in range(N):
        
        for i in range(N):
            for j in range(N):
                if 0 <= i + a <= N-1:
                    y = i + a
                else:
                    y = (i + a) - N
                S2[y][j] = S[i][j]
        
        flag = True
        for i in range(N):
            if not flag:
                break
            for j in range(N):
                if i == j:
                    continue
                if S2[i][j] != S2[j][i]:
                    flag = False
                    break
        if flag:
            cnt += 1

    print(cnt * N)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

def _input(n):
    return [int(raw_input()) for i in xrange(n)]

def LIS(arr):
    arr = [0] + arr
    L = [0] + [0] * len(arr)
    P = [-1] + [0] * len(arr)

    for i in xrange(1, len(arr)):
        k = 0
        for j in xrange(0, i):
            if arr[j] < arr[i] and L[j] > L[k]:
                k = j
        L[i] = L[k] + 1
        P[i] = k

    return max(L)

#==============================================
def main():
    n = int(raw_input())
    arr = _input(n)
    print LIS(arr)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import bisect

def _input(n):
    return [int(raw_input()) for i in xrange(n)]

# Wrapper for built-in function
def lower_bound(arr, target):
    return bisect.bisect_right(arr, target)


def LIS(arr, n):
    L = [0] * n

    L[0] = arr[0]
    length = 1

    for i in xrange(1, n):
        if L[length - 1] < arr[i]:
            L[length] = arr[i]#L.append(A[i])
            length += 1
        else:
            if L[lower_bound(L[:length], arr[i])-1 if lower_bound(L[:length], arr[i])-1 > 0 else 0] \
                    != arr[i]: # Fix common item - Dont insert common item and zero Problem
                L[lower_bound(L[:length], arr[i])] = arr[i]
    return length, L

#=========================================================
def main():

    n = int(raw_input())
    arr = _input(n)
    print LIS(arr, n)[0]#, LIS(arr, n)[1]#, arr

if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

sum = 0
num = 0
nm = [1,0,-1]

c = 0

while True:
    if n[num] == 0:
        num += 1
        continue
    sum += nm[num]
    n[num]-=1
    c+=1
    if c == n[3]:
        break


print(sum)


### FIXED CODE ###

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

sum = 0
num = 0
nm = [1,0,-1]
c = n[3]
cu =0


for i in n:
    if c == 0:
        break
    if i > c:
        sum+= nm[num]*c
        break
    if i <= c:
        sum += nm[num] * i
        c-=i
        num+=1




print(sum)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, Q = MAP()
# 3種類の状態変化をイベントとして一括管理する
# 0: 工事終了, 1: 工事開始, 2: 人の出発
events = []
for i in range(N):
    s, t, x = MAP()
    # (開始座標に合わせた状態の工事開始時間, フラグ, 実際の座標)
    events.append((s-x, 1, x))
    # (開始座標に合わせた状態の工事終了時間, フラグ, 実際の座標)
    events.append((t-x, 0, x))
for i in range(Q):
    d = INT()
    # (人の出発時間, フラグ, index)
    events.append((d, 2, i))
# 時系列に沿ってソート、フラグも同時刻な時先に処理して欲しいものから番号を振ってある
events.sort()

# setとheapqを合わせて、時刻に合わせた処理と最小値取得を行う
S = set()
hp = []
ans = [0] * Q
for t, flag, x in events:
    # 工事終了
    if flag == 0:
        S.remove(x)
    # 工事開始
    elif flag == 1:
        S.add(x)
        heappush(hp, x)
    # 人の移動
    elif flag == 2:
        # heapqの先頭要素ついて、setと状態を合わせる
        while len(hp) and hp[0] not in S:
            heappop(hp)
        if len(hp):
            ans[x] = hp[0]
        else:
            ans[x] = -1
[print(a) for a in ans]


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, Q = MAP()
# 3種類の状態変化をイベントとして一括管理する
# 0: 工事終了, 1: 工事開始, 2: 人の出発
events = []
for i in range(N):
    s, t, x = MAP()
    # (開始座標に合わせた状態の工事開始時間, フラグ, 実際の座標)
    events.append((s-x, 1, x))
    # (開始座標に合わせた状態の工事終了時間, フラグ, 実際の座標)
    events.append((t-x, 0, x))
for i in range(Q):
    d = INT()
    # (人の出発時間, フラグ, index)
    events.append((d, 2, i))
# 時系列に沿ってソート、フラグも同時刻な時先に処理して欲しいものから番号を振ってある
events.sort()

# setとheapqを合わせて、時刻に合わせた処理と最小値取得を行う
S = set()
hp = []
ans = [0] * Q
for t, flag, x in events:
    # 工事終了
    if flag == 0:
        S.remove(x)
    # 工事開始
    elif flag == 1:
        S.add(x)
        heappush(hp, x)
    # 人の移動
    elif flag == 2:
        # heapqの先頭要素ついて、setと状態を合わせる
        while len(hp) and hp[0] not in S:
            heappop(hp)
        if len(hp):
            ans[x] = hp[0]
        else:
            ans[x] = -1
[print(a) for a in ans]