Harryxun/stf_run huggingface dataset:
n, m = map(int, input().split())
*a, = map(int, input().split())

a = sorted(a)

for i in range(m):
    a[n-1] = a[n-1] // 2
    temp = a.pop()

    left = 0
    right = n-2
    mid = 0
    while left < right:
        mid = (left + right) // 2
        if a[mid] > temp:
            right = mid - 1
            if right == left:
                a.insert(right+1, temp)
        elif a[mid] < temp:
            left = mid + 1
            if right == left:
                a.insert(right, temp)
        else:
            a.insert(right, temp)
            break
    
    
print(sum(a))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
*a, = map(int, input().split())

ans = []
for i in range(n):
    heapq.heappush(ans, -a[i])

for i in range(m):
    temp = -heapq.heappop(ans)
    heapq.heappush(ans, -(temp//2))

print(-sum(ans))
S = input()
judge = True
for i in range(len(S)//2):
    if S[i] != S[len(S) - i - 1]:
        judge = False
        break


if judge:        
    for i in range(int((len(S)-1)/2)):
  
        if S[i] != S[int((len(S)-1)/2)- 1 - i]:
            judge = False
            break
        elif S[int((N+3)/2)-1 + i] != S[N-1-i]:
            judge = False
            break

if judge:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

S = input()
N = len(S)
judge = True
for i in range(len(S)//2):
    if S[i] != S[len(S) - i - 1]:
        judge = False
        break


if judge:        
    for i in range(int((len(S)-1)/2)):
  
        if S[i] != S[int((len(S)-1)/2)- 1 - i]:
            judge = False
            break
        elif S[int((N+3)/2)-1 + i] != S[N-1-i]:
            judge = False
            break

if judge:
    print("Yes")
else:
    print("No")
#ABC125C-GCDonBlackboard.py

from sys import stdin
from fractions import gcd
from functools import reduce
from functools import lru_cache

input = stdin.readline

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

@lru_cache
def L(i):
    if i == 0:
        return 0
    else:
        return gcd(L(i-1),A[i-1])

@lru_cache
def R(i):
    if i == N:
        return 0
    else:
        return gcd(R(i+1),A[i])

M = []

for i in range(N):
    M.append(gcd(L(i), R(i+1)))

print(max(M))


### FIXED CODE ###

#ABC125C-GCDonBlackboard.py

from sys import stdin
from sys import setrecursionlimit
#import random
from fractions import gcd
from functools import lru_cache

setrecursionlimit(1000000)

input = stdin.readline

N = int(input())
A = list(map(int, input().split()))
#A = [random.randrange(1,10**9) for _ in range(N)]

@lru_cache(maxsize=None)
def L(i):
    if i == 0:
        return 0
    else:
        return gcd(L(i-1),A[i-1])

@lru_cache(maxsize=None)
def R(i):
    if i == N:
        return 0
    else:
        return gcd(R(i+1),A[i])

M = []

for i in range(N):
    M.append(gcd(L(i), R(i+1)))

print(max(M))
n,m = map(int, input().split())
sc=[list(map(int,input().split())) for i in range(m)]
s=[]
c=[]
f=0
ans=[str(0) for i in range(n)]
for i in range(m):
    if sc[i][0]==1 and sc[i][1]==0 and n!=1:
        f=-1
        break
    else:
        if sc[i][0] in s:
            if sc[i][1]!=c[s.index(sc[i][0])]:
                f=-1
                break
        else:
            ans[sc[i][0]-1]=str(sc[i][1])
            s.append(sc[i][0])
            c.append(sc[i][1])
if s[i] in 1:
    if n!=1 and c[s.index(1)]==0:
        f=-1
if f==-1:
    print(-1)
else:
    if n==1:
        print(''.join(ans))
    else:
        if ans[0]==str(0):
            ans[0]==str(1)
        print(''.join(ans))


### FIXED CODE ###

N,M=map(int,input().split())
sc = [list(map(int, input().split())) for _ in range(M)]
a=str(0)*N
A=[a[i] for i in range(len(a))]
x=0
#print(sc)
b=[]
c=[]
for i in range(M):
    if (sc[i][0] == 1) and (sc[i][1]==0) and (N!=1):
        x=-1
        break
    else:
        if (sc[i][0]) in b:#左から何桁目の情報が既にある場合、既に登録されているその桁の値と新たに登録しようとしてるその桁の値が異なるとき弾く
            if sc[i][1]!=int(c[b.index(sc[i][0])]):
                #print(c[b.index(sc[i][0])])
                x=-1
                break
        else:
            A[sc[i][0]-1]=str(sc[i][1])
            b.append(sc[i][0])
            c.append(sc[i][1])
if x==-1:
    print(-1)      
elif b==[] and (N!=1):
    if N==2:
        print(10)
    elif N==3:
        print(100)
elif (1 not in b) and(N!=1):
    A[0]=str(1)
    a="".join(A)
    print(a)
elif  (1 not in b) and (2 not in b) and (N==3):
    A[0]=str(1)
    A[1]=str(0)
    a="".join(A)
    print(a)

else:
    a="".join(A)
    print(a)
def f(x):
  if x <= 0:
    return 0
  return (x%10)+f(x//10)

n = int(input)
fx = f(n)
ans = "Yes" if n % fx == 0 else "No"
print (ans)

### FIXED CODE ###

def f(x):
  if x <= 0:
    return 0
  return (x%10)+f(x//10)

n = int(input())
fx = f(n)
ans = "Yes" if n % fx == 0 else "No"
print (ans)
num = int(input())
List = input().split(" ")
height = [int(n) for n in List]
dp = [{} for n in range(10000)]
def jump(a,now):
  if now in dp[a]:
    return dp[a][now]
  if a == num:
    res = 0
  elif a+2 > num:
    res = jump(a+1,height[a])+abs(now-height[a])
  else:
    res = min(jump(a+1,height[a])+abs(now-height[a]),jump(a+2,height[a+1])+abs(now-height[a+1]))
  dp[a][now] = res
  return res
print(jump(1,height[0]))

### FIXED CODE ###

num = int(input())
List = input().split(" ")
height = [int(n) for n in List]
dp = [0 for n in range(10 ** 5 * 2)]
a = 0
while dp[num-1] == 0:
  a+= 1
  if a == num:
    break
  if a == 1:
    dp[a] = abs(height[a]-height[a-1])
  else:
    dp[a] = min(abs(height[a]-height[a-1])+dp[a-1],abs(height[a]-height[a-2])+dp[a-2])
print(dp[num-1])
import math
S = int(input())
L = 10**9

def search():
    p = int(math.sqrt(S))
    q = p
    i = 0
    while p*q < S:
        if i % 2 == 0 or q == L-1: p += 1
        if i % 2 == 1 or p == L-1: q += 1
        i += 1
    target = p*q - S
    assert target < L
    return (0, 0, p, 1, target, q)

print(*search())

### FIXED CODE ###

import math
S = int(input())
L = 10**9

def search():
    p = int(math.sqrt(S))
    q = p
    i = 0
    while p*q < S:
        if i % 2 == 0 or q == L: p += 1
        if i % 2 == 1 or p == L: q += 1
        i += 1
    assert p <= L and q <= L
    target = p*q - S
    divisor = 1
    #assert target < L
    return (0, 0, p, divisor, target, q)

print(*search())
a=int(input())
if a%2==0:
  print(0.5)
 else:
  print((a-1)/2/a)

### FIXED CODE ###

a=int(input())
if a%2==0:
    print(0.5)
else:
    print(1-(a-1)/2/a)
S=input()

count=0

for i in S:
  if i=="1":
    count +=1

print(min(i,len(S)-count))

### FIXED CODE ###

S=input()
 
count=0
 
for i in S:
  if i=="1":
    count +=1
 
print(min(count,len(S)-count)*2)
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <numeric>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

int main(void)
{
    int n;
    cin >> n;

    ll ans = 1;

    ll r = 1e18;

    vector<ll> a(n);

    for (auto &x : a)
    {
        cin >> x;
        if (x == 0)
        {
            cout << 0 << endl;
            return 0;
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (1000000000000000000 / ans <= a[i])
        {
            cout << -1 << endl;
            return 0;
        }

        ans *= a[i];
    }

    cout << ans << endl;
}


### FIXED CODE ###

n = int(input())

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

ans = 1

for i in range(n):
   if a[i] == 0:
        print(0)
        exit()

for i in range(n):
    ans *= a[i]
    if ans > 1e18:
        print(-1)
        exit()

print(ans)
S = list(input())
price = 700
for i in S:
    if S[i] == "○":
        price += 100
print(price)

### FIXED CODE ###

S = list(input())
price = 700
for i in range(len(S)):
    if S[i] == "o":
        price += 100
print(price)
n = int(input())
a = list(map(int, input().split()))

N = max(a)

li = [abs(N/2 - k) for k in a]
index = li.index(min(li))

print("{0} {1}".format(N, a[index]))


### FIXED CODE ###

a, b, x = map(int, input().split())
if x >= a and x <= a + b:
    print("YES")
else:
    print("NO")
n = int(input())
a = list(map(int, input().split()))
b = [0]*10**5+3
c = [0]*10**5+3
for i in range(n):
  if i%2==0:
    b[a[i]]+=1
  else:
    c[a[i]]+=1
bm=max(b)
cm=max(c)
if b.index(max(b))==c.index(max(c)):
  b[b.index(max(b))]=0
  c[c.index(max(c))]=0
  bm2=max(b)
  cm2=max(c)
  print(min(n-bm-cm2,n-cm-bm2))
else:
  print(n-bm-cm)
  


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0]*(10**5+3)
c = [0]*(10**5+3)
for i in range(n):
  if i%2==0:
    b[a[i]]+=1
  else:
    c[a[i]]+=1
bm=max(b)
cm=max(c)
if b.index(max(b))==c.index(max(c)):
  b[b.index(max(b))]=0
  c[c.index(max(c))]=0
  bm2=max(b)
  cm2=max(c)
  print(min(n-bm-cm2,n-cm-bm2))
else:
  print(n-bm-cm)
# -*- coding: utf-8 -*-

# スペース区切りの整数の入力
N = int(input())
an = list(map(int, input().split()))

sum_cnt = 0
for a in an:
    tmp = a
    cnt = 0
    while tmp % 2 == 0:
        cnt += 1
        tmp = tmp / 2

    sum_cnt += cnt

print(sum_cnt)


### FIXED CODE ###

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

# スペース区切りの整数の入力
A, B = map(int, input().split())

if A <= 8 and B <= 8:
    print('Yay!')
else:
    print(':(')
a,b=map(int,input())
if a<13:
  if 5<a:
  print(b/2)
  else:
    print(0)
else:
  print(b)

### FIXED CODE ###

a,b=map(int,input().split())
if a<13:
  if 5<a:
    print(b//2)
  else:
    print(0)
else:
  print(b)
import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
　　x = int(input())
　　b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
　　res = INF
　　for S in [s[b - 1], s[b]]:
　　　　for T in [t[d - 1], t[d]]:
　　　　　　d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
　　　　　　res = min(res, d1, d2)
print(res)

### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
  x = int(input())
  b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
  res = INF
  for S in [s[b - 1], s[b]]:
    for T in [t[d - 1], t[d]]:
      d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
      res = min(res, d1, d2)
  print(res)
N=input()
A=input()
B=N%500
if(B-A==0):
    print("Yes")
else:
    print("No")


### FIXED CODE ###

N=int(input())
A=int(input())
N!=0
B=int(N%500)
if(B <= A):
    print("Yes")
else:
    print("No")
n = [ input() for _ in range ( int ( input () ) )]
m = [ input() for _ in range ( int ( input () ) )]
l = list( set (n) )
print( max(0, max(n.count( l[i] ) - (m.count( l[i] ) for i in range(len(l))))))

### FIXED CODE ###

n=[input() for _ in range(int(input()))]
m=[input() for _ in range(int(input()))]
l=list(set(n))
print(max(0,max(n.count(l[i])-m.count(l[i]) for i in range(len(l)))))
A,B = map(int, input().split())

L = [1,2,3]
L.remove(A)
L.remove(B)
for l in L:
  print(l)

### FIXED CODE ###

A = int(input())
B = int(input())
L = [1,2,3]
L.remove(A)
L.remove(B)
for l in L:
  print(l)
n = int(input())
a = list(map(int,input().split()))

t = 0
cnt = 0
for i in range(n):
    if a[i] == i+1:
        t += 1

for i in range(0,n,2):
    if (a[i] == i+1) and (a[i+1] == i+2):
        cnt += 1

print(t-cnt)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
 
t = 0
for i in range(n):
    if a[i] == i+1:
        t += 1

i = 0
cnt = 0
while i < n-1:
    if a[i] == i+1 and a[i+1] == i+2:
        cnt += 1
        i += 2
    else:
        i += 1

print(t-cnt)
N, M, Q = map(int, input().split())
X = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(M):
    L, R = map(int, input().split())
    X[L][R] = 1

# for i in range(N):
#     for j in range(N):
#         X[i+1][j+1] += X[i][j+1] + X[i+1][j]
# print(*X, sep='\n')
# print('')

for i in range(N+1):
    for j in range(N):
        X[i][j+1] += X[i][j]
# print(*X, sep='\n')

for i in range(N+1):
    for j in range(N):
        # print(i, j)
        X[j+1][i] += X[j][i]
ans = []
for _ in range(Q):
    p, q = map(int, input().split())
    ans.appned(X[q][q] - X[q][p-1] - X[p-1][q] + X[p-1][p-1])
    # print(ans)
# print(*X, sep='\n')
print(*ans, sep='\n')

### FIXED CODE ###

N, M, Q = map(int, input().split())
X = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(M):
    L, R = map(int, input().split())
    X[L][R] += 1

# for i in range(N):
#     for j in range(N):
#         X[i+1][j+1] += X[i][j+1] + X[i+1][j]
# print(*X, sep='\n')
# print('')

for i in range(N+1):
    for j in range(N):
        X[i][j+1] += X[i][j]

for i in range(N+1):
    for j in range(N):
        X[j+1][i] += X[j][i]
# print(*X, sep='\n')

ans = []
for _ in range(Q):
    p, q = map(int, input().split())
    ans.append(X[q][q] - X[q][p-1] - X[p-1][q] + X[p-1][p-1])

print(*ans, sep='\n')
from fractions import gcd
from functools import reduce

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def cnt_div_2(x):
    cnt = 0
    while x > 0:
        if x % 2 == 0:
            x //= 2
            cnt += 1
        else:
            break
    return cnt

def main():
    N, M = map(int, input().split())
    A = list(set(map(int, input().split())))
    cnt_2 = cnt_div_2(A[0])
    for a in A:
        if cnt_div_2(a) != cnt_2:
            print(0)
            exit()


    common = lcm_list(A)
    max_A = max(A)
    cnt = M // common
    if (cnt + 0.5) * common <= M:
        print(cnt + 1)
    else:
        print(cnt)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

from fractions import gcd
from functools import reduce

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def cnt_div_2(x):
    cnt = 0
    while x > 0:
        if x % 2 == 0:
            x //= 2
            cnt += 1
        else:
            break
    return cnt

def main():
    N, M = map(int, input().split())
    A = list(set(map(int, input().split())))
    cnt_2 = cnt_div_2(A[0])
    for a in A:
        if cnt_div_2(a) != cnt_2:
            print(0)
            exit()


    common = lcm_list(A)
    max_A = max(A)
    cnt = M // common
    if ((2 * cnt + 1) * common) // 2 <= M:
        print(cnt + 1)
    else:
        print(cnt)
    
if __name__ == "__main__":
    main()
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def prime_decomposition(n):
  i = 2
  d = {}
  while i * i <= n:
    while n % i == 0:
      n /= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d

def eratosthenes(n):
    prime = []
    limit = n**0.5
    numbers = [i for i in range(2,n+1)]
    while True:
        p = numbers[0]
        if limit <= p:
            return prime + numbers
        prime.append(p)
        numbers = [i for i in numbers if i%p != 0]
    return prime

N = int(input())
A = [int(input()) for i in range(N+1)]
g = A[0]
for a in A:
     g = gcd(g,a)
d = prime_decomposition(g)
ans = [p for p in d]

prime = eratosthenes(N+2)
A.reverse()
for p in prime:
    if A[-1]%p != 0:
        continue
    for n in range(1,p):
        s = 0
        for k in range(int((N-n)/(p-1))+1):
            s += A[n+k*(p-1)]
            s %= p
        if s != 0:
            break
    if s == 0:
        ans.append(p)

ans = list(set(ans))
ans.sort()

for p in ans:
    print(p)

### FIXED CODE ###

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

def prime_decomposition(n):
  i = 2
  d = {}
  while i * i <= n:
    while n % i == 0:
      n //= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d

def eratosthenes(n):
    if n < 2:
        return []
    prime = []
    limit = n**0.5
    numbers = [i for i in range(2,n+1)]
    while True:
        p = numbers[0]
        if limit <= p:
            return prime + numbers
        prime.append(p)
        numbers = [i for i in numbers if i%p != 0]
    return prime

def ok(p):
    if A[0]%p != 0:
        return False
    B = [A[i]%p for i in range(1,N+1)]
    mod = [0]*(p-1)
    for i in range(N):
        mod[i%(p-1)] += B[i]
        mod[i%(p-1)] %= p
    return sum(mod)==0

N = int(input())
A = [int(input()) for i in range(N+1)][::-1]
g = abs(A[0])
for a in A:
     g = gcd(g,abs(a))
d = prime_decomposition(g)
ans = [p for p in d]

prime = eratosthenes(N+1)

for p in prime:
    if ok(p):
        ans.append(p)

ans = list(set(ans))
ans.sort()

for p in ans:
    print(p)
n = int(input())
a = list(map(int,input().split()))
c = defaultdict(int)
for x in a:
  c[x] += 1

top, sec = 0,0
for k,v in c:
  if n < 2:
    continue
  if k > top:
    sec = top
    top = k
  elif k > sec:
    sec = k

print(top * sec)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
c = defaultdict(int)
for x in a:
  c[x] += 1

sq = False
top, sec = 0,0
for k,v in c.items():
    if v < 2:
        continue
    if k > top:
        sq = v >= 4
        sec = top
        top = k
    elif k > sec:
        sec = k

if sq:
    print(top * top)
else:
    print(top * sec)
a, b, c = input().split()

if a + b + c >= 22:
  print('bust')
else:
  print('win')

### FIXED CODE ###

a, b, c = input().split()

if int(a) + int(b) + int(c) >= 22:
  print('bust')
else:
  print('win')
N,Q = map(int,input().split())
Ki_Oya=dict()
Ki_Dict=dict()
Ki_Count=dict()
for i in range(N-1):
  A,B = input().split()
  if A not in Ki_Dict:
    Ki_Dict[A]=set(A)
    Ki_Count[A]=0
    Ki_Oya[A]=set(A)
  if B not in Ki_Dict:
    Ki_Dict[B]=set(B)
    Ki_Count[B]=0
    Ki_Oya[B]=set(B)|Ki_Oya[A]
  Ki_Dict[A]|set(B)
  if A in Ki_Oya:
    for j in list(Ki_Oya[A]):
      Ki_Dict[j]|set(B)

for i in range(Q):
  P,X = input().split()
  X = int(X)
  for i in list(Ki_Dict[P]):
    Ki_Count[i] += X
Ki_List = list(Ki_Dict.keys())
ans=[]
for i in Ki_List:
  ans.append(str(Ki_Count[i]))
print(" ".join(ans))

### FIXED CODE ###

N,Q = map(int,input().split())
Ki_Oya=dict()
for i in range(N-1):
  A,B = map(int,input().split())
  Ki_Oya[B-1]=A-1
Counter_list=[0]*N
for i in range(Q):
  P,X=map(int,input().split())
  Counter_list[P-1] += X
print(Counter_list[0],end=" ")
for i in range(1,len(Counter_list)):
  Counter_list[i] += Counter_list[Ki_Oya[i]]
  print(Counter_list[i],end=" ")
print("")
N, M = map(int, input().split())
S = []
C = []
for _ in range(N):
  s, c = map(int, input().split())
  S.append(s - 1)
  C.append(c)

num = ['*'] * N

for s, c in zip(S, C):
  if num[s] == '*':
    num[s] = str(c)
  elif num[s] != str(c):
    print(-1)
    exit()

print(''.join(num).replace('*', '0'))

### FIXED CODE ###

N, M = map(int, input().split())
S = []
C = []
for _ in range(M):
  s, c = map(int, input().split())
  S.append(s - 1)
  C.append(c)

num = ['*'] * N

for s, c in zip(S, C):
  if s == 0 and c == 0 and N != 1:
    print(-1)
    exit()
  if num[s] == '*':
    num[s] = str(c)
  elif num[s] != str(c):
    print(-1)
    exit()

if num[0] == '*' and N != 1:
  num[0] = '1'
print(''.join(num).replace('*', '0'))
def isOver(a,b):
    return True if (a[0]-b[0])**2 + (a[1]-b[1])**2 < 4.0+1.0e-12 else False

def largestGroup(mtrx,num):
    mx = 1
    ls = [num]
    for i in mtrx[num]:
        if i == num:
            continue
        m = youKnow(mtrx,ls,i)
        mx = max(mx,m)
    return mx

def youKnow(mtrx,ls,num):
    mx = len(ls)
    if set(ls) <= set(mtrx[num]):
        if num not in ls:
            ls.append(num)
        for i in list(set(mtrx[num])-set(ls)):
            m = youKnow(mtrx,ls,i)
            mx = max(mx,m)
    return mx

while True:
    max_over = 0
    n = int(raw_input())
    if n == 0: break
    seals = [map(float, raw_input().split(",")) for i in range(n)]

    overs = []
    for i in range(n):
        over = []
        for j in range(n):
            if isOver(seals[i],seals[j]):
                over.append(j)
    overs.append(over)

    ref = [i for i in range(n)]
    for i in ref:
        num_over = largestGroup(overs,i)
        for j in overs[i]:
            ref.remove(j)
        if num_over > max_over:
            max_over = num_over
    print max_over

### FIXED CODE ###

def isOver(array,x,y):
	return True if (array[0]-x)**2+(array[1]-y)**2 <= 1.01 else False
	
while True:
    mx = 0
    n = int(raw_input())
    if n == 0: break
    seals = [map(float, raw_input().split(",")) for i in range(n)]
    x = 0
    while x < 10.0:
    	y = 0.0
    	while y < 10.0:
    		num = 0
    		for seal in seals:
    			if isOver(seal,x,y):
    				num += 1
    		mx = max(mx,num)
    		y += 0.1
        x += 0.1
    print mx
class UnionFind:
    def __init__(self,n):
        super().__init__()
        self.par = [-1]*n
        self.rank = [0]*n
        self.tsize = [1]*n
    
    def root(self,x):
        if self.par[x] == -1:
            return x 
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x_r = self.root(x)
        y_r = self.root(y)
        
        if self.rank[x_r]>self.rank[y_r]:
            self.par[y_r] = x_r

        elif self.rank[x_r]<self.rank[y_r]:
            self.par[x_r] = y_r

        elif x_r != y_r:
            self.par[y_r] = x_r
            self.rank[x_r] += 1

        if x_r != y_r:
            size = self.tsize[x_r]+self.tsize[y_r]
            self.tsize[x_r] = size
            self.tsize[y_r] = size

    def isSame(self,x,y):
        return self.root(x) == self.root(y)

    def size(self,x):
        return self.tsize[self.root(x)]

def main():

    n= tuple([int(t)for t in input().split()])
    uf = UnionFind(2*(n+1))
    
    for _ in range(n-1):
      x,y,w = tuple([int(t)for t in input().split()])
      if w%2==0:
        uf.unite(2*x,2*y)
        uf.unite(2*x+1,2*y+1)
      else:
        uf.unite(2*x+1,2*y)
        uf.unite(2*x,2*y+1)

    w = uf.root(0)
    for i in range(n):
      if w == ufroot(2*i):
        print(1)
      else:
        print(0)

if __name__ == "__main__":
    main()


### FIXED CODE ###

class UnionFind:
    def __init__(self,n):
        super().__init__()
        self.par = [-1]*n
        self.rank = [0]*n
        self.tsize = [1]*n
    
    def root(self,x):
        if self.par[x] == -1:
            return x 
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x_r = self.root(x)
        y_r = self.root(y)
        
        if self.rank[x_r]>self.rank[y_r]:
            self.par[y_r] = x_r

        elif self.rank[x_r]<self.rank[y_r]:
            self.par[x_r] = y_r

        elif x_r != y_r:
            self.par[y_r] = x_r
            self.rank[x_r] += 1

        if x_r != y_r:
            size = self.tsize[x_r]+self.tsize[y_r]
            self.tsize[x_r] = size
            self.tsize[y_r] = size

    def isSame(self,x,y):
        return self.root(x) == self.root(y)

    def size(self,x):
        return self.tsize[self.root(x)]

def main():

    n= int(input())
    uf = UnionFind(2*(n+1))
    
    for _ in range(n-1):
      x,y,w = tuple([int(t)for t in input().split()])
      if w%2==0:
        uf.unite(2*x,2*y)
        uf.unite(2*x+1,2*y+1)
      else:
        uf.unite(2*x+1,2*y)
        uf.unite(2*x,2*y+1)

    w = uf.root(2)

    for i in range(1,n+1):
      if w == uf.root(2*i):
        print(1)
      else:
        print(0)

if __name__ == "__main__":
    main()