Harryxun/stf_run huggingface dataset:
N = int(input())
G = [[] * N for i in range(N)]

for i in range(N-1):
    u, v, w = map(int, input().split())
    if w % 2 == 0:
        G[u-1].append((v-1, 1))
        G[v-1].append((u-1, 1))
    else:
        G[u-1].append((v-1, -1))
        G[v-1].append((u-1, -1))

color = [None for i in range(N)]


def set_color(v, c):
    color[v] = c
    for next_v, d in G[v]:
        if color[next_v] is None:
            set_color(next_v, d*c)


set_color(0, 1)

for c in color:
    if c == 1:
        print(1)
    else:
        print(0)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)


N = int(input())
G = [[] for i in range(N)]

for i in range(N-1):
    u, v, w = map(int, input().split())
    if w % 2 == 0:
        G[u-1].append((v-1, 1))
        G[v-1].append((u-1, 1))
    else:
        G[u-1].append((v-1, -1))
        G[v-1].append((u-1, -1))

color = [None for i in range(N)]


def set_color(v, c):
    color[v] = c
    for next_v, d in G[v]:
        if color[next_v] is None:
            set_color(next_v, d*c)


set_color(0, 1)

for c in color:
    if c == 1:
        print(1)
    else:
        print(0)
n = int(input())
l = []
for i in range(1, 10):
  for j in range(1, 10):
    l.appned(i*j)

if n in l:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n = int(input())
l = []
for i in range(1, 10):
  for j in range(1, 10):
    l.append(i*j)

if n in l:
  print("Yes")
else:
  print("No")
N,K = map(int,input().split())
P = list(map(int,input().split()))
dp = []*N+1
dp[0] = 0
for i in range(N):
    dp[i+1] = max(dp[i]//P[i],dp[i+1]//P[i+1])
hope = max(dp[i:i+3])
hopes = sum(hope)

### FIXED CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
for i in range(N):
  P[i] = (P[i]+1)/2
now = sum(P[:K])
ans = now
for j in range(N-K):
  now = now - P[j] + P[j+K]
  ans = max(ans,now)
print(ans)
import sys, math, collections, heapq, itertools
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    event = []
    for i in range(N):
        s, t, x = map(int, line_input())
        event.append((max(s-x, 0), 1, x))
        event.append((max(t-x, 0), -1, x))
    for i in range(Q):
        d = int(single_input())
        event.append((d, 2, d))
    event.sort()
    stop = []
    ans = ""
    for time, parameter, co in event:
        if parameter == 1: stop.append(co)
        elif parameter == -1: stop.remove(co)
        else:
            if stop:
                stop.sort()
                ans += str(stop[0]) + "\n"
            else: ans += "-1\n"
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys, collections, heapq
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    event = []
    for i in range(N):
        s, t, x = map(int, line_input())
        event.append((s-x, 1, x))
        event.append((t-x,-1, x))
    for i in range(Q):
        d = int(single_input())
        event.append((d, 2, d))
    event.sort()
    candidate = []
    heapq.heapify(candidate)
    stop = collections.defaultdict(int)
    ans = ""
    for time, parameter, co in event:
        if parameter == 1:
            heapq.heappush(candidate, co)
            stop[co] += 1
        elif parameter == -1:
            stop[co] -= 1
        else:
            while candidate:
                x = heapq.heappop(candidate)
                if stop[x] > 0:
                    heapq.heappush(candidate, x)
                    ans += str(x) + "\n"
                    break
            else: ans += "-1\n"
    print(ans)

    return 0

if __name__ == "__main__":
    solve()
import math
import copy
from copy import deepcopy
import sys
import fractions
import numpy as np
from functools import reduce
# import statistics
import heapq
sys.setrecursionlimit(100001)

# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

n = int(input())

data = getSomeInputListInt(n-1)

ans = [-1]*n

g = [[] for i in range(n)]
for i in range(n-1):
    u,v,w = map(int,input().split())
    u-=1;v-=1
    g[u].append([v,w])
    g[v].append([u,w])
ans = [-1]*n
def dfs(x,y):
    for i,j in g[x]:
        if ans[i] == -1:
            ans[i] = (y+j)%2
            dfs(i,y+j)
dfs(0,0)
for i in ans:
    print(i)

### FIXED CODE ###

import math
import copy
from copy import deepcopy
import sys
import fractions
import numpy as np
from functools import reduce
# import statistics
import heapq
sys.setrecursionlimit(100001)

# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

n = int(input())


ans = [-1]*n

g = [[] for i in range(n)]
for i in range(n-1):
    u,v,w = map(int,input().split())
    u-=1;v-=1
    g[u].append([v,w])
    g[v].append([u,w])
ans = [-1]*n
def dfs(x,y):
    for i,j in g[x]:
        if ans[i] == -1:
            ans[i] = (y+j)%2
            dfs(i,y+j)
dfs(0,0)
for i in ans:
    print(i)
import pandas as pd
n_entradas = int(input())
contador = 0
vetor=[]
while (contador<n_entradas):
    situacao = str(input())
    vetor.append(situacao)
    contador=contador+1    
print('AC x',vetor.count('AC'))
print('WA x',vetor.count('WA'))
print('TLE x',vetor.count('TLE'))
print('RE x',vetor.count('RE'))

### FIXED CODE ###

n_entradas = int(input())
contador = 0
vetor=[]
while (contador<n_entradas):
    situacao = str(input())
    vetor.append(situacao)
    contador=contador+1    
print('AC x',vetor.count('AC'))
print('WA x',vetor.count('WA'))
print('TLE x',vetor.count('TLE'))
print('RE x',vetor.count('RE'))
n = int(input())

for i in rang(0,2):
    if( n % 10 == 7):
        print("YES")
        break
    n /= 10
else:
    print("NO")

### FIXED CODE ###

n = int(input())

for i in range(0,3):
    if( n % 10 == 7):
        print("Yes")
        break
    n = int(n / 10)
else:
    print("No")
n = int(input())

for i in range(n//7+1):
	if n%4==0:
		print("Yes")
		break
	n -=7
else:
	print("No")


### FIXED CODE ###

N, K = map(int,input().split())

if N%K==0:
   print(0)
else:
   print(1)
x = int(input())
 
ans=0
for i in range(1,x):
    for j in range(2,x):
        if b**p<=x:
            ans=b**p
        else:
            break
print(ans)

### FIXED CODE ###

x=int(input())
i,j=2,1
ans=[]
if x==1:
    print(1)
    quit()
while True:
    j+=1
    if i**j>x:
        i+=1
        j=2
        if i**j>x:
            break
    ans.append(i**j)
print(max(ans))
a=map(int,input().split())
print(a[0]*a[1]//2)

### FIXED CODE ###

a=list(map(int,input().split()))
print(a[0]*a[1]//2)
from scipy.misc import comb

def solve(n,m):
    maxdiv = int(m**0.5)
    l = []
    tmp = 2
    num = 0
    while tmp <= maxdiv:
        if m % tmp == 0:
            m /= tmp
            num += 1
        else:
            tmp += 1
            if num != 0:
                l.append(num)
                num = 0
    if m != 1:
        l.append(1)
    res = 1
    for div in l:
        tmp = comb(n+div-1,div,exact=True)%(10**9+7)
        res = res * tmp % (10**9+7)
    return int(res)
        

if __name__ == '__main__':
    n,m = map(int,input().split())
    print(solve(n,m))

### FIXED CODE ###

# from scipy.misc import comb

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def solve(n,m):
    maxdiv = int(m**0.5)
    l = []
    tmp = 2
    num = 0
    while tmp <= maxdiv:
        if m % tmp == 0:
            m /= tmp
            num += 1
        else:
            tmp += 1
            if num != 0:
                l.append(num)
                num = 0
    if m != 1:
        l.append(1)
    res = 1
    for div in l:
        tmp = cmb(n+div-1,div)%(10**9+7)
        res = res * tmp % (10**9+7)
    return int(res)
        

if __name__ == '__main__':
    n,m = map(int,input().split())
    print(solve(n,m))
S = input()
T = input()

count = 0
for i in range(len(S)):
  if S[i] == T[i]:
  	continue
  else:
    S[i] = T[i]
    count += 1
return count
    

### FIXED CODE ###

S = list(input())
T = list(input())

count = 0
for i in range(len(S)):
  if S[i] == T[i]:
  	continue
  else:
    S[i] = T[i]
    count += 1
print(count)
N,K=map(int,input().split())
p=list(map(int,input().split()))
p.sort()
res=0
for x in p[:K]:
	res+=x

print(res)

### FIXED CODE ###

S=input()
T=input()

res=0
for i in range(len(S)):
	if not S[i]==T[i]:
		res+=1
print(res)
import fractions
from functools import reduce

n = int(input())
a = list(map(int, input().split()))
t = []
a.sort()

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

for i in range(int(n/2) +1):
    aa = a[i]
    a[i] = a[i+1]
    t.append(gcd(*a))
    a[i] = aa
    
print(max(t))

### FIXED CODE ###

from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
result = []

left = [0] * (n+1)
right = [0] * (n+1)
for i in range(n):
    left[i+1] = gcd(left[i], a[i])
for j in range(n-1, -1, -1):
    right[j] = gcd(right[j+1], a[j])
for i in range(n):
    result.append(gcd(left[i], right[i+1]))

print(max(result))
n = int(input())

a = [set() for i in range(n)]

for i in range(n-1):
  b, c = map(int, input().split())
  b -= 1
  c -= 1
  if i == 0:
    s = b
  a[b].add(c)
  a[c].add(b)

col = [0 for i in range(n)]
visited = [False for i in range(n)]
visited[0] = True

def dfs(s,k):
  visited[s] = True
  col[s] = k
  j = 1
  for i in a[s]:
    if visited[i] == False:
      if col[s] == j:
        j += 1
      dfs(i,j)
      j += 1

dfs(0,0)

print (max(col))
for i in col[1:]:
  print (i)

### FIXED CODE ###

from collections import deque
n = int(input())
a = [[] for i in range(n)]
e = []
for i in range(n-1):
  b, c = map(int, input().split())
  b -= 1
  c -= 1
  a[b].append(c)
  e.append(c)
col = [0 for i in range(n)]
v = deque([0])

while v:
  d = v.popleft()
  k = 1
  for i in a[d]:
    if col[d] == k:
      k += 1
    col[i] = k
    v.append(i)
    k += 1
print (max(col))
for i in e:
  print(col[i])
n,x = map(int,input().split())
s = list(map(int,input().split()))
import math
for i in range(n):
    s[i] = s[i] - x

t = s[0]
for i in range(n-1):
    t = math.gcd(t,s[i+1])

print(t)

### FIXED CODE ###

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

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a

for i in range(n):
    s[i] = abs(s[i] - x)

if s[0] != 0:
    t = s[0]
    for i in range(n-1):
        if s[i+1] == 0:
            continue
        else:
            t = gcd(t,s[i+1])
else:
    t = s[-1]
    for i in range(n-1):
        if s[-i-2] == 0:
            continue
        else:
            t = gcd(t,s[-i-1])

print(t)
line=input().split()
x=int(line[0])
y=int(line[1])
if x<y:
    temp=x
    x=y
    y=temp
def greatst(x,y):
    if x==y:
        return x
    else:
        return greatst(y,x%y)
print(greatst(x,y))


### FIXED CODE ###

import math
line=input().split()
x=int(line[0])
y=int(line[1])
print(math.gcd(x,y))
N = int(input())
XY = []
for n in range(N):
    XY.append([int(i) for i in input().split()])
cnt = {}
for n in range(N):
    for nn in range(n+1,N): 
        dist = [XY[n][0]-XY[nn][0],XY[n][1]-XY[nn][1]]
        if str(dist) in cnt:
            cnt[str(dist)] += 1
        else:
            cnt[str(dist)] = 1
print(N - max(cnt.values()))

### FIXED CODE ###

N = int(input())
XY = []
for n in range(N):
    XY.append([int(i) for i in input().split()])
XY = sorted(XY)
cnt = {}
for n in range(N):
    for nn in range(n+1,N): 
        dist = [XY[n][0]-XY[nn][0],XY[n][1]-XY[nn][1]]
        if str(dist) in cnt:
            cnt[str(dist)] += 1
        else:
            cnt[str(dist)] = 1
if N == 1:
    print(1)
else:
    print(N - max(cnt.values()))
H, N= map(int, input().split())
An = list(map(int, input().split()))
if sum(An)>= H:
	print('Yes')
else:
	print('No

### FIXED CODE ###

H, N = [int(x) for x in input().split()]
attacks = [int(x) for x in input().split()]
print("Yes" if H - sum(attacks) <= 0 else "No")
NUM = 3
max = input(data)
print(max**NUM)

### FIXED CODE ###

max = int(input())
print(max ** 3)
a = list(input().split())

if max(a[0],a[2]) < min(a[1],a[3]):
    print(int(min(a[1],a[3])-int(max(a[0],a[2])))
              
              
              
else if max(a[0],a[2]) >= min(a[1],a[3]):
    print(0)       


### FIXED CODE ###

a = list(input().split())

b = int(a[0])
c = int(a[1])
d = int(a[2])
e = int(a[3])

if max(b,d) < min(c,e):
    print(min(c,e)-max(b,d))       

elif max(b,d)>=min(c,e):
        print(0)
from math import factorial

n,k = map(int,input().split())
mod = 10**9+7

def comb(n,r):
    return factorial(n) / (factorial(r) * factorial(n-r))

for i in range(1,k+1):
    x = comb(k-1,k-i) % mod
    if n-k+1 >= i:
        y = comb(n-k+1,i) % mod
    elif: i > n-k+1
        y = 0
    print(int(x*y)%mod)

### FIXED CODE ###

from math import factorial

n,k = map(int,input().split())
mod = 10**9+7

def cmb(n,r):
    return factorial(n) // (factorial(r) * factorial(n-r))

for i in range(1,k+1):
    if n-k+1 < i or k-1 < i-1:
        print(0)
    else:
        x = cmb(k-1,i-1) % mod
        y = cmb(n-k+1,i) % mod
        ans = (x*y) % mod
        print(int(ans))
while True:
	try:
		A=[int(j) for j in input().split()]
		a=A[3]/A[0]
		for i in range(3):
			A[i]*=a
		for i in range(3):
			A[i]=A[i]-A[i+3]
		y=A[2]/A[1]
		x=(A[5]-A[4]*y)/A[3]
		print(x,y)
	except EOFError:
		break

### FIXED CODE ###

while True:
    try:
        l=list(map(int, input().split()))
        x=(l[1]*l[5]-l[2]*l[4])/(l[1]*l[3]-l[0]*l[4])
        y=(l[2]-l[0]*x)/l[1]
        if x == 0: x = 0
        print( "{0:.3f} {1:.3f}".format(x,y))
    except:
        break
def countInn(n, L):
  numInn = 1
  mainHurdle = L[0]
  hurdle = L[1]
  for i in range(1, n):
    currentH = L[i]
    if currentH < mainHurdle or currentH < hurdle:
      continue
    numInn += 1
    hurdle = currentH
  print(numInn)
  
n = int(input())
a = list(map(int, input().split()))
countInn(n, a)

### FIXED CODE ###

def countInn(n, L):
  numInn = 1
  mainHurdle = L[0]
  hurdle = mainHurdle
  for i in range(1, n):
    currentH = L[i]
    if currentH < mainHurdle or currentH < hurdle:
      continue
    numInn += 1
    hurdle = currentH
  print(numInn)
  
n = int(input())
a = list(map(int, input().split()))
countInn(n, a)
a, b = list(map(int, input().split()))
if a * b % 2 == 0:


### FIXED CODE ###

a, b = list(map(int, input().split()))
if a * b % 2 == 0:
    print('Even')
else:
    print('Odd')
a,op,b = input()
if op == "+":
  ans = a+b
else:
  ans = a-b
print(ans)

### FIXED CODE ###

a,op,b = input().split()
ans = 0
if op == "+":
  ans = int(a)+int(b)
else:
  ans = int(a)-int(b)
print(ans)
import math
 
def gooddistance(l1, l2):
    calc = []
    
    for i in range(len(l1)):
        calc.append((l1[i] - l2[i])**2)
 
    if math.sqrt(sum(calc)).is_integer():
        return 1
    else:
        return 0
 
 n, d = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(n)]
count = 0
 
for i in range(n):
    for j in range(i+1,n):
       count += gooddistance(lst[i],lst[j])
 
 print(count)

### FIXED CODE ###

import numpy as np
N,D=map(int,input().split())
X=[np.array(input().split(),dtype=np.int64) for _ in range(N)]
ans=0
for i in range(N):
    for j in range(i+1,N):
        d=((X[i]-X[j])*(X[i]-X[j])).sum()
        dd=int(round(d**.5))
        if d==dd*dd:
            ans +=1
print(ans)
from itertools import accumulate
import bisect
 
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
 
acum1=[0]
for i in range(n): #累積和ai,bjを求める
    acum1.append(acum1[-1]+arr1[i])
for i in range(m):
    acum2.append(acum2[-1]+arr2[i])
 
ans = 0
for an in range(n + 1):
    rem = k - acum1[an]
    if rem < 0:
        # aをこれ以上読めません
        break
 
    bn = bisect.bisect_right(acum2, rem)
    ans = max(ans, an + bn)
 
print(ans)

### FIXED CODE ###

from itertools import accumulate
import bisect

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

a_acc = [0] + list(accumulate(a))  # aを0冊読む=1冊も読まない場合があるので、[0]を先頭に追加します
b_acc = list(accumulate(b))  # bisect_rightでは、x以下の要素がいくつあるか？を求めるので、こちらに0は入れません

ans = 0
for an in range(n + 1):
    rem = k - a_acc[an]
    if rem < 0:
        # aをこれ以上読めません
        break

    bn = bisect.bisect_right(b_acc, rem)
    ans = max(ans, an + bn)

print(ans)
n = int(input())
x = list(map(int,input().split()))
ans = []
for p in range(min(x), max(x)):
    meter = 0
    for xi in x:
        meter += pow((xi-p),2)
    ans.append(meter)
print(min(ans))

### FIXED CODE ###

n = int(input())
x = list(map(int,input().split()))
ans = []
if len(set(x)) == 1:
    print(0)
else: 
    for p in range(min(x), max(x)):
        meter = 0
        for xi in x:
            meter += pow((xi-p),2)
        ans.append(meter)
    print(min(ans))
n,l=(int(x) for x in input().split())

mojil=[]

for i in range(l):
    mojil.append(input())

mojil.sort()

for i in range(l):
    print(mojil[i],end="")

### FIXED CODE ###

n,l=(int(x) for x in input().split())

mojil=[]

for i in range(n):
    mojil.append(input())

mojil.sort()

for i in range(n):
    print(mojil[i],end="")
# 2019/05/25
# AtCoder Beginner Contest 061 - B

# Input
n, m = map(int, input().split())
rcnt = [0] * (n + 1)
for i in range(m):
    a, b = map(int, input().split())
    rcnt[a] += 1
    rcnt[b] += 1

# Output
for i in range(1, n+1):
    print[i]


### FIXED CODE ###

# 2019/05/25
# AtCoder Beginner Contest 061 - B

# Input
n, m = map(int, input().split())
rcnt = [0] * (n + 1)
for i in range(m):
    a, b = map(int, input().split())
    rcnt[a] += 1
    rcnt[b] += 1

# Output
for i in range(1, n+1):
    print(rcnt[i])
a,b=input().split();printa/b+a%b)

### FIXED CODE ###

a=eval(input().replace(' ', '+'));print(a//2+a%2)
import numpy as np
N = int(input())
A = np.array(input().split(),dtype=np.int32)
total_medians = N*(N+1)//2
# n件のデータ
# (上側中央値 >= x) iff (a > x となる a が(n-1)//2以下)

def BIT_update(BIT,x,value):
  # 番号xにvalueを加える
  L = len(BIT)
  while x < L:
    BIT[x] += value
    bottom_bit = x & (-x)
    x += bottom_bit
  return

def BIT_sum(BIT,x):
  # 番号1～xの和を求める
  result = 0
  while x:
    result += BIT[x]
    bottom_bit = x & (-x)
    x -= bottom_bit
  return result

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  B = np.concatenate([[0],(A > x).cumsum()])
  # count L,R such that -1<=L<R<=N-1 and B(R)-B(L) >= (R-L)/2
  # count L,R such that B(R) - R/2 >= B(L) - L/2
  C = 2*B-np.arange(N+1)
  C -= np.min(C) - 1
  M = C.max()
  BIT = [0]*(M+1)
  
  cnt = 0
  prev = C[0]
  for c in C[1:]:
    BIT_update(BIT,prev,1)
    cnt += BIT_sum(BIT,c) # 右端がRとなる(L,R)対
    prev = c
  return cnt <= (total_medians-1)//2

AA = sorted(set(A))
left = -1 # 答はAA[left]より大きい
right = len(AA)-1 # 答はAA[right]以下である
while right - left > 1:
  mid = (left+right)//2
  if test(AA[mid]):
    right = mid
  else:
    left = mid
    
answer = AA[right]
print(answer)


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
total_medians = N*(N+1)//2
# n件のデータ
# (上側中央値 >= x) iff (a > x となる a が(n-1)//2以下)

def BIT_update(BIT,x,value):
  # 番号xにvalueを加える
  L = len(BIT)
  while x < L:
    BIT[x] += value
    bottom_bit = x & (-x)
    x += bottom_bit
  return

def BIT_sum(BIT,x):
  # 番号1～xの和を求める
  result = 0
  while x:
    result += BIT[x]
    bottom_bit = x & (-x)
    x -= bottom_bit
  return result

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  B = [0]
  for a in A:
    B.append(B[-1] + (1 if a>x else -1))
  m = min(B)-1
  B = [x-m for x in B]

  BIT = [0]*(N+1)
  
  cnt = 0
  for R in range(1,N+1):
    BIT_update(BIT,B[R-1],1)
    cnt += BIT_sum(BIT,B[R]) # 右端がRとなる(L,R)対
  return cnt <= (total_medians-1)//2

AA = sorted(A)
left = -1 # 答はAA[left]より大きい
right = len(AA)-1 # 答はAA[right]以下である
while right - left > 1:
  mid = (left+right)//2
  if test(AA[mid]):
    right = mid
  else:
    left = mid
answer = AA[right]

print(answer)
class Node:
    def __init__(self, i):
        self.index = i
        self.val = -1
        self.nodes = []
        self.link = 0

    def __lt__(self, other):
        # self < other
        return self.link < other.link

def width_search(node):
    if node.val == -1:
        node.val = c.pop(0)
        for child in sorted(node.nodes):
            width_search(child)

N = int(input())
if N == 1:
    c = list(map(int, input().split()))
    print(0)
    print(c[0])
else:
    nodes = [Node(i) for i in range(N)]

    for i in range(N-1):
        a, b = map(int, input().split())
        node_a = nodes[a-1]
        node_b = nodes[b-1]
        node_b.nodes.append(node_a)
        node_b.link += 1
        node_a.nodes.append(node_b)
        node_a.link += 1

    c = list(map(int, input().split()))
    c = sorted(c, reverse=True)

    max_c = 0
    sum_c = 0
    for tmp in c:
        sum_c += tmp
        max_c = max(max_c, tmp)

    width_search(max(nodes))

    print(sum_c - max_c)
    for i in range(N-1):
        print(nodes[i].val, end=" ")
    print(nodes[-1].val)


### FIXED CODE ###

from collections import deque

class Node:
    def __init__(self):
        self.val = -1
        self.link = []

def main():
    N = int(input())
    nodes = [Node() for i in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1; b -= 1;
        nodes[a].link.append(nodes[b])
        nodes[b].link.append(nodes[a])
    c = list(map(int, input().split()))
    c = sorted(c, reverse=True)
    count = 0
    q = deque()
    q.append(nodes[0])
    while len(q) > 0:
        node = q.popleft()
        node.val = c[count]
        count += 1
        for next in node.link:
            if next.val == -1:
                q.append(next)
    print(sum(c) - c[0])
    for i in range(N):
        print(nodes[i].val, end="")
        if i != N-1:
            print(" ",end="")
        else:
            print()

if __name__ == "__main__":
    main()
n=int(input())
a=eval(input().replace(" ","*"))
if a>10**18:
  print(-1)
else:
  print(a)

### FIXED CODE ###

import functools
import operator

n=int(input())
a=list(map(int,input().split()))
b=0
r=1
if min(a)==0:
  print(0)
  exit()
for i in a:
  r*=i
  if r>10**18:
    print(-1)
    exit()
print(r)
a, b, c, d = map(int, input().split())
aok = 0
while c > 0:
  c = c - b
  aok += 1
  
if (aok - 1) * d - a => 0:
  print("No")
else:
  print("Yes")


### FIXED CODE ###

a, b, c, d = map(int, input().split())
aok = 0
while c > 0:
  c = c - b
  aok += 1
  
if ((aok - 1) * d - a) >= 0:
  print("No")
else:
  print("Yes")