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

def tax(p,x):
    return p*(100+x) // 100 # 整数除算

def solve(X,Y,S):
    ans = 0
    oldsum = 0
    newsum = 0
    for a in range(1,S):
        for b in range(1,S-a+1): #税抜き価格a,bの総和はS以下である
            oldsum = tax(a,X)+tax(b,X) #税制改定前の税込合計額
            print(oldsum,a,b)
            if oldsum == S: # 新税でのtax(a,Y)+tax(b,Y) について検討 
                newsum = tax(a,Y)+tax(b,Y) 
                if newsum > ans:
                    ans =newsum
            if oldsum > S:
                break # b増加ならばsum増加のため
    print(ans)

while True:
    a,b,c = map(int, input().split())
    if a == 0:
        break
    solve(a,b,c)


### FIXED CODE ###

def tax(p,x):
    return p*(100+x) // 100 # 整数除算

def solve(X,Y,S):
    ans = 0
    oldsum = 0
    newsum = 0
    for a in range(1,S):
        for b in range(1,S-a+1): #税抜き価格a,bの総和はS以下である
            oldsum = tax(a,X)+tax(b,X) #税制改定前の税込合計額
            if oldsum == S: # 新税でのtax(a,Y)+tax(b,Y) について検討 
                newsum = tax(a,Y)+tax(b,Y) 
                if newsum > ans:
                    ans =newsum
            if oldsum > S:
                break # b増加ならばsum増加のため
    return ans

while True:
    X,Y,S = map(int, input().split())
    if X == 0:
        break
    print(solve(X,Y,S))
### BUGGY CODE ###

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

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

    def connect(self, x, y):
        x = self.root(x)
        y = self.root(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 isConnect(self, x):
        return self.root(x) == self.root(y)

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

N, K = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))

INF = 10 ** 18
ans = -INF
dp = [[-INF] * (N + 1) for _ in range(N)]
uf = Unionfind(N)

for i in range(N):
    dp[i][0] = 0
    now = i
    for j in range(min(N, K)):
        now = P[now]
        dp[i][j + 1] = dp[i][j] + C[now]
        uf.connect(i, now)
        ans = max(ans, dp[i][j + 1])

for i in range(N):
    M = uf.size(i)
    if dp[i][M] <= 0:
        continue
    roop = K // M
    move = K % M
    if move == 0:
        roop -= 1
        move = M
    for j in range(move):
        ans = max(ans, dp[i][M] * roop + dp[i][j + 1])

print(ans)


### FIXED CODE ###

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

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

    def connect(self, x, y):
        x = self.root(x)
        y = self.root(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 isConnect(self, x):
        return self.root(x) == self.root(y)

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

N, K = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))

INF = 10 ** 18
ans = -INF
dp = [[-INF] * (N + 1) for _ in range(N)]
uf = Unionfind(N)

for i in range(N):
    dp[i][0] = 0
    now = i
    for j in range(min(N, K)):
        now = P[now]
        dp[i][j + 1] = dp[i][j] + C[now]
        uf.connect(i, now)
        ans = max(ans, dp[i][j + 1])

for i in range(N):
    M = uf.size(i)
    if dp[i][M] <= 0:
        continue
    roop = K // M
    move = K % M
    if move == 0:
        roop -= 1
        move = M
    for j in range(move):
        ans = max(ans, dp[i][M] * roop + dp[i][j + 1])

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

n,k=map(int,input().split())
ab=[]
for i in  range(n):
    a,b=map(int,input().split())
    ab.append([a,b])
ab.sort()
x=[]
for i in range(n):
    x.extend([ab[i][0]]*ab[i][1])
    if len(x)>k:
        break
print(x[k-1])


### FIXED CODE ###

n,k=map(int,input().split())
ab=[]
for i in  range(n):
    a,b=map(int,input().split())
    ab.append([a,b])
ab.sort()
c=0
for i in range(n):
    c+=ab[i][1]
    if c>=k:
        print(ab[i][0])
        exit()
### BUGGY CODE ###

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

def barger(n):
    if n == 0 :
        return "1"
    else:
        return "0" + barger(n-1) + "1" + barger(n-1) + "0"

print(barger(n)[:x].count("1"))

### FIXED CODE ###

n,x = map(int,input().split())
p=[1]
s=[1]
for i in range(50):
    p.append(p[i]*2+1)
    s.append(s[i]*2+3)

def burger(n,x):
    if n ==0:
        return 1
    elif x == 1:
        return 0
    elif x<=1+s[n-1]:
        return burger(n-1,x-1)
    elif x == 2+s[n-1]:
        return p[n-1] + 1
    elif x <= 2 + s[n-1] * 2:
        return p[n-1] + 1 + burger(n-1,x-s[n-1]-2)
    elif x <= 3 + s[n-1] * 2:
        return 1 + p[n-1] * 2
    else:
        print("ERROR")

print(burger(n,x))
### BUGGY CODE ###

def main():
  K=list()
  L=list()
  N=int(input())
  R=[0]*N
  t=set()
  for i in range(N):
    A=input()
    if A in t:
      R[L.index(A)]+=1
      L.append(A)
    else:
      R[i]=1
      L.append(A)
    t=set(L)
  c=max(R)
  for i in range(N):
    if R[i]==c:
      K.append(L[i])
  K=sorted(K)
  for i in range(len(K)):
    print(K[i])
if __name__ == '__main__':
    main()

### FIXED CODE ###

c={}
N=int(input())
for i in range(N):
  s=input()
  if s not in c:
    c[s]=1
  else:
    c[s]+=1
n=max(c.values())
L=list()
for i in c:
  if c[i]==n:
    L.append(i)
L=sorted(L)
for i in L:
  print(i)
### BUGGY CODE ###


n=int(input())
s=tuple(input())

pin=set()
for i in range(0,1000):
    yn=""
    stri=format(i,"03d")
    for ii in range(n-2):
        if stri[0]==s[ii]:
            yn="yes1"
            break
    if yn!="yes1":
        continue
    for iii in range(ii+1,n-1):
        if stri[1]==s[iii]:
            yn="yes2"
            break
    if yn!="yes2":
        continue
    if stri[2] in s[iii+1:n]:
        pin.add(stri)

print(len(pin))        
    

### FIXED CODE ###

n=int(input())
s=list(input())

pin=set()
for i in range(0,1000):
    yn=""
    stri=format(i,"03d")
    for ii in range(n-2):
        if stri[0]!=s[ii]:
            continue
        else:
            yn="yes1"
            break
    if yn!="yes1":
        yn="no"
        continue
    for iii in range(ii+1,n-1):
        if stri[1]!=s[iii]:
            continue
        else:
            yn="yes2"
            break
    if yn!="yes2":
        yn="no"
        continue
    for iiii in range(iii+1,n):
        if stri[2]!=s[iiii]:
            continue
        else:
            yn="yes3"
            break
    if yn=="yes3":
        pin.add(stri)
    else:
        continue

print(len(pin))
### BUGGY CODE ###

n,m,k=map(int,input().split())
ans=0
mod=998244353
f=[1]
for i in range(n):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
for kk in range(k+1):
  anss=m*pow(m-1,n-1-kk,mod)%mod
  anss=anss*comb(n-1,kk)%mod
  ans=(ans+anss)%mod
print(ans)

### FIXED CODE ###

n,m,k=map(int,input().split())
ans=0
mod=998244353
f=[1]
for i in range(n):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
for kk in range(k+1):
  anss=m*pow(m-1,n-1-kk,mod)%mod
  anss=anss*comb(n-1,kk)%mod
  ans=(ans+anss)%mod
print(ans)
### BUGGY CODE ###

Q = int(input())
prime = [2]
def setPrime(TOP):
    for x in range(3,TOP+1):
        for y in range(len(prime)):
            if x%prime[y] == 0:
                break
            if y == len(prime)-1:
                prime.append(x)
l = [0]*Q
r = [0]*Q
for i in range(Q):
    l[i],r[i] = list(map(int,input().split()))

setPrime(max(r))

result = [0]*max(r)
for x in range(len(prime)):
    if int((prime[x]+1)/2) in prime:
        for y in range(prime[x]-1,max(r)):
            result[y] += 1

for n in range(Q):
    if l[n] > 1:
        print(result[r[n]-1]-result[l[n]-2])
    else:
        print(result[r[n]-1])

### FIXED CODE ###

import math
Q=int(input())
querys = [list(map(int,input().split())) for x in range(Q)]
large = max(q[1] for q in querys)
like2017 = [0]*(large+1)

#siever
cands = [False if (5 < i and (i%2)*(i%3)*(i%5) == 0) or (i < 2) or (i == 4) else True for i in range(large+1)]
if 5 <= large:
  for i in range(6,int(math.sqrt(large)+1)):
    if cands[i]:
      for j in range(i*i,large+1,i):
        if cands[j]:
          cands[j] = False

#find 2017-like-number          
for x in range(large+1):
  if cands[x] and cands[(x+1)//2]:
    like2017[x] = 1
for y in range(1,large+1):
  like2017[y] += like2017[y-1]

for q in querys:
  print(like2017[q[1]]-like2017[q[0]-1])
### BUGGY CODE ###

input()
(*a,) = map(int, input().split())
ma = max(a)

最小公倍数 = ma
while True:
    if all(最小公倍数 % i == 0 for i in a):
        break
    最小公倍数 += ma
ans = 最小公倍数 / sum(最小公倍数 // i for i in a)
print([ans, int(ans)][ans % 1 == 0])

### FIXED CODE ###

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

ただの倍数 = 1
for i in set(a):
    ただの倍数 *= i
ans = ただの倍数 / sum(ただの倍数 // i for i in a)
print([ans, int(ans)][ans % 1 == 0])
### BUGGY CODE ###

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

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [0]*N
for i in range (len(A)):
    B[A[i]-1] +=1
print('\n'.join(map(str, B)))
### BUGGY CODE ###

N = int(input())
L = [int(i) for i in input().split()]

L_len = len(L)

L.sort(reverse=True)

count = 0
for i in range(L_len - 2):
    for j in range(i + 1, L_len - 1):
        for k in range(j + 1, L_len):
            if L[i] < L[j] + L[k]:
                count += 1
            else:
                break

print(count)

### FIXED CODE ###

N = int(input())
L = [int(i) for i in input().split()]

from bisect import bisect_left

L.sort()

count = 0
for i in range(0, N - 2):
    for j in range(i + 1, N - 1):
        length = L[i] + L[j]
        idx = bisect_left(L, length)
        count += idx - j - 1

print(count)
### BUGGY CODE ###

def MAP(): return list(map(int,input().split()))

#排他的論理和
def XOR(lst):
    #lst = [000,010,011...] type is str
    lst = sorted(lst,key = lambda x:len(x),reverse = True)
    n = len(lst[0])
    ans = []
    for i in range(1,n+1):
        tmp = 0
        for j in lst:
            if len(j)>=i:
                if j[-i]=="1":
                    tmp+=1
        if tmp%2==0:
            ans.insert(0,"0")
        else:
            ans.insert(0,"1")
    return "".join(ans)

#10進数→2進数
def binary(num):
    lst = []
    while num!=0:
        lst.insert(0,num%2)
        num = num//2
    return "".join(map(str,lst))

#2進数→10進数
def decimal(num):
    ans=0
    for i,x in enumerate(str(num)[::-1]):
        ans += int(x)*2**i
    return ans

A,B = MAP()
lst = [binary(i) for i in range(A,B+1)]
print(decimal(XOR(lst)))


### FIXED CODE ###

def MAP(): return list(map(int,input().split()))
def f(x):
    tmp = (x+1)%4
    if tmp==0:
        return 0
    elif tmp==1:
        return x
    elif tmp==2:
        return 1
    else:
        return 1^x
A,B = MAP()
print(f(A-1)^f(B))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    G = [[] for i in range(N + 1)]
    for i in range(N-1):
        u, v, w = (int(i) for i in input().split())
        G[u].append((v,w))
        G[v].append((u,w))
    color = [-1] * (N + 1)
    todo = []
    todo_append = todo.append
    todo_pop = todo.pop
    cur = 0
    color[1] = cur
    todo_append(1)
    while todo:
        u = todo[-1]
        for next_v,w in G[u]:
            if color[next_v] != -1: 
                continue
            if w&1:
                color[next_v] = (color[u] + 1) % 2
            else:
                color[next_v] = color[u]
            todo_append(next_v)
            break
        else:
            todo_pop(-1)
    for i in range(1,N+1):
        print(color[i])
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    G = [[] for _ in range(N+1)]
    st = 0
    st_w = 0
    for i in range(N-1):
        u, v, w = (int(i) for i in input().split())
        G[u].append((v, w))
        G[v].append((u, w))
        if i == 0:
            st = u
            st_w = w
    color = [-1] * (N+1)  # 0: white, 1: black, -1: undefined
    from collections import deque

    def coloring(v, w):
        """
        breadth-first search
        a simplified version
        """
        que = deque()
        color[v] = 0
        que.append((v, w))
        while que:
            u, w = que.popleft()
            for v, d in G[u]:
                if color[v] != -1:
                    continue
                if d % 2 != 0:
                    n_col = (color[u] + 1) % 2
                else:
                    n_col = color[u]
                color[v] = n_col
                que.append((v, d))

    coloring(st, st_w)
    for c in color[1:]:
        print(c)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

temp = [ [0 for _ in range(n)] for _ in range(n)]
tables = [ [0 for _ in range(n)] for _ in range(n)]

for _ in range(m):
    l, r = map(int, input().split())
    temp[l - 1][r - 1] += 1

pq = [tuple(int(x) - 1 for x in input().split()) for _ in range(q)]

for i in range(n):
    for j in range(n):
        tables[i][j] = sum(temp[i][:j + 1])

for p, q in pq:
    ans = 0
    if p > 0:
        for i in range(p, q + 1):
            ans += tables[i][q] - tables[i][p - 1]
    else:
        for i in range(q + 1):
            ans += tables[i][q]
    print(ans)

### FIXED CODE ###

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

temp = [ [0 for _ in range(n)] for _ in range(n)]
tables = [ [0 for _ in range(n)] for _ in range(n)]

if n == 1:
    print('1')
    exit()

for _ in range(m):
    l, r = map(int, input().split())
    temp[l - 1][r - 1] += 1

pq = [tuple(int(x) - 1 for x in input().split()) for _ in range(q)]

hoge = 0
for j in range(n):
    hoge += temp[0][j]
    tables[0][j] = hoge

for i in range(1, n):
    hoge = 0
    for j in range(n):
        hoge += temp[i][j]
        tables[i][j] = tables[i - 1][j] + hoge

for p, q in pq:
    if p == 0:
        print(tables[q][q])
    else:
        print(tables[q][q] - tables[p - 1][q] - tables[q][p - 1] + tables[p - 1][p - 1] )
### BUGGY CODE ###

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

dp = [10 ** 10] * (n + k)
h += [10 ** 10] * k
dp[0] = 0

for i in range(n):
    for j in range(1, k + 1):
        cost = abs(h[i] - h[i + j])
        dp[i + j] = min(dp[i + j], dp[i] + cost)

print(dp[n - 1])


### FIXED CODE ###

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

dp = [10 ** 10] * (n + k)
h += [10 ** 10] * k
dp[0] = 0

for i in range(n):
    for j in range(1, k + 1):
        cost = abs(h[i] - h[i + j])
        dp[i + j] = min(dp[i + j], dp[i] + cost)

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

S = input()
K = int(input())

ans = ''
i = 0
while(K>0):
  if i == len(S)-1:
    K %= 26
    ans += chr(((ord(S[i])-97)+K)%26+97)
    K = 0
  else:
    if S[i] != 'a':
      a = 26-(ord(S[i])-97)
      if K > a:
        ans += 'a'
        K -= a
      else:
        ans += S[i]
    else:
      ans += S[i]
  i += 1
print(ans)


### FIXED CODE ###

S = input()
K = int(input())

S = list(S)
i = 0
while(K>0):
  if i == len(S)-1:
    S[i] = chr(((ord(S[i])-97)+K)%26+97)
    K = 0
  else:
    a = 26-(ord(S[i])-97)
    if a != 26 and K >= a:
      S[i] = 'a'
      K -= a
  i += 1
print(''.join(S))
### BUGGY CODE ###

N,K=[int(x) for x in input().rstrip().split()]
p=[int(x) for x in input().rstrip().split()]
ex=[1/2*(i+1) for i in p]

mx=0
ind=0
ans=0
# for i in range(ind,ind+K):
#   ans+=ex[p[i]-1]

for i in range(N-K+1):
  mx=max(mx,sum(ex[i:i+K]))
print(mx)




### FIXED CODE ###

N,K=[int(x) for x in input().rstrip().split()]
p=[int(x) for x in input().rstrip().split()]
ex=[1/2*(i+1) for i in p]
ruiseki=[0]
ans=0

for i in range(N):
  ruiseki.append(ruiseki[i]+ex[i])


for i in range(N+1-K):
  if ans<ruiseki[i+K]-ruiseki[i]:
    ans=ruiseki[i+K]-ruiseki[i]
print(ans)
### BUGGY CODE ###

N, Ma, Mb = map(int, input().split())
Med = [tuple(map(int, input().split())) for _ in range(N)]
N *= 100
import numpy as np
dp = np.full((N+1,N+1),np.inf) #dp[i,j]:Aがiグラム、Bがjグラムの時の最小予算
dp[0,0] = 0 
from itertools import product
R = lambda x:reversed(range(x,N+1))
for a,b,c in Med:
    for i,j in product(R(a),R(b)):
        dp[i,j] = min(dp[i,j], dp[i-a,j-b]+c)

ans = np.inf
for i,j in product(R(1),R(1)):
    if i*Mb == j*Ma:
        ans = min(ans, dp[i,j])
print(int(ans) if ans != np.inf else -1)

### FIXED CODE ###

import collections
import copy
INF = 10000

#入力
N, Ma, Mb = map(int, input().split())
medichine = [tuple(map(int, input().split())) for _ in range(N)]

dp = {}
#dp初期化
dp = collections.defaultdict(lambda:INF)
dp[0,0] = 0

for a, b, c in medichine:
    dp_ = copy.copy(dp)
    for ca,cb in dp.keys():
        dp_[ca+a, cb+b] = min(dp_[ca+a, cb+b], dp[ca,cb]+c)
    dp = dp_    

ans = INF
for ca,cb in dp.keys():
    if ca == cb == 0: continue
    if ca*Mb == cb*Ma:
        ans = min(ans, dp[ca,cb])
        
print(-1 if ans == INF else ans)
### BUGGY CODE ###

# RGBの数列からから'R,G,B'を取り出す必要がある．
# RGBの組み合わせのなかから(r*g*b)の中から，例えば，Rを固定して，Rからの距離の絶対値が一致するようなものは
# iを固定して， j-i=k-j= l として j,kの位置で，i以外の２文字になっているかを確認する．
# i
from collections import deque
N=int(input())
S=input()
R=deque()
G=deque()
B=deque()
for i,s in enumerate(S):
    if s=='R':
        R.append(i)
    if s == 'G':
        G.append(i)
    if s == 'B':
        B.append(i)

rgb = len(R)*len(G)*len(B)
import bisect

for i in range(0,N):
    if i in R:
        lest1 = G
        lest2 = B
    elif i in G:
        lest1 = B
        lest2 = R
    else:
        lest1 = R
        lest2 = G
    max_j_width = int((N-1-i)/2)+1
    for j in range(1,max_j_width+1):
        if i+j in lest1 and i+2*j in lest2:
            rgb-=1
        elif i+2*j in lest1 and i+j in lest2:
            rgb-=1
print(rgb)









### FIXED CODE ###

# RGBの数列からから'R,G,B'を取り出す必要がある．
# RGBの組み合わせのなかから(r*g*b)の中から，例えば，Rを固定して，Rからの距離の絶対値が一致するようなものは
# iを固定して， j-i=k-j= l として j,kの位置で，i以外の２文字になっているかを確認する．
# i
from collections import deque
N=int(input())
S=input()
R=deque()
G=deque()
B=deque()
for i,s in enumerate(S):
    if s=='R':
        R.append(i)
    if s == 'G':
        G.append(i)
    if s == 'B':
        B.append(i)

rgb = len(R)*len(G)*len(B)
import bisect
# ワンホット表現にしてみる
R_one = [0 for _ in range(N+3)]
G_one = [0 for _ in range(N+3)]
B_one = [0 for _ in range(N+3)]

for r in R:
    R_one[r] = 1
for g in G:
    G_one[g] = 1
for b in B:
    B_one[b] = 1

for i in range(0,N):
    if i in R:
        lest1 = G_one
        lest2 = B_one
    elif i in G:
        lest1 = B_one
        lest2 = R_one
    else:
        lest1 = R_one
        lest2 = G_one
    max_j_width = int((N-1-i)/2)+1
    for j in range(1,max_j_width+1):
        if lest1[i+j]== lest2[i+2*j] == 1:
            rgb-=1
        elif lest2[i + j] == lest1[i + 2 * j] == 1:
            rgb-=1
print(rgb)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
query = [[0]*N for _ in range(N)]
for _ in range(N-1):
    a, b, c = mapint()
    query[a-1][b-1] = c
    query[b-1][a-1] = c

Q, K = mapint()
from collections import deque
stack = deque([(K-1, 0, -1)])
dist = [0]*N
while stack:
    now, cnt, per = stack.pop()
    lis = query[now]
    dist[now] = cnt
    for nx, c in enumerate(lis):
        if nx==per:
            continue
        if c!=0:
            stack.append((nx, cnt+c, now))

for _ in range(Q):
    x, y = mapint()
    print(dist[x-1]+dist[y-1])

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
query = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = mapint()
    query[a-1].append((b-1, c))
    query[b-1].append((a-1, c))

Q, K = mapint()
from collections import deque
stack = deque([(K-1, 0, -1)])
dist = [0]*N
while stack:
    now, cnt, per = stack.pop()
    lis = query[now]
    dist[now] = cnt
    for nx, c in lis:
        if nx==per:
            continue
        if c!=0:
            stack.append((nx, cnt+c, now))

for _ in range(Q):
    x, y = mapint()
    print(dist[x-1]+dist[y-1])
### BUGGY CODE ###

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

#隣接する最大の部分をとって(N+1)/2すればいい

max_part = 0
for i in range(N-K+1):
    x = sum(ps[i:i+K])
    if max_part < x:
        max_part = x

print((max_part+K)/2)

### FIXED CODE ###

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

max_sum = sum(ps[:K])
num = sum(ps[:K])

for i in range(N-K):
    num = num - ps[i] + ps[i+K]
    max_sum = max(max_sum,num)
    

print((max_sum+K)/2)
### BUGGY CODE ###

N,M = map(int,input().split())
AB= []
for i in range(N):
    AB.append([int(j) for j in input().split()])
 
AB = sorted(AB, key=lambda x: x[0])
AB = sorted(AB, key=lambda x: x[1], reverse=True)
#お金が高い＞日にちがかからない　の順にソート
 
for i in range(N):  #同じ仕事があっても消せるようにIDを振る
    AB[i].append(i)
 
money = 0
 
def NdayOK(n):  #あとn日残されているときに選べる仕事のリスト
    nd = []
    for i in range(N):
        if AB[i][0] <= n:
            nd.append(AB[i][2])
    return(nd)
 
checker = []
for i in range(M+1):
    NOi = NdayOK(i)
    for j in NOi:
        if AB[j][2] not in checker:
            money += AB[j][1]
            checker.append(AB[j][2])
            break
 
print(money)

### FIXED CODE ###

import heapq

N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]
L=[[] for i in range(M+1)]

for i in range(N):
    if AB[i][0]<=M:
        L[AB[i][0]].append(-AB[i][1])

LL=[]
money=0

for i in range(1,M+1):
    for j in L[i]:
        heapq.heappush(LL,j)
    if len(LL)==0:
        continue
    money+=heapq.heappop(LL)

print(-money)
### BUGGY CODE ###

n = int(input())
u = [-1] * n
u[0] = 0
a = []
for i in range(n-1):
    u1, u2, w = [int(j) for j in input().split()]
    u1, u2 = u1 - 1, u2 - 1
    a.append((u1, u2, w))
i=0
while a:
    j=a[i]
    if u[j[0]] != -1:
        u[j[1]] = (u[j[0]] + j[2]) % 2
        del a[i]
        i=-1
    elif u[j[1]] != -1:
        u[j[0]] = (u[j[1]] + j[2]) % 2
        del a[i]
        i = -1
    i+=1

for i in u:
    print(i)
    


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)


def input():
    return sys.stdin.readline()


n = int(input())
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b, c = [int(i) - 1 for i in input().split()]
    c += 1
    e[a].append([b, c])
    e[b].append([a, c])

c = [0] * n


def dfs(i=0, r=-1, co=0):
    c[i] = co
    for j, k in e[i]:
        if j != r:
            dfs(j, i, (co+k) % 2)


dfs()
print("\n".join(map(str, c)))