Harryxun/stf_run huggingface dataset:
n = int(input())
a = [(A, i) for i, A in enumerate(map(int, input().split()))]

a.sort()
dp = [[-1]*n for _ in range(n)]

def recursive(l, r):
    if l > r:
        return 0
    if dp[l][r] >= 0:
        return dp[l][r]
    k = r - l
    energy, pos = a[k]
    from_l = energy * abs(l - pos)
    from_r = energy * abs(r - pos)
    dp[l][r] = max(from_l + recursive(l+1, r), from_r + recursive(l, r-1))
    return dp[l][r]

print(recursive(0, n-1))

### FIXED CODE ###

def main():
  N = int(input())
  INF = float('inf')
  A = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
  A = sorted(A, key=lambda x: x[1], reverse = True)

  dp = [[-INF] * (N+1) for _ in range(N+1)]
  dp[0][0] = 0

  for s in range(1, N+1):
    for l in range(s+1):
      r = s - l
      dp[l][r] = max(dp[l-1][r] + A[s-1][1] * abs(A[s-1][0]-l), dp[l][r-1] + A[s-1][1] * abs(N-r+1-A[s-1][0]))
    
  ans = 0
  for m in range(N):
    if(dp[m][N-m] > ans):
      ans = dp[m][N-m]
    
  print(ans)

main()
n,m = map(int, raw_input().split(' '))
keys = set(range(1,n+1))
for _ in range(m):
	a,b = map(int, raw_input().split(' '))
    keys = keys.intersection(set( range(a,b+1)  ))
    if len(keys) == 0:
      break
print len(keys)

### FIXED CODE ###

n,m = map(int, raw_input().split(' '))
def intersection(A,B):
	a,b  = max(A[0],B[0]), min(A[1],B[1])
	return [a,b] if a <= b else []

r = [1,n+1]
for _ in range(m):
	a,b = map(int, raw_input().split(' '))
	r = intersection(r, [a,b])
	if len(r) == 0: break
print (r[1] - r[0] + 1) if r else 0
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    

a,b,c=int(input())

if (c-a)>=0 and b-c>=0:
	print("Yes")
else:
	print("No")

### FIXED CODE ###

import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    

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

if (c-a)>=0 and b-c>=0:
	print("Yes")
else:
	print("No")
from collections import deque
H, W = map(int,input().split())
S = [list(input()) for _ in range(H)]
dhw = [[0,1],[0,-1],[1,0],[-1,0]]

ans = 0
for h in range(H):
  for w in range(W):
    d = deque([h,w])
    maze = [[-1] * W for _ in range(H)]
    if S[h][w] == '#':
      continue
    maze[h][w] = 0
    while d:
      ht , wt = d.popleft()
      for dh, dw in dhw:
        nh = ht + dh
        nw = wt + dw
        if not(0 <= nh < H and 0 <= nw < W):
          continue
        S[nh][nw] == '#':
          continue
        if maze[nh][nw] == -1:
          d.append([nh,nw])
          maze[nh][nw] = maze[ht][wt] + 1
    ans = max(ans,max[max(l) for l in maze])

print(ans)


### FIXED CODE ###

from collections import deque

def main():
    H, W = map(int, input().split())
    maze = [list(input()) for _ in range(H)]
    directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

    ans = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == '#':
                continue

            goal_dists = [[-1] * W for _ in range(H)]
            goal_dists[h][w] = 0
            d = deque([[h, w]])

            while d:
                ht, wt = d.popleft()
                for dh, dw in directions:
                    if not (0 <= ht+dh < H and 0 <= wt+dw < W):
                        continue
                    if maze[ht+dh][wt+dw] == '#':
                        continue
                    if goal_dists[ht+dh][wt+dw] == -1:
                        goal_dists[ht+dh][wt+dw] = goal_dists[ht][wt] + 1
                        d.append([ht+dh, wt+dw])
            
            ans = max(ans, max([max(l) for l in goal_dists]))

    print(ans)

if __name__ == "__main__":
    main()
# 16D8101022L 小林勇希 ID:k_mb python3

def GCD(x,y):
    if(x >= y):
        z = y
        w = x%y
    else:
        z = x
        w = y%x
    if(w != 0):
        GCD(z,w)
    else:
        print(z)

a = int(input())
b = int(input())
GCD(a,b)

"""実行結果

100
55
5



66
77
11

"""



### FIXED CODE ###

def GCD(x,y):

    if(x >= y):
        z = y
        w = x%y
    else:
        z = x
        w = y%x

    if(not(w == 0)):
        return GCD(z,w)
    else:
        return z

A = [int(i) for i in input().split()]
print(GCD(A[0],A[1]))

"""実行結果

100 55
5



66 77
11

"""
import sys
n=list(input())
N=len(n)
k=int(input())
dp=[[0 for i in range(len(n))] for j in range(k)]
ans=0
x=int(n[0])

if k==1:
  ans+=(N-1)*9
  ans+=x
  print(ans)
  sys.exit()

elif k==2:
  ans+=(N-1)*(N-2)*81//2
  ans+=(x-1)*(N-1)*9
  n2=n[1:N+1]
  N2=len(n2)
  x=int(n2[0])
  ans+=(N2-1)*9
  ans+=x
  print(ans)
  sys.exit()

else:
  ans+=(N-1)*(N-2)*(N-3)*729//6
  ans+=(x-1)*(N-1)*(N-2)*81//2
  n=n[1:N+1]
  N=len(n)
  x=int(n[0])
  ans2=0
  ans2+=(N-1)*(N-2)*81//2
  ans2+=(x-1)*(N-1)*9
  n2=n[1:N+1]
  N2=len(n2)
  x=int(n2[0])
  ans2+=(N2-1)*9
  ans2+=x
  ans+=ans2
  print(ans)
  sys.exit()

### FIXED CODE ###

import sys
n=list(input())
N=len(n)
k=int(input())
x=int(n[0])
if N<k:
  print(0)
  sys.exit()

def s1(m):
  N=len(m)
  x=int(m[0])
  if N>1 and x==0:
    m2=m[1:N+1]
    return s1(m2)
  elif x==0:
    return 0
  else:
    ans=0
    ans+=(N-1)*9
    ans+=x
    return ans

def s2(m):
  N=len(m)
  x=int(m[0])
  if N>1 and x==0:
    m2=m[1:N+1]
    return s2(m2)
  elif x==0:
    return 0
  else:
    ans=0
    ans+=((N-1)*(N-2))*81//2
    ans+=((x-1)*(N-1))*9
    m2=m[1:N+1]
    ans+=s1(m2)
    return ans
  
def s3(m):
  N=len(m)
  x=int(m[0])
  if N>1 and x==0:
    m2=m[1:N+1]
    return s3(m2)
  elif x==0:
    return 0
  else:
    ans=0
    ans+=((N-1)*(N-2)*(N-3)*729)//6
    ans+=((x-1)*(N-1)*(N-2)*81)//2
    m2=m[1:N+1]
    ans+=s2(m2)
    return ans

if k==1:
  print(s1(n))
  sys.exit()

if k==2:
  print(s2(n))
  sys.exit()

if k==3:
  print(s3(n))
  sys.exit()
n = input()
print(''.join(map(lambda c: '9' if c == '1' else '1' if c == '9' else c, n))

### FIXED CODE ###

n = input()
print(''.join(map(lambda c: '9' if c == '1' else '1' if c == '9' else c, n)))
x=input()
print(X[0],X[8],X[10])

### FIXED CODE ###

X=input()
print(X[0]+X[8]+X[-7])
from math import log2

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

def f(n):
    return sum(n^i for i in A)

K += 1

if K == 1:
    print(f(0))
else:
    mb = int(log2(K))
    hN = N / 2

    s = 0
    A_ = A.copy()
    for i in range(mb+1):
        s += (0 if sum(i &0x01 for i in A_) >= hN else 1) * (1 << i)
        A_ = [i >> 1 for i in A_]

    if s >= K:
        def g(i, n, k):
            mask = (2**i) - 1
            s_ = (s & mask) | (k - (k & mask))
            s_ -= (s_ & (1 << i))
            return s_

        gl = [g(i, s, K) for i, b in enumerate(f"{K:b}"[::-1]) if b == "1"]
        fl = [f(i) for i in gl]
        print(max(fl))
    else:
        print(f(s))


### FIXED CODE ###

from math import log2

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

def f(n):
    return sum(n^i for i in A)

K += 1

if K == 1:
    print(f(0))
else:
    mb = int(log2(K))
    hN = N / 2

    s = 0
    A_ = A.copy()
    for i in range(mb+1):
        s += (0 if sum(i &0x01 for i in A_) >= hN else 1) * (1 << i)
        A_ = [i >> 1 for i in A_]

    if s >= K:
        def g(i, n, k):
            mask = (2**i) - 1
            s_ = (s & mask) | (k - (k & mask))
            s_ -= (s_ & (1 << i))
            return s_

        gl = [g(i, s, K) for i, b in enumerate("{:b}".format(K)[::-1]) if b == "1"]
        fl = [f(i) for i in gl]
        print(max(fl))
    else:
        print(f(s))
N,M=map(int,input().split())
L=[0]*M
R=[0]*M
for i range(M):
  L[i],R[i]=map(int,input().split())

def prison(N,M,L,R):
  count=0
  for n in range(N):
    num_of_truth=0
    for l,r in zip(L,R):
      if l<=(n+1)<=r:
        num_of_truth+=1
    if num_of_truth==M:
      count+=1
  return count
 
print(prison(N,M,L,R))


### FIXED CODE ###

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

L=[0]*M
R=[0]*M

for i in range(M):
  L[i],R[i]=map(int,input().split())

def prison(N,M,L,R):
  max_val=min(R)
  min_val=max(L)
  num=max_val-min_val+1
  if num<=0:
    num=0
  return(num)

print(prison(N,M,L,R))
def f(i):
    if memo[i] != float("Inf"):return memo[i]

    memo[i] = min(memo[i],f(i-1)+abs(ary[i-1]-ary[i]))
    if i > 1:memo[i] = min(memo[i],f(i-2)+abs(ary[i-2]-ary[i]))

    return memo[i]
n = int(input())
ary = list(map(int,input().split()))
memo = [float("Inf") for _ in range(n)]
memo[0] = 0
print(f(n-1))

### FIXED CODE ###

nums = int(input())
ary = list(map(int,input().split()))
dp = [0 for i in range(nums)]
for i in range(1,nums):
    dp[i] = float("inf")
jump_min = 0
for i in range(1,nums):
    for x in range(1,3):
        jump = i-x
        if i-x < 0: continue
        jump = dp[i-x] + abs(ary[i-x] - ary[i])
        if jump < dp[i]:
            dp[i] = jump
print(dp[nums-1])
n, k = map(int, input().split())
a = set()

for m in range(k):
  d = int(input())
  print(d)
  for l in range(d):
    a.append(range(n))
  print(a)

### FIXED CODE ###

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

for _ in range(k):
  d = int(input())
  a += [int(m) for m in input().split()]

print(n - len(set(a)))
import math
N,M=map(int,input().split())
l = [int(s) for s in input().split()]

for i in range(M):
  math.floor(l[l.index(max(l))] = l[l.index(max(l))]/2)

p = 0
for i in range(N):
  p += l[i]
print(p)  


### FIXED CODE ###

s = input()
 
if s == 'Sunny':
    print('Cloudy')
elif s == 'Cloudy':
    print('Rainy')
elif s == 'Rainy':
    print('Sunny')
h, w, K = map(int, input().split())
grid = []
for i in range(h):
    grid.append(input())

ans = 1000000
for i in range(2**(h-1)):
    b = format(i, "0{}b".format(h-1))
    ans_temp = b.count("1")
    white_after = [0]*(ans_temp+1)
    index = 0
    for j in range(w):
        for k in range(h):
            if grid[k][j] == "1":
                white_after[index] += 1
            if k != h-1:
                if b[k] == "1":
                    index += 1
        if max(white_after) <= K:
            white_before = white_after[:]
        else:
            for k in range(len(white_after)):
                white_after[k] -= white_before[k]
            white_before = white_after[:]
            ans_temp += 1
        index = 0
    ans = min(ans, ans_temp)

print(ans)


### FIXED CODE ###

h, w, K = map(int, input().split())
grid = []
for i in range(h):
    grid.append(input())

ans = 1000000
for i in range(2**(h-1)):
    b = format(i, "0{}b".format(h-1))
    ans_temp = b.count("1")
    white_after = [0]*(ans_temp+1)
    index = 0
    flag = 1
    for j in range(w):
        for k in range(h):
            if grid[k][j] == "1":
                white_after[index] += 1
            if k != h-1:
                if b[k] == "1":
                    index += 1
        if max(white_after) <= K:
            white_before = white_after[:]
        else:
            try:
                for k in range(len(white_after)):
                    white_after[k] -= white_before[k]
                    if white_after[k] > K:
                        flag = 0
                white_before = white_after[:]
                ans_temp += 1
            except:
                flag = 0
                break
        index = 0
    if flag == 0:
        continue
    ans = min(ans, ans_temp)

print(ans)
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse = True)
    return divisors
N, K = map(int, input().split())
A = list(map(int, input().split()))
m = sum(A)
divisors = make_divisors(m)
for d in divisors:
    A1 = list(map(lambda x:x%d, A))
    A1.sort()
    res = 0
    for i in range(N):
        res+=A1[i]
        if res>K:
            res-=A1[i]
            index = i+1
            break
    res1 = 0
    for i in range(index, N):
        res1+=d-A1[i]
    if res>=res1:
        ans = d
        break
print(ans)        
    

### FIXED CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse = True)
    return divisors
N, K = map(int, input().split())
A = list(map(int, input().split()))
m = sum(A)
divisors = make_divisors(m)
for d in divisors:
    A1 = list(map(lambda x:x%d, A))
    A1.sort()
    res = 0
    index = N
    for i in range(N):
        res+=A1[i]
        if res>K:
            res-=A1[i]
            index = i
            break
    
    res1 = 0
    for i in range(index, N):
        res1+=d-A1[i]
    if res>=res1:
        ans = d
        break
print(ans)
n = input()
print(800 * n - 200 * (n//15))


### FIXED CODE ###

n = int(input())
print(800 * n - 200 * (n//15))
S=input()

if S = 'SUN':
    print(7)
else if S = 'MON':
    print(1)
else if S = 'TUE':
    print(2)
else if S = 'WED':
    print(3)
else if S = 'THS':
    print(4)
else if S = 'FRI':
    print(5)
else if S = 'SAT':
    print(6)

### FIXED CODE ###

S=input()

if S == 'SUN':
    print(7)
elif S == 'MON':
    print(6)
elif S == 'TUE':
    print(5)
elif S == 'WED':
    print(4)
elif S == 'THU':
    print(3)
elif S == 'FRI':
    print(2)
elif S == 'SAT':
    print(1)
a,b,c,d=map(int,input().split())
if a=b:
  print("bad")
  else if b=c:
    print("bad")
    else if c=d:
      print("bad")
      else:
        print("good")

### FIXED CODE ###

s=input()
if s[0]==s[1] or s[1]==s[2] or s[2]==s[3]:
  print("Bad")
else:
  print("Good")
a_,b_ = map(int, (raw_input().strip().split(" ")))

foo = []
for i,a in enumerate(range(a_)):
    foo = raw_input().strip().split(" ")
    for j in range(b_):
        if foo[j] == 'snuke':
            print(chr(65 + j) + str(i + 1))
    

### FIXED CODE ###

a_,b_ = map(int, (raw_input().strip().split(" ")))
foo = []
for i,a in enumerate(range(a_)):
    foo = raw_input().strip().split(" ")
    for j in range(b_):
        if foo[j] == 'snuke':
            print(chr(65 + j) + str(i + 1))
n = int(input())
w_list = list(map(int, input().split()))
print(min([abs(s[:i]-s[i:]) for i in range(1, n)]))

### FIXED CODE ###

n = int(input())
w_list = list(map(int, input().split()))
print(min([abs(sum(w_list[:i])-sum(w_list[i:])) for i in range(1, n)]))
if s=="Sunny":
    print s("Cloudy")
else if s=="Cloudy":
    print ("Rainy")
else if s=="Rainy":
    print ("Sunny")


### FIXED CODE ###

s = str(raw_input())

if s=="Sunny":
    print ("Cloudy")
if s=="Cloudy":
    print ("Rainy")
if s=="Rainy":
    print ("Sunny")
a,b,c=map(input().split())
print('YNeos'[a+b<c::2])

### FIXED CODE ###

a,b,c=map(int,input().split())
print('YNeos'[a+b<c::2])
(int,input().split())
if L >= 0:
  print(int((N-1)/2*(L + L + N )))
else:
  if L + N - 1 >= 0: 
    print(int(N / 2 * (L + L + N - 1)))
  else:
    print(int((N - 1)/ 2 * (L + L + N - 2)))


### FIXED CODE ###

N,L=map(int,input().split())
if L >= 0:
  print(int((N-1)/2*(L + L + N)))
else:
  if L + N - 1 >= 0: 
    print(int(N / 2 * (L + L + N - 1)))
  else:
    print(int((N - 1)/ 2 * (L + L + N - 2)))
K=int.input()
if K%2==0
  A=K*K//4
  print(A)
else:
  B=(K-1)*K//4
  print(B)

### FIXED CODE ###

K=int(input())
if K%2==0:
  A=K*K//4
  print(A)
else:
  B=(K-1)*(K+1)//4
  print(B)
import sys

for v in iter(sys.stdin.readline)
    a,op,b = v.split()
    a = int(a)
    b = int(b)
    if op == '+':
        print(a+b)
    elif op == '-':
        print(a-b)
    elif op == '*':
        print(a*b)
    elif op == '/':
        print(a/b)
    elif op == '?':
        break

### FIXED CODE ###

import sys

for v in iter(sys.stdin.readline,""):
    a,op,b = v.split()
    a = int(a)
    b = int(b)
    if op == '+':
        print(a+b)
    elif op == '-':
        print(a-b)
    elif op == '*':
        print(a*b)
    elif op == '/':
        print(a/b)
    elif op == '?':
        break
a = input()



e = input()
k = input()
if e - a > k:
  	print(':(')
else:
  	print('Yay!')

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())
if e - a > k:
  	print(':(')
else:
  	print('Yay!')
import numpy as np
n = int(input())
a = np.array(input().split(),dtype=int)
sum = 0

kn = [0 for i in range(n)]
for i in range(n):
    kn[a[i]] += 1
for i in range(n):
    sum += kn[i]*(kn[i]-1)//2

for i in range(n):
    x = kn[a[i]]
    print(sum-x+1)


### FIXED CODE ###

import numpy as np
n = int(input())
a = np.array(input().split(),dtype=int)
sum = 0

kn = [0 for i in range(n+1)]
for i in range(n):
    kn[a[i]] += 1
for i in range(n+1):
    sum += kn[i]*(kn[i]-1)//2

for i in range(n):
    x = kn[a[i]]
    print(sum-x+1)
C=[list(input()) for i in range(2)]
if C[0]==reverse(C[1]):
    print('YES')
else:
    print('NO')

### FIXED CODE ###

C=[list(input()) for i in range(2)]
if C[0][0]==C[1][2] and C[0][1]==C[1][1] and C[0][2]==C[1][0]:
    print('YES')
else:
    print('NO')
str = S

print(str[0:2])


### FIXED CODE ###

S= input()

str = S

print(str[0:3])
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = -1e9
for i in range(N):
  cost = 0
  S = []
  x = P[i] - 1
  l = 1
  while 1:
    cost += C[x]
    S.append(cost)
    if x == i:
      break
    l += 1
    x = P[x] - 1
  if cost > 0:
    ans = max(ans, cost * (K // l) + max(S[:K % l]))
  else:
    ans = max(ans, max(S))
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = -1000000000
for i in range(N):
  cost = 0
  S = []
  x = P[i] - 1
  l = 1
  while 1:
    cost += C[x]
    S.append(cost)
    if x == i:
      break
    l += 1
    x = P[x] - 1
  if cost > 0:
    for j in range(l):
      ans = max(ans, S[j] + cost * ((K - j - 1) // l))
  else:
    ans = max(ans, max(S[:min(K, l)]))
print(ans)
h, a = input()
print(int(h/a) + 1)

### FIXED CODE ###

import math

h, a = input().split()
print(math.ceil(int(h)/int(a)))
N=int(input())
AC=0
WA=0
TLE=0
RE=0

for k in range(N):
  K=input()
  if K=="AC":
    AC=AC+1
  if K=="WA":
    WA=WA+1
  if K=="TLE":
    TLE=TLE+1
  if K=="RE":
    RE=RE+1

print("AC x " + AC)
print("WA x " + RE)
print("TLE x " + TLE)
print("RE x " + RE)

### FIXED CODE ###

N=int(input())
AC=0
WA=0
TLE=0
RE=0
 
for k in range(N):
  K=input()
  if K=="AC":
    AC=AC+1
  if K=="WA":
    WA=WA+1
  if K=="TLE":
    TLE=TLE+1
  if K=="RE":
    RE=RE+1
 
print("AC x " + str(AC))
print("WA x " + str(WA))
print("TLE x " + str(TLE))
print("RE x " + str(RE))
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

a.append(23)

count = 0

for i in range(n):
    count += b[a[i]-1]
    print("added"+str(b[a[i]-1]))
    if ((a[i]+1)==a[i+1]):
        print("yeah"+str(c[i]))
        count += c[i+1]
print(count)



### FIXED CODE ###

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

a.append(23)
c.append(0)
count = 0

for i in range(n):
    count += b[a[i]-1]
    #print("added"+str(b[a[i]-1]))
    if ((a[i]+1)==a[i+1]):
        #print("yeah"+str(c[a[i]-1]))
        count += c[a[i]-1]
print(count)
n, m = map(int,input().split())

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

ca = []
for i in la:
    a, b = map(int, input().split())
    ca.append((a,b))

for i in range(len(la)):
    mi = 1000000001
    ans = 0
    for j in range(len(ca)):
        p = abs(la[i][0]-ca[j][0]) + abs(la[i][1]-ca[j][1])
        if  p < mi:
            mi = p
            ans = j+1
    print(ans)



### FIXED CODE ###

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

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

ca = []
for i in range(m):
    a, b = map(int, input().split())
    ca.append((a,b))

for i in range(len(la)):
    mi = 1000000001
    ans = 0
    for j in range(len(ca)):
        p = abs(la[i][0]-ca[j][0]) + abs(la[i][1]-ca[j][1])
        if  p < mi:
            mi = p
            ans = j+1
    print(ans)
import sys
sys.setrecursionlimit(10**10)

n = int(input())
dic = {}
for i in range(n+1):
    if i <= 1: continue
    ai = int(input())
    if ai in dic:
        dic[ai].append(i)
    else:
        dic[ai] = [i]

def dfs(nxt):
    lst = []
    if nxt in dic:
        while dic[nxt] != []:
            child = dic[nxt].pop()
            tempmax = dfs(child)
            lst.append(tempmax)
    else:
        return 0
    lst.sort(reverse=True)
    for i in range(len(lst)):
        lst[i] += i+1
    return max(lst)

ans = dfs(1)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)

n = int(input())
dic = {}
for i in range(n+1):
    if i <= 1: continue
    ai = int(input())
    if ai in dic:
        dic[ai].append(i)
    else:
        dic[ai] = [i]

def dfs(nxt):
    lst = []
    if nxt in dic:
        while dic[nxt] != []:
            child = dic[nxt].pop()
            tempmax = dfs(child)
            lst.append(tempmax)
    else:
        return 0
    lst.sort(reverse=True)
    for i in range(len(lst)):
        lst[i] += i+1
    return max(lst)

ans = dfs(1)
print(ans)
A,B,C,D,E,F=map(int,input().split())
    best_water=0
    best_salt=0
    best_rate=0
    for i in range(30//A+1):#Aの投入数
      for j in range(30//B+1):#Bの投入数
        water=(i*A+j*B)*100
        if water<=F and water:
          max_salt=(i*A+j*B)*E
          for k in range(max_salt//C+1):#Cを何個使うか
            l=(max_salt-C*k)//D#Dは何個つかえるか
            salt=k*C+l*D
            rate=100*salt/(water+salt)
            if rate>best_rate and salt<=max_salt and rate<=E and water+salt<=F:
              best_rate=rate
              best_salt=salt
              best_water=water
    print(best_water+best_salt,best_salt)

### FIXED CODE ###

A,B,C,D,E,F=map(int,input().split())
best_water=0
best_salt=0
best_rate=0
for i in range(30//A+1):#Aの投入数
  for j in range(30//B+1):#Bの投入数
    water=(i*A+j*B)*100
    if water<=F and water:
      max_salt=min(F-(i*A+j*B)*100,(i*A+j*B)*E)
      for k in range(max_salt//C+1):#Cを何個使うか
        l=(max_salt-C*k)//D#Dは何個つかえるか
        salt=k*C+l*D
        rate=100*salt/(water+salt)
        if rate>=best_rate and rate<=E and water+salt<=F:
          best_rate=rate
          best_salt=salt
          best_water=water
print(best_water+best_salt,best_salt)
N = int(input())
a = map(int, input().split())
l = [0]*10**5
ans = 0
num = 0

for i in a:
    l[i] +=1
    l[i+1] +=1
    l[i+2] +=1

print(max(l))

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
l = [0]*(10**5+2)

for i in a:
    l[i] +=1
    l[i+1] +=1
    l[i+2] +=1

print(max(l))
a,b=map(int,input().split())
print(max(0,a-2*b)

### FIXED CODE ###

a, b = map(int, input().split())
print(max(0, a - 2 * b))
import queue
import sys

input = sys.stdin.readline

N = int(input())
nodes = queue.Queue()
for i in range(N - 1):
    nodes.put(list(map(int, input().split())))

B, W = set(), set()
u, v, w = nodes.get()
if w % 2 == 0:
    B.add(u)
    B.add(v)
else:
    B.add(u)
    W.add(v)

while nodes.qsize() != 0:
    u, v, w = nodes.get()
    if w % 2 == 0:
        if u in B or v in B:
            B.add(u)
            B.add(v)
        elif u in W or v in W:
            W.add(u)
            W.add(v)
        else:
            nodes.put(u, v, w)
    else:
        if u in B or v in W:
            B.add(u)
            W.add(v)
        elif u in W or v in B:
            W.add(u)
            B.add(v)
        else:
            nodes.put(u, v, w)

ans = [0] * N
for x in W:
    ans[x - 1] = 1
for x in ans:
    print(x)


### FIXED CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(100000)
input = sys.stdin.readline

N = int(input())
G = defaultdict(list)
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    G[u - 1].append((v - 1, w))
    G[v - 1].append((u - 1, w))
res = [None] * N


def dfs(v, c):
    res[v] = c
    for u, w in G[v]:
        if res[u] is not None:
            continue
        if w % 2 == 0:
            dfs(u, c)
        else:
            dfs(u, 1 - c)


dfs(0, 0)
for x in res:
    print(x)