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

import collections
import sys
input = sys.stdin.readline
from array import array
def solve():
  n = int(input())
  query2 = []
  ans = array('I', [ 0 for i in range(n)])
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    query2.append(a)
    query2.append(b)
    
  c = list(int(i) for i in input().split())
  c = sorted(c,reverse =True)
  
  d = collections.Counter(query2)
  
  nl = 0
  nr = 0
  for i in range(len(d)):
    ans[d.most_common()[i][0]-1] = c[i]
    
  print(sum(c) +(-1)*max(c))
  #dの処理
  print(*ans)
  
solve()

### FIXED CODE ###

import collections
import sys
input = sys.stdin.readline
import heapq
from array import array
def solve():
  n = int(input())

  query2 = collections.deque([])
  edge = [[] for _ in range(n)]
  ans = array('I', [ 0 for i in range(n)])
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    query2.append(a)
    query2.append(b)
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
  c = list(int(i) for i in input().split())
  if n == 1:
    print(1)
    print(c[0])
    exit()
  c = collections.deque(sorted(c,reverse =True))
  d = collections.Counter(query2)
  d2 = d.most_common()
  bfs = []
  heapq.heappush(bfs,(-1*d2[0][1],d2[0][0]-1,-1))#回数,場所、親
  ct = 0
  visit = [False]*n
  while bfs:
    times,place,parent = heapq.heappop(bfs)
    if visit[place]:
      continue
    else:
      visit[place] = True

      for i in range(len(edge[place])):
        newp = edge[place][i]
        newtimes = len(edge[newp])
        if not visit[newp]:
          heapq.heappush(bfs,(-1*newtimes,newp,place))
      #print(place,parent,times)
      ans[place] = c.popleft()

      #print(c,place)

  print(sum(ans)-max(ans))
  print(*ans)
  
solve()
### BUGGY CODE ###

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))


def binarysearch(key, a, length):
    left = 0
    right = length-1
    while left < right:
        mid = int((left + right)/2)
        if a[mid] == key:
            return True
        elif key < a[mid]:
            right = mid
        else:
            left = mid
    return False


cnt = 0
for i in T:
    if binarysearch(i, S, n):
        cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))


def binarysearch(key, a, length):
    left = 0
    right = length
    while left < right:
        mid = int((left + right)/2)
        if a[mid] == key:
            return True
        elif key < a[mid]:
            right = mid
        else:
            left = mid+1
    return False


cnt = 0
for i in T:
    if binarysearch(i, S, n):
        cnt += 1
print(cnt)
### BUGGY CODE ###

N, M = map(int, input().split())
l, m = map(int, input().split())
ans = set(list(range(l, m+1)))
for i in range(M-1):
    l, m = map(int, input().split())
    ans = ans & set(list(range(l, m+1)))
print(len(ans))
    

### FIXED CODE ###

N, M = map(int, input().split())
l = 1
m = N
for i in range(M):
    l_i, m_i = map(int, input().split())
    l = max(l, l_i)
    m = min(m, m_i)
if m < l:
    print(0)
else:
    print(m - l + 1)
### BUGGY CODE ###

N,K = map(int, input().split())
A = [0]+list(map(int,input().split()))
inf = float('INF')
costs = [inf for i in range(N+1)]
costs[0] = costs[1] = 0
for i in range(1,N+1):
    for j in range(i+1,i+K+1):
        if j > N:
            break
        costs[j] = min(costs[i]+abs(A[i]-A[j]), costs[j])
print(costs[N])


### FIXED CODE ###

N,K = map(int, input().split())
A = [0]+list(map(int,input().split()))
inf = float('INF')
costs = [inf for i in range(N+1)]
costs[0] = costs[1] = 0
for i in range(1,N+1):
    for j in range(i+1,i+K+1):
        if j > N:
            break
        costs[j] = min(costs[i]+abs(A[i]-A[j]), costs[j])
print(costs[N])
### BUGGY CODE ###

n,m = map(int, input().split())
p = [0] * m
s = [0] * m
for i in range(m):
    p[i],s[i] = map(str,input().split())
    p[i] = int(p[i])

ac = []
for i in range(m):
    if s[i] == 'AC':
        ac.append(p[i])

ac = list(set(ac))

first_sub = []
for i in ac:
    for j in range(m):
        if p[j] == i:
            first_sub.append(j)
            break

ans_ng = 0
for i in range(len(ac)):
    ng = 0
    for j in range(first_sub[i],m):
        if p[j] == ac[i] and s[j] == 'WA':
            ng += 1
        elif p[j] == ac[i] and s[j] == 'AC':
            break
    ans_ng += ng
            


print(len(ac),ans_ng)


### FIXED CODE ###

n,m = map(int, input().split())
p = [0] * m
s = [0] * m
for i in range(m):
    p[i],s[i] = map(str,input().split())
    p[i] = int(p[i])

ac = [0] * (n+1)
wa = [0] * (n+1)
for i in range(m):
    if s[i] == 'WA':
        if ac[p[i]] == 0:
            wa[p[i]] += 1
        else:
            pass
    if s[i] == 'AC':
        ac[p[i]] = 1

ac_num = 0
for i in range(len(ac)):
    if ac[i] != 0:
        ac_num += 1
ng = 0
for i in range(len(wa)):
    if ac[i] != 0:
        ng += wa[i]
            
print(ac_num,ng)
### BUGGY CODE ###

N = int(input())

S = input()
w = [0]*N
e = [0]*N
ans = N
for i in range(N):
    if S[i] == "W":
        w[i] = 1
    else:
        e[i] = 1

for i in range(N):
    d = sum(w[:i]) + sum(e[i+1:])
    ans = min(ans,d)
    
print(ans)    

### FIXED CODE ###

N = int(input())

S = input()

w = [0]*(N+1)
e = [0]*(N+1) 

for i in range(N):
    if S[i] == "W":
        w[i+1] = 1
    
    if S[i] == "E":
        e[i+1] = 1

for i in range(N):
    w[i+1] += w[i]
    e[i+1] += e[i]

ans = N
for i in range(1,N+1):
    d = w[i-1] + e[N]-e[i]
    ans = min(ans,d)

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

import sys
input = sys.stdin.readline
from collections import deque
h,w,k = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
grid = [input().rstrip() for i in range(h)]
dp = [[10**18 for i in range(w)] for j in range(h)]
dp[sx-1][sy-1] = 0
q = deque()
q.append((sx-1,sy-1,0,1))
while q:
  px,py,direc,dis = q.popleft()
  for j in range(1 if direc != "U" else dis,k+1):
    if px+j >= h or grid[px+j][py] == "@" or dp[px+j][py] <= dp[px][py]:
      break
    dp[px+j][py] = dp[px][py]+1
    q.append((px+j,py,"U",k-j+1))
  for j in range(1 if direc != "D" else dis,k+1):
    if px-j < 0 or grid[px-j][py] == "@" or dp[px-j][py] <= dp[px][py]:
      break
    dp[px-j][py] = dp[px][py]+1
    q.append((px-j,py,"D",k-j+1))
  for j in range(1 if direc != "L" else dis,k+1):
    if py+j >= w or grid[px][py+j] == "@" or dp[px][py+j] <= dp[px][py]:
      break 
    dp[px][py+j] = dp[px][py]+1
    q.append((px,py+j,"L",k-j+1))
  for j in range(1 if direc != "R" else dis,k+1):
    if py-j < 0 or grid[px][py-j] == "@" or dp[px][py-j] <= dp[px][py]:
      break
    dp[px][py-j] = dp[px][py]+1
    q.append((px,py-j,"R",k-j+1))
if dp[gx-1][gy-1] == 10**18:
  print(-1)
else:
  print(dp[gx-1][gy-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque
h,w,k = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
grid = [input().rstrip() for i in range(h)]
dp = [[10**6 for i in range(w)] for j in range(h)]
dp[sx-1][sy-1] = 0
q = deque()
q.append((sx-1,sy-1))
while q:
  px,py = q.popleft()
  d = dp[px][py]
  for j in range(1,k+1):
    if px+j >= h or grid[px+j][py] == "@" or dp[px+j][py] <= d:
      break
    if dp[px+j][py] == 10**6:
      dp[px+j][py] = d+1
      q.append((px+j,py))
  for j in range(1,k+1):
    if px-j < 0 or grid[px-j][py] == "@" or dp[px-j][py] <= d:
      break
    if dp[px-j][py] == 10**6:
      dp[px-j][py] = d+1
      q.append((px-j,py))
  for j in range(1,k+1):
    if py+j >= w or grid[px][py+j] == "@" or dp[px][py+j] <= d:
      break 
    if dp[px][py+j] == 10**6:
      dp[px][py+j] = d+1
      q.append((px,py+j))
  for j in range(1,k+1):
    if py-j < 0 or grid[px][py-j] == "@" or dp[px][py-j] <= d:
      break
    if dp[px][py-j] == 10**6:
      dp[px][py-j] = d+1
      q.append((px,py-j))
if dp[gx-1][gy-1] == 10**6:
  print(-1)
else:
  print(dp[gx-1][gy-1])
### BUGGY CODE ###

def main():
  MOD=10**9+7
  import sys
  input = sys.stdin.readline
  N=int(input())
  A=list(map(int,input().split()))
  def lcm(a,N):
      from fractions import gcd
      x = a[0]
      y=  a[N//2]
      for i in range(1, N//2):
          x = (x * a[i]) // gcd(x, a[i])
          y = (y * a[i+N//2]) // gcd(y, a[i+N//2])
      y = (y * a[-1]) // gcd(y, a[-1])
      return (x*y)//gcd(x,y)
  z=lcm(A,N)
  ans=0
  import numpy as np
  A=np.array(A)
  ans=0
  for i in range(N):
    ans+=z//A[i]
  print(ans%MOD)
  
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  MOD=10**9+7
  N=int(input())
  A=list(map(int,input().split()))
  def lcm(a,N):
      from fractions import gcd
      x = a[0]
      y=  a[N//2]
      for i in range(1, N//2):
          x = (x * a[i]) // gcd(x, a[i])
          y = (y * a[i+N//2]) // gcd(y, a[i+N//2])
      y = (y * a[-1]) // gcd(y, a[-1])
      return (x*y)//gcd(x,y)
  z=lcm(A,N)
  ans=0
  for i in range(N):
    ans+=z//A[i]
  print(ans%MOD)
  
if __name__=='__main__':
  main()
### BUGGY CODE ###

import numpy as np

def resolve():
  N, M = map(int, input().split(" "))
  rooms = [None] * N

  def search_and_mark(recent_rooms, AB, depth):
    if None not in rooms:
      return rooms

    tmp_rooms = []
    for r in recent_rooms:
      tmp = AB[np.any(AB == r, axis=1)]
      target = tmp[tmp != r]
      tmp_rooms.extend(target)
      
      for t in target:
        if rooms[t] == None:
          rooms[t] = r

    recent_rooms = list(set(tmp_rooms))
    return search_and_mark(recent_rooms, AB, depth+1)

  AB = []
  for m in range(M):
    AB.append([int(x) - 1 for x in input().split(" ")])

  AB = np.array(AB)
  result = search_and_mark([0], AB, 0)

  print("Yes")
  for r in result[1:]:
    print(r + 1)

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
  N, M = map(int, input().split(" "))
  AB_map = [[] for i in range(N)]
  for m in range(M):
    AB = [int(x) - 1 for x in input().split(" ")]
    AB_map[AB[0]].append(AB[1])
    AB_map[AB[1]].append(AB[0])

  not_finished = set(range(1, N+1))
  rooms = [None] * N
  rooms[0] = 0
  room_depths = [0] * N

  recent_rooms = [0]
  depth = 1
  while len(not_finished) != 0 and depth < N:
    temp_recent = set()
    for r in recent_rooms:
      for target in AB_map[r]:
        if target in not_finished:
          temp_recent.add(target)
          not_finished.remove(target)
          rooms[target] = r
          room_depths[target] = depth
    depth += 1
    recent_rooms = list(temp_recent)

  print("Yes")
  for r in rooms[1:]:
    print(r + 1)

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

N = int(input())
A = list(map(int,input().split()))
for i in range(N):
  print(A.count(i+1))
  

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans =[0]*N
for i in A:
  ans[i-1] += 1
for i in range(N):
  print(ans[i])
### BUGGY CODE ###

MOD = 998244353
s = input()
n = len(s)
R = s.count("0") * 2 + s.count("1")
B = 2*n - R
rb = [[R, B] for _ in range(2*n)]
if s[0] == "0":
	rb[0] = [2, 0]
elif s[0] == "1":
	rb[0] = [1, 1]
else:
	rb[0] = [0, 2]
for i in range(1, n):
	if s[i] == "0":
		rb[i] = [rb[i-1][0] + 2, rb[i-1][1] + 0]
	elif s[i] == "1":
		rb[i] = [rb[i-1][0] + 1, rb[i-1][1] + 1]
	else:
		rb[i] = [rb[i-1][0] + 0, rb[i-1][1] + 2]

dp = [[0 for _ in range(R+1)] for _ in range(2*n)]
if rb[0][0] >= 1:
	dp[0][1] = 1
if rb[0][1] >= 1:
	dp[0][0] = 1
for i in range(1, 2*n):
	for j in range(R+1):
		if j > 0 and rb[i][0] >= j:
			dp[i][j] += dp[i-1][j-1]
			dp[i][j] %= MOD
		if j != i+1 and rb[i][1] >= i+1 - j:
			dp[i][j] += dp[i-1][j]
			dp[i][j] %= MOD

print(dp[2*n-1][R])

### FIXED CODE ###

MOD = 998244353
s = input()
n = len(s)
R = s.count("0") * 2 + s.count("1")
B = 2*n - R
rb = [[R, B] for _ in range(2*n)]
if s[0] == "0":
	rb[0] = [2, 0]
elif s[0] == "1":
	rb[0] = [1, 1]
else:
	rb[0] = [0, 2]
for i in range(1, n):
	if s[i] == "0":
		rb[i] = [rb[i-1][0] + 2, rb[i-1][1] + 0]
	elif s[i] == "1":
		rb[i] = [rb[i-1][0] + 1, rb[i-1][1] + 1]
	else:
		rb[i] = [rb[i-1][0] + 0, rb[i-1][1] + 2]

dp = [[0 for _ in range(R+1)] for _ in range(2*n)]
if rb[0][0] >= 1:
	dp[0][1] = 1
if rb[0][1] >= 1:
	dp[0][0] = 1
for i in range(1, 2*n):
	for j in range(R+1):
		if j > 0 and rb[i][0] >= j:
			dp[i][j] += dp[i-1][j-1]
			dp[i][j] %= MOD
		if j != i+1 and rb[i][1] >= i+1 - j:
			dp[i][j] += dp[i-1][j]
			dp[i][j] %= MOD

print(dp[2*n-1][R])
### BUGGY CODE ###

N = int(input())
p = list(map(int,input().split()))

cnt = 0
for n in p:
  i = p.index(n)
  if n == p[0]:
    cnt += 1
  elif min(p[:i]) >= n:
    cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
p = list(map(int,input().split()))

cnt = 0
for n in p:
  if n == p[0]:
    cnt += 1
    min = n
  elif min >= n:
    cnt += 1
    min = n
print(cnt)
### BUGGY CODE ###

import numpy as np
A,B,Q=map(int,input().split())
s=[0 for i in range(A)]
t=[0 for i in range(B)]
x=[0 for i in range(Q)]
s=np.array(s)
t=np.array(t)
x=np.array(x)
for i in range(A):
    s[i]=int(input())
for i in range(B):
    t[i]=int(input())
for i in range(Q):
    x[i]=int(input())
for X in x:
    l1=min(abs(X-t))
    if -l1 in X-t:
        l1=-l1
    l2=min(abs(X-s))
    if -l2 in X-s:
        l2=-l2
    print(min(min(abs(X-t))+min(abs(X-l1-s)),min(abs(X-s))+min(abs(X-l2-t))))


### FIXED CODE ###

import bisect
INF=10**18
A,B,Q=map(int,input().split())
s=[int(input()) for i in range(A)]
t=[int(input()) for i in range(B)]
s=[-INF]+s+[INF]
t=[-INF]+t+[INF]
for q in range(Q):
    X=int(input())
    t1=bisect.bisect_right(t,X)
    s1=bisect.bisect_right(s,X)
    res=INF
    for T in [t[t1],t[t1-1]]:
        for S in [s[s1],s[s1-1]]:
            ans1=abs(X-T)+abs(S-T)
            ans2=abs(X-S)+abs(S-T)
            res=min(res,ans1,ans2)
    print(res)
### BUGGY CODE ###

import sys
#sys.exit()
#sorted( ,reverse=True)
N = int(input())
#S,T = map(int, input().split())
#A = list(map(int, input().split()))
#print(N)
#print(S,T)
#print(A)
S = str(input())
#r = S.count("R")
#g = S.count("G")
#b = S.count("B")
#ans = (r*g*b)
r2 = [i for i, x in enumerate(S) if x == 'R']
g2 = [i for i, x in enumerate(S) if x == 'G']
b2 = [i for i, x in enumerate(S) if x == 'B']
ans = (len(r2)*len(g2)*len(b2))
for i in range (0,len(r2)):
    for j in range (0,len(g2)):
        for k in range (0,len(b2)):
            lis2 =[r2[i], g2[j], b2[k]]
            lis= sorted(lis2)
            if lis[1]-lis[0] == lis[2]-lis[1]:
                ans -=1
                #print(r2[i],g2[j],b2[k])
print(ans)


### FIXED CODE ###

import sys
#sys.exit()
#sorted( ,reverse=True)
N = int(input())
S = str(input())
r = S.count("R")
g = S.count("G")
b = S.count("B")
ans = (r*g*b)
for i in range (N-2):
    for j in range (i+1,N-1):
        k = 2*j-i
        if k < N and S[i]!=S[j] and S[j] != S[k] and S[k] != S[i]:
                ans -=1
                #print(r2[i],g2[j],b2[k])
print(ans)
### BUGGY CODE ###

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

mins=[0]

for i in range(1,n):
	if i == 1:
		mins.append(abs(hlist[1]-hlist[0]))
		continue
	
	tmplist=[]
	tmp=hlist[i]
	for j in range(min(k,i)):
		tmplist.append(mins[i-j-1]+abs(tmp-hlist[i-j-1]))
	mins.append(min(tmplist))

print(mins[n-1])


### FIXED CODE ###

n,k=map(int,input().split())
hlist=list(map(int,input().split()))
 
mins=[0]
 
for i in range(1,n):
	if i == 1:
		mins.append(abs(hlist[1]-hlist[0]))
		continue
	
	tmplist=[]
	tmp=hlist[i]
	for j in range(min(k,i)):
		tmplist.append(mins[i-j-1]+abs(tmp-hlist[i-j-1]))
	mins.append(min(tmplist))
 
print(mins[n-1])
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()

for i in range(q):
    l,r=map(int,input().split())
    ss=s[l-1:r]
    m=0
    for j in range(r-l):
            if ss[j]=="A" and ss[j+1]=="C":
                m+=1
    print(m)


### FIXED CODE ###

n,q=map(int,input().split())
s=input()
t=[0]*(n+1)
for i in range(n):
    t[i+1]=t[i]+(1 if s[i:i+2]=="AC" else 0)

for i in range(q):
    l,r=map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

import numpy as np

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

a = [i for i in a if i <k]
n = len(a)

DP1 = np.full((n+1, k+1), False)
DP1[0][0] = True
DP2 = np.full((n+1, k+1), False)
DP2[0][0] = True

for i in range(n):
    DP1[i+1] = DP1[i]
    DP1[i+1][a[i]:] = np.logical_or(DP1[i+1][a[i]:], DP1[i][:k-a[i]+1])
    DP2[i+1] = DP2[i]
    DP2[i+1][a[n-1-i]:] = np.logical_or(DP2[i+1][a[n-1-i]:], DP2[i][:k-a[n-1-i]+1])

hoge = []
for i in range(n+1):
    q = [0]
    for j in range(k+1):
        q.append(q[-1]+int(DP2[i][j]))
    hoge.append(q)

ans = 0
for i in range(n):
    use = False
    for j in range(k+1):
        if not DP1[i][j]:
            continue
        left = max(0, k-a[i]-j)
        right = k-j
        if hoge[n-i-1][right] - hoge[n-i-1][left]:
            use = True
            break
    if not use:
        ans += 1

print(ans)

### FIXED CODE ###

import numpy as np

def main():
    def check(m):
        DP = np.full(k+1, False)
        DP[0] = True
        for i in range(n):
            if i == m:
                continue
            DP[a[i]:] = np.logical_or(DP[a[i]:], DP[:k+1-a[i]])
        return any(DP[i] for i in range(k-a[m], k))

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

    a = [i for i in a if i <k]
    a.sort()
    n = len(a)

    left = -1
    right = n

    while right-left > 1:
        mid = (right+left)//2
        if check(mid):
            right = mid
        else:
            left = mid

    print(right)

main()
### BUGGY CODE ###

import heapq as hp

n,q=[int(x) for x in input().rstrip().split()]

l=[[] for i in range(n)]
ans=[0]*n

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

for i in range(q):
  p,x=map(int,input().split())
  ans[p-1]+=x

def dfs():
  val=0
  que=[[0,val]]
  done=[0]*n  

  while(que):
    now,val=que.pop(0)
    if done[now]==1:
      continue
    val+=ans[now]
    ans[now]=val
    done[now]=1

    for i in l[now]:
      if done[i]==0:
        que.append([i,val])

dfs()
print(*ans)


### FIXED CODE ###

n,q=[int(x) for x in input().rstrip().split()]
l=[[] for i in range(n)]
ans=[0]*n

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

for i in range(q):
  p,x=map(int,input().split())
  ans[p-1]+=x

def dfs():
  que=[0]
  done=[0]*n  
  done[0]=1
  while(que):
    now=que.pop()

    for i in l[now]:
      if done[i]==0:
        done[i]=1
        que.append(i)
        ans[i]+=ans[now]

dfs()
print(*ans)
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ"
memo=[[] for _ in range(26)]
for i,s in enumerate(S):
    memo[ABC.index(s)].append(i)
state=[1]*N
exist=N

for _ in range(Q):
    t,d=input().split()
    
    if d=='L':
        for m in memo[ABC.index(t)]:
            if m==0:
                exist-=state[m]
            else:
                state[m-1]+=state[m]
            state[m]=0
    
    else:
        for m in memo[ABC.index(t)][::-1]:
            if m==N-1:
                exist-=state[m]
            else:
                state[m+1]+=state[m]
            state[m]=0
print(exist)

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
TD=[tuple(input().split()) for _ in range(Q)]

def go(x):
    pos=x
    for t,d in TD:
        if pos==N: return N
        if pos==-1: return -1
        if t==S[pos]:
            if d=='L': pos-=1
            else: pos+=1
    return pos

U=N
L=-1
while U-L>1:
    x=(U+L)//2
    if go(x)==-1: L=x
    else: U=x
left=L

U=N
L=-1
while U-L>1:
    x=(U+L)//2
    if go(x)==N: U=x
    else: L=x
right=U

print(right-left-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


n, q = map(int, input().split())
events = []
for _ in range(n):
    start, end, pos = map(int, input().split())
    events.append([start - pos, 1, pos])
    events.append([end - pos, 0, pos])

events.sort()

departures = [int(input()) for _ in range(q)]

idx = 0
mini = 10**10
mini_check = False
candidates = set()
time, is_under_construction, pos = events[idx]
for departure in departures:
    while time <= departure:
        if is_under_construction:
            candidates.add(pos)
            if not mini_check or pos < mini:
                mini = pos
        else:
            candidates.remove(pos)
            if pos == mini:
                mini_check = False
        idx += 1
        if idx == 2 * n:
            time = float('INF')
            break
        time, is_under_construction, pos = events[idx]

    if not candidates:
        print(-1)
    else:
        if not mini_check:
            mini = min(candidates)
        print(mini)

### FIXED CODE ###

import sys
input = sys.stdin.readline


n, q = map(int, input().split())
events = []
for _ in range(n):
    start, end, pos = map(int, input().split())
    events.append([start - pos, 1, pos])
    events.append([end - pos, 0, pos])

events.sort()

departures = [int(input()) for _ in range(q)]

idx = 0
mini = 10**10
mini_check = False
candidates = set()
time, is_under_construction, pos = events[idx]
for departure in departures:
    while time <= departure:
        if is_under_construction:
            candidates.add(pos)
            if pos < mini:
                mini = pos
                mini_check = True
        else:
            candidates.remove(pos)
            if pos == mini:
                mini_check = False
        idx += 1
        if idx == 2 * n:
            time = float('INF')
            break
        time, is_under_construction, pos = events[idx]

    if not candidates:
        print(-1)
    else:
        if not mini_check:
            mini = min(candidates)
            mini_check = True
        print(mini)
### BUGGY CODE ###

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

for i in range(N):
    if K + A.count(i+1) - Q > 0:
        print("Yes")
    else: print("No")

### FIXED CODE ###

N, K, Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
ans = [K-Q]*N
for i in range(Q):
    ans[A[i]-1]+=1
for i in range(N):
    if ans[i]>0:
        print("Yes")
    else: print("No")