Harryxun/stf_run huggingface dataset:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,q = readInts()
G = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(lambda x: int(x) - 1,input().split())
    G[a].append(b)
    G[b].append(a)
val = [0] * n
for i in range(q):
    p,x = readInts()
    p -= 1
    val[p] += x

def dfs(v,p):
    if p != -1:
        val[v] += val[p]
    for e in G[v]:
        if e == p:
            continue
        dfs(e,v)

dfs(0,-1)
print(*val)


### FIXED CODE ###

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,q = readInts()
G = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(lambda x: int(x) - 1,input().split())
    G[a].append(b)
    G[b].append(a)
val = [0] * n
for i in range(q):
    p,x = readInts()
    p -= 1
    val[p] += x
stack = [(0,-1)]
while stack:
    v,p = stack.pop()
    for nv in G[v]:
        if nv == p:
            continue
        val[nv] += val[v]
        stack.append((nv,v))
# def dfs(v,p):
#     if p != -1:
#         val[v] += val[p]
#     for nv in G[v]:
#         if nv == p:
#             continue
#         dfs(nv,v)
#
# dfs(0,-1)
print(*val)
#!/usr/bin/env python
# coding: utf-8

# In[11]:


S=input()
t=list()
ct=0
for i in range(len(S)):
    if S[i]=='A' or S[i]=='C' or S[i]=='T' or S[i]=='G':
        i+=1
        ct+=1
    else:
        t.append(ct)
        ct=0
        i+=1
print(max(t))


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[21]:


S=input()
t=list()
ct=0
for i in range(len(S)):
    if S[i]=='A' or S[i]=='C' or S[i]=='T' or S[i]=='G':
        i+=1
        ct+=1
    else:
        t.append(ct)
        ct=0
        i+=1
t.append(ct)
print(max(t))


# In[ ]:
s = input()

if s = "ABC":
    print("ARC")
else:
    print("ABC")


### FIXED CODE ###

s = input()

if s == "ABC":
    print("ARC")
else:
    print("ABC")
from collections import defaultdict

n, m, k = map(int, input().split())
def connection(n):
    connect = defaultdict(set)
    for i in range(n):
        a, b = map(int, input().split())
        connect[a].add(b)
        connect[b].add(a)
    return connect
    
friends = connection(m)
blocks = connection(k)
groups = []
def dfs(start, check_set):
    seen = [False for i in range(n+1)]
    todo = []
    seen[start] = True
    todo.append(start)
    while todo:
        v = todo.pop()
        for w in check_set[v]:
            if not seen[w]:
                seen[w] = True
                todo.append(w)
    return seen

checked_friends = set()
groups = {}
group_num = 0
belong_group = {}
for person in range(n):
    if person in checked_friends:
        continue
    group_num += 1
    seen_friends = dfs(person, friends)
    seen_set = set(i for i, flag in enumerate(seen_friends) if flag)
    seen_len = len(seen_set)
    for i in seen_set:
        belong_group[i] = group_num
    not_checked_friends |= seen_set
    groups[group_num] = seen_set

print(' '.join(str(len(groups[belong_group[i]])-len(groups[belong_group[i]]&(friends[i]|blocks[i]))-1) for i in range(1, n+1)))
    
    

### FIXED CODE ###

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return ''.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(n)

from collections import defaultdict
direct_f = defaultdict(int)
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    direct_f[a] += 1
    direct_f[b] += 1
    uf.union(a, b)
ans = [uf.size(i) - direct_f[i] - 1 for i in range(n)]
for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.same(c,d):
        ans[c] -= 1
        ans[d] -= 1
print(*ans)
def dfs(d,tot,num):
    global A,N,S,how
    if tot==S:
        how[num]+=1
        return
    if d==N:
        return
    if tot+A[d]<=S:
        dfs(d+1,tot+A[d],num+1)
    dfs(d+1,tot,num)
        
    

N,S=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
how=[0]*(N+1)
dfs(0,0,0)
cur=1
res=0
for i in range(N,0,-1):
    res+=how[i]*cur
    cur*=2
print(res)

### FIXED CODE ###

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

def f(N,S,A):
    MOD=998244353
    dp=[0]*(S+1)
    dp[0]=pow(2,N,MOD)
    div=pow(2,MOD-2,MOD)
    m=0
    for a in A:
        m+=a
        for i in range(min(m,S),a-1,-1):
            dp[i]=(dp[i]+dp[i-a]*div)%MOD
    return dp[S]

print(f(N,S,A))
S=list(1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51)
k=int(input())
print(S[k-1])

### FIXED CODE ###

S=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k=int(input())
print(S[k-1])
n,p=map(int,input().split())
s=input()
b=1
d=0
l=[0]*n
ans=0
for c in s[::-1]:
  if p==2 or p==5:
    if int(c)%p==0:
      ans+=1
  else:
    d+=int(c)*b
    d%=p
    l[d]+=1
    b*=10
    b%=p
if p==2 or p==5:
  ans=ans*(ans+1)//2
else:
  for i in l:
    ans+=i*(i-1)//2
print(ans+l[0])

### FIXED CODE ###

n,p=map(int,input().split())
s=input()
b=1
d=0
l=[0]*p
l[0]=1
ans=0
for i,c in enumerate(s[::-1]):
  if p==2 or p==5:
    if int(c)%p==0:
      ans+=n-i
  else:
    d+=int(c)*b
    d%=p
    l[d]+=1
    b*=10
    b%=p
if p!=2 and p!=5:
  for i in l:
    ans+=i*(i-1)//2
print(ans)
import bisect
import numpy as np
N, K = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)
A = np.sort(A)

Aneg = A[A < 0]
Azero = A[A == 0]
Apos = A[A > 0]

neg = len(Aneg)
zero = len(Azero)
pos = len(Apos)

Nneg = neg * pos
Npos = 0
if neg > 0:
    Npos += neg * (neg - 1) // 2
if pos > 0:
    Npos += pos * (pos - 1) // 2
Nzero = N * (N - 1) // 2 - Npos - Nneg
print(Nneg, Npos, Nzero)


def C(N, ar):
    if len(ar) <= 1:
        return 0
    tmp = np.arange(len(ar))+1
    n = np.searchsorted(ar, N / ar, side="left")
    return (len(ar)-np.maximum(n, tmp)).sum()


def C1(N, ar1, ar2):
    tmp = np.arange(len(ar1))+1
    n = np.searchsorted(ar1, N / ar2, side="left")
    return (len(ar1)-np.maximum(n, tmp)).sum()


def bs_Neg():
    l, r = -10 ** 20, 0
    while r - l > 1:
        m = (r - l) // 2
        num = C1(m, Apos, Aneg)
        if num < K:
            r = m
        else:
            l = m
    return l


def bs_Pos(K):
    l, r = 0, 10 ** 20
    while r - l > 1:
        m = (r - l) // 2
        num = C(m, Apos) + C(m, Aneg)
        if num < K:
            r = m
        else:
            l = m
    return l


if K <= Nneg:
    ans = bs_Neg()
elif K <= Nneg + Nzero:
    ans = 0
else:
    K = K-Nneg-Nzero
    ans = bs_Pos(K)

print(ans)


### FIXED CODE ###

import numpy as np


def get_Negative(K, pos, neg):
    K = len(pos) * len(neg) - K + 1
    l = 0
    r = 10 ** 18 + 10
    while r - l > 1:
        m = (l + r) // 2
        target = m // pos
        x = np.searchsorted(neg, target, side="right").sum()
        if x >= K:
            r = m
        else:
            l = m
    return -r


def get_Positive(K, pos, neg):
    l = 0
    r = 10 ** 18 + 10
    tmp_pos = np.arange(len(pos))
    tmp_neg = np.arange(len(neg))
    while r - l > 1:
        m = (r + l) // 2
        cnt = 0
        if len(pos) > 1:
            t1 = m // pos
            x1 = np.searchsorted(pos, t1, side="right")
            x1 = np.maximum(0, x1 - tmp_pos - 1)
            cnt += x1.sum()
        if len(neg) > 0:
            t2 = m // neg
            x2 = np.searchsorted(neg, t2, side="right")
            x2 = np.maximum(0, x2 - tmp_neg - 1)
            cnt += x2.sum()
        if cnt >= K:
            r = m
        else:
            l = m
    return r


def main():
    N, K = map(int, input().split())
    A = np.array(input().split(), dtype=np.int64)

    positive = A[A > 0]
    negative = -A[A < 0]
    positive.sort()
    negative.sort()

    Npos = len(positive)
    Nneg = len(negative)
    Nzero = N - Npos - Nneg

    P_neg = Npos * Nneg
    P_pos = 0
    if Npos:
        P_pos += Npos * (Npos - 1) // 2
    if Nneg:
        P_pos += Nneg * (Nneg - 1) // 2
    P_zero = N * (N - 1) // 2 - P_pos - P_neg

    if K <= P_neg:
        ans = get_Negative(K, positive, negative)
        return ans
    K -= P_neg
    if K <= P_zero:
        return 0
    K -= P_zero
    ans = get_Positive(K, positive, negative)
    return ans


if __name__ == "__main__":
    print(main())
from sys import stdin
N = int(tdin.readline().rstrip())
Lucas_number = [0]*(N+1)
Lucas_number[0] = 2
Lucas_number[1] = 1
for i in range(2,N+1):
    Lucas_number[i] = Lucas_number[i-1] + Lucas_number[i-2]
print(Lucas_number[N])

### FIXED CODE ###

from sys import stdin
N = int(stdin.readline().rstrip())
Lucas_number = [0]*(N+1)
Lucas_number[0] = 2
Lucas_number[1] = 1
for i in range(2,N+1):
    Lucas_number[i] = Lucas_number[i-1] + Lucas_number[i-2]
print(Lucas_number[N])
a,b=map(int,input(),input().split())
print(max(a+b,a-b,a*b))

### FIXED CODE ###

a,b=map(int,input().split())
print(max(a+b,a-b,a*b))
a=input().split(' ')
X=int(a[0])
N=int(a[1])

if N!=0:
  Ls=input().split(' ')
  L=[]
  for i in range(N):
    L.append(int(Ls[i]))
else:
  s=X

for i in range (N):
  if X-i in L and X+i in L:
    pass
  elif X-i not in L:
    s=X-i
    break
  elif X-i in L and X+i not in L:
    s=X+i
    break
print(s)

### FIXED CODE ###

a=input().split(' ')
X=int(a[0])
N=int(a[1])

if N!=0:
  Ls=input().split(' ')
  L=[]
  for i in range(N):
    L.append(int(Ls[i]))
  for i in range (N+1):
    if X-i in L and X+i in L:
      pass
    elif X-i not in L:
      s=X-i
      break
    elif X-i in L and X+i not in L:
      s=X+i
      break
else:
  s=X


print(s)
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n,k=map(int,input().split())
a=list(map(int,input().split()))
m=0
if k==0:
    m=int(math.log2(1)+1)
else:
    m=int(math.log2(k)+1)
lst=[0]*m
for i in range(n):
    tmp=a[i]
    for j in range(m):
        if tmp&(1<<j):
            lst[j]+=1
# print(lst)

ans=0
ans2=0
for i in range(m):
    if lst[i]<=n/2 and ans+pow(2,i)<=k:
        ans+=pow(2,i)
# print(ans)
# print(ans2)
for i in range(n):
    ans2+=ans^a[i]

print(ans2)

### FIXED CODE ###

import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n,k=map(int,input().split())
a=list(map(int,input().split()))
m=0
if k==0:
    m=int(math.log2(1)+1)
else:
    m=int(math.log2(k)+1)
lst=[0]*m
for i in range(n):
    for j in range(m):
        if a[i]&(1<<j):
            lst[j]+=1
# print(lst)

ans=0
ans2=0
for i in range(m):
    if lst[m-i-1]<=n/2 and ans+pow(2,m-i-1)<=k:
        ans+=pow(2,m-i-1)
# print(ans)
# print(ans2)
for i in range(n):
    ans2+=ans^a[i]

print(ans2)
import numpy as np
N,M,X = map(int,input().split())
arr = np.array([list(map(int,input().split())) for i in range(n)])
C = arr.T[0]
A = arr.T[1:].T


cost = np.zeros(1<<N, np.int64)
ability = np.zeros((1<<N, M), np.int64)
for i in range(N):
    cost[1<<i:1<<(i+1)] = cost[:1<<i] + C[i]
    ability[1<<i:1<<(i+1)] = ability[:1<<i] + A[i]

ok = np.all(ability >= X, axis=1)

x = cost[ok]
answer = -1 if len(x) == 0 else x.min()
print(answer)


### FIXED CODE ###

import numpy as np
n,m,x = map(int,input().split())
a = [list(map(int,input().split())) for i in range(n)]

ans = np.inf
flag = 0
for i in range(2**n):
    r = np.array([0]*(m+1))
    for j in range(n):
        if (i>>j)&1:
            for k in range(m+1): r[k] += a[j][k]
    if np.all(r[1:]>=x):
        if ans > r[0]: ans = r[0]
        flag = 1
    else: flag = 0

if flag: print(ans)
else: print("-1")
import itertools 
n = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))
l = list(itertools.permutation([i for i in range(1, n+1)]))
print(abs(l.index(P) - l.index(Q)))

### FIXED CODE ###

import itertools 
n = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))
l = list(itertools.permutations([i for i in range(1, n+1)]))
print(abs(l.index(P) - l.index(Q)))
import math
def distance(x1,x2,y1,y2):
  d=math.sqrt((x1-x2)**2+(y1-y2)**2)
  return d
count=int(input())
zahyou=[]
for i in range(count):
  a=input().split(" ")
  zahyou.append(a)

lenth=0
for i in zahyou:
  for j in zahyou:
    lenth=lenth+distance(int(i[0]),int(j[0]),int(i[1]),int(j[1]))
print(lenth/count)

### FIXED CODE ###

a=int(input())
print(a*a)
#ABC079C

n=raw_input()
s=[]
for i in xrange(4):
 s.append(n[i])
if s[0]==s[1]==s[2] or s[1]==s[2]==s[3] or s[2]==s[3]==s[4]:
 print 'Yes'
else:
 print 'No'


### FIXED CODE ###

#ABC079C

n=raw_input()
s=[]
for i in xrange(4):
 s.append(n[i])
if s[0]==s[1]==s[2] or s[1]==s[2]==s[3]:
 print 'Yes'
else:
 print 'No'
# coding: utf-8

def main()
  n, b, r = map(int, input().split())

  x = n // (b + r)

  if n % (b + r) > b:
      print(x * b + b)

  else:
      print((x * b) + (n % (b + r)))
      

if __name__ == '__main__':
    main()
    

### FIXED CODE ###

# coding: utf-8

n, b, r = map(int, input().split())

x = n // (b + r)

if n % (b + r) > b:
    print(x * b + b)
   
else:
    print((x * b) + (n % (b + r)))
from fractions import gcd

n = int(input())
a = [int(x) for x in input().split()]

def lcm(x, y):
    return (x * y) // gcd(x, y)
l = a[0]
for i in range(n):
    if i == 0:
        continue
    l = lcm(l, a[i])
sum = 0
for i in range(n):
    sum += l / a[i]
    sum %= 1000000007
print(sum)


### FIXED CODE ###

import sys
from fractions import gcd
input = sys.stdin.readline

def lcm(x, y):
    return (x * y) // gcd(x, y)
def main():
    n = int(sys.stdin.readline())
    a = list(map(int,input().split()))
    
    l = a[0]
    for i in range(n):
        l = lcm(l, a[i])
    sum = 0
    for i in range(n):
        sum += l // a[i]
    print(sum % 1000000007)
main()
a,b = map(int, input().split())
diff = b - a - 1
def tower(n):
    if n < 1:
        return 0
    return n + tower(n - 1)
print(tower(diff) - a)

### FIXED CODE ###

a,b = map(int, input().split())
print(int(((b-a)*(b-a+1))/2) - b)
a, b, c, d = map(int, input().split())
if b * d >= 0:
  print(b * d)
else:
  z = []

  for x in range(a, b + 1):
    for y in range(c, d + 1):
      z.append(x * y)
print(max(z))

### FIXED CODE ###

a, b, c, d = map(int, input().split())
print(max(a * c, a * d, b * c, b * d))
import pandas as pd
N = int(input())
S = []
P = []
for i in range(N):
    S1, SP = input().split()
    S = S + [S1]
    P = P + [int(SP)]
df = pd.DataFrame({'city': S, 'point': P})
df = df.sort_values(by=['point'], ascending=False)
df = df.sort_values(by=['city'], ascending=True)
for x in df.index:
    print(x+1)

### FIXED CODE ###

N = int(input())
DF = []
for i in range(N):
    S1, SP = input().split()
    DF = DF + [[i+1, S1, int(SP)]]
DF1 = sorted(DF, key=lambda x:x[2], reverse=True)
DF2 = sorted(DF1, key=lambda x:x[1], reverse=False)
for i in range(N):
    print(DF2[i][0])
def main():
	n = int(input())
	a = list(map(int, input().split()))
	dp = [[0] * n for _ in range(n)]
	for i in range(n):
    	dp[i][i] = a[i]
	for i in range(n - 2, -1, -1):
    	for j in range(i + 1, n):
        	dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])
    print(dp[0][n-1])
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
dp = [[0] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = a[i]

for i in range(n - 2, -1, -1):
    for j in range(i + 1, n):
        dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])

print(dp[0][n - 1])
print (int(input()//3)

### FIXED CODE ###

print (int(input())//3)
N, M, Q = map(int, input().split())
reqs = [list(map(int, input().split())) for _ in range(Q)]

As = []

def make(A):
  global As, N, M
  if len(A) == N+1:
    As.append(A)
  elif:
    for i in range(A[len(A)-1], M+1):
      A.append(i)

make([1])

max = 0
for A in As:
  score = 0
  for req in reqs:
    if A[req[1]] - A[req[0]] == req[2]:
      score += req[3]
  max = max(score, max)

print(max)

### FIXED CODE ###

N, M, Q = map(int, input().split())
reqs = [list(map(int, input().split())) for _ in range(Q)]

As = []

def make(A):
  global As, N, M
  # print(A)
  if len(A) == N+1:
    As.append(A)
  else:
    for i in range(A[len(A)-1], M+1):
      make(A+[i])

make([1])

maxs = 0
for A in As:
  score = 0
  for req in reqs:
    if A[req[1]] - A[req[0]] == req[2]:
      score += req[3]
  maxs = max(score, maxs)

print(maxs)
H,W,A,B=map(int,input().split())
def kaijo(a):
    x=1
    for i in range(a):
       x=x*(i+1)
    return x
def con(a,b):
    x=kaijo(a)
    y=kaijo(b)
    z=kaijo(a-b)
    res = x/y/z
    return res

def calc(x,y):
    res = con(x+y-2,x-1)
    return res

all = calc(H,W)
for i in range(B):
    x=i+1
    k = calc(x,H-A)*calc(A,W-x)
    all=all-k
result=int(all)%(7+10**9)
print(result)

### FIXED CODE ###

H, W, A, B = [int(_) for _ in input().split()]
mod = 10**9 + 7
 
X = [i for i in range(H + W + 1)]
X[0] = 1
for i in range(2, H + W + 1):
    X[i] = X[i - 1] * i % mod
 
Y = X.copy()
Y[-1] = pow(Y[-1], mod - 2, mod)
for i in range(H + W, 1, -1):
    Y[i - 1] = i * Y[i] % mod
 
 
def comb(x, y):
    return X[x] * Y[y] * Y[x - y] % mod
 
 
ans = 0
for i in range(B, min(B + H - A, W)):
    ans += comb(H - A + B - 1, i) * comb(W + A - B - 1, W - i - 1)
    ans %= mod
print(ans)
a,b,c = list(map(int,input().split()))
a,b = b,a
a,c = c,a
print(f'{a} {b} {c}')

### FIXED CODE ###

a,b,c = list(map(int,input().split()))
a,b = b,a
a,c = c,a
print(a,b,c)
n=input().split()
a=int(n[0])
b=int(n[1])
c=int(n[2])
k=b//n
if k>c:
  print(c)
else:
  print(k)

### FIXED CODE ###

import math
x = input().split()
A = int(x[0])
B = int(x[1])
C = int(x[2])
if (math.floor(B/A) >= C):
  print(C)
else:
  print(math.floor(B/A))
def dfs(graph, node, dist):
    if graph[node-1][2] == 1:
        return
    else:
        graph[node-1][2] = 1
        graph[node-1][3] += dist
        if graph[node-1][3] % 2 == 0:
            graph[node-1][4] = 1
        else:
            pass
        ll = graph[node-1][0]
        for i in range(len(ll)):
            dfs(graph, ll[i], graph[node-1][3] + graph[node-1][1][i]);

def main():
    n = int(input())
    edge = []
    for i in range(n-1): edge.append(list(map(int,input().split())))

# graph[[node, node, ...], [dist, dist, ...], [reached or not], 
#       [dist from root], [color]]
    graph = [[[],[],0,0,0] for i in range(n)]
    for i in range(n-1):
        node1 = edge[i][0]
        node2 = edge[i][1]
        weight = edge[i][2]
        graph[node1-1][0].append(node2)
        graph[node2-1][0].append(node1)
        graph[node1-1][1].append(weight)
        graph[node2-1][1].append(weight)
    
    dfs(graph, 1, 0)
    for i in range(n):
        print(graph[i][4])

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def dfs(graph, node, dist):
    if graph[node-1][2] == 1:
        return
    else:
        graph[node-1][2] = 1
        graph[node-1][3] += dist
        if graph[node-1][3] % 2 == 0:
            graph[node-1][4] = 1
        else:
            pass
        ll = graph[node-1][0]
        for i in range(len(ll)):
            dfs(graph, ll[i], graph[node-1][3] + graph[node-1][1][i]);

def main():
    n = int(input())
    edge = []
    for i in range(n-1): edge.append(list(map(int,input().split())))

# graph[[node, node, ...], [dist, dist, ...], [reached or not], 
#       [dist from root], [color]]
    graph = [[[],[],0,0,0] for i in range(n)]
    for i in range(n-1):
        node1 = edge[i][0]
        node2 = edge[i][1]
        weight = edge[i][2]
        graph[node1-1][0].append(node2)
        graph[node2-1][0].append(node1)
        graph[node1-1][1].append(weight)
        graph[node2-1][1].append(weight)
    
    dfs(graph, 1, 0)
    for i in range(n):
        print(graph[i][4])

if __name__ == "__main__":
    main()
num=int(input())
if(num%2==0): 
     print(0.5)
else
     print((num/2+1)/num)



### FIXED CODE ###

n=int(input())
c=0
for i in range(1,n+1):
    if(i%2!=0):
        c+=1
print('%.10f'%(c/n))
from itertools import product

x = int(input())

for a, b in product(list(range(-1000,1000)), repeat=2):
    if a - b == x:
        print(int(a**0.2), int(b**0.2))
        break


### FIXED CODE ###

from itertools import combinations

x = int(input())
num = [i**5 for i in range(1000)]

for a, b in combinations(num, 2):
    if a - b == x:
        print(int(a**0.2), int(b**0.2))
    elif a + b == x:
        print(int(a**0.2), -int(b**0.2))
    elif b - a == x:
        print(int(b**0.2), int(a**0.2))
    elif b + a == x:
        print(int(b**0.2), -int(a**0.2))
    else:
        continue
    break
N, M = map(int, input().split())
ans = 0
Q = [0] * N
wrong = [0] * N
for i in (M):
  p, S = map(str, input().split())
  p = int(p) - 1
  if Q[p] == 0 and S == "AC":
    ans += wrong[p]
    Q[p] = 1
  elif S == "WA":
    wrong[p] += 1
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
ans1 = 0
ans2 = 0
Q = [0] * N
wrong = [0] * N
for i in range(M):
  p, S = map(str, input().split())
  p = int(p) - 1
  if Q[p] == 0 and S == "AC":
    ans1 += 1
    ans2 += wrong[p]
    Q[p] = 1
  elif S == "WA":
    wrong[p] += 1
print(ans1,ans2)
n = list(map(int,input().split()))
if n.sorted() == [1,4,7,9]:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

n = list(map(int,input().split()))
if sorted(n) == [1,4,7,9]:
  print("YES")
else:
  print("NO")
import math
n, d = map(int, input().split())
p = 0
for i in range(n):
  x, y = map(int, input().split())
  if sqrt(pow(x,2)+pow(y,2)) ≤ d :
    p += 1
print(p)
  

### FIXED CODE ###

from math import *
n, d = map(int, input().split())
p = 0
for i in range(n):
  x, y = map(int, input().split())
  if sqrt(pow(abs(x),2)+pow(abs(y),2)) <= d :
    p += 1
print(p)
while true:
if W==0 and H==0 :
    break
H,W = map(int,raw_input().split())
print '#' * W + '\n'
/*実行すると、この直前の行でerrorになる。なぜ。。。*/
print ('#'+ '.'*(W-2)+ '#'+'\n')*(H-2)
print '#'*W + '\n'

### FIXED CODE ###

while 1:
    H, W = map(int,raw_input().split())
    if H + W == 0: break
    print ('#' * W)
    for h in range(H-2):
        print ('#' + '.' * (W - 2) + '#')
    print ('#' * W + '\n')