Harryxun/sft_time huggingface dataset:
### 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))
    def is_bipartite_by_dfs(G,v,color):
        todo = []
        todo_append = todo.append
        todo_pop = todo.pop
        cur = 0
        color[v] = cur
        todo_append(v)
        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)
    color = [-1] * (N + 1) # 0: white, 1: black, -1: undefined
    is_bipartite_by_dfs(G,1,color)
    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=int(input())
A=list(map(int, input().split()))
B=[0]+A
for i in range(0,len(B)):
    print(B.count(i+1))

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
import collections
B=collections.Counter(A)
for i in range(0,N):
    print(B[i+1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import fractions
import numpy as np
 
mod = 10**9+7
 
n = int(input())
a = list(map(int, input().split()))
 
div = a[0]
for i in range(1, n):
    div = div*a[i]//fractions.gcd(div, a[i])

ans = 0
for i in range(n):
    ans += div//a[i]

print(ans%mod)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import fractions
 
mod = 10**9+7
 
n = int(input())
a = list(map(int, input().split()))
 
div = a[0]
for i in a[1:]:
    div = div*i//fractions.gcd(div, i)

ans = 0
for i in a:
    ans += div//i

print(ans%mod)
### BUGGY CODE ###

from collections import Counter

N = int(input())

cntA = Counter(map(int, input().split()))
cntB = Counter(map(int, input().split()))
cntC = Counter(map(int, input().split()))

keyA = sorted(list(cntA.keys()))
keyB = sorted(list(cntB.keys()))
keyC = sorted(list(cntC.keys()))

iA = 0
iC = 0
numA = 0
numC = N
ans = 0
for kB in keyB:
    for i, k in enumerate(keyA[iA:], iA):
        if k >= kB:
            iA = i
            break
        numA += cntA[k]
    else:
        iA = len(keyA)

    for i, k in enumerate(keyC[iC:], iC):
        if k > kB:
            iC = i
            break
        numC -= cntC[k]
    else:
        iC = len(keyC)

    ans += numA * numC * cntB[kB]

print(ans)


### FIXED CODE ###

from collections import Counter

N = int(input())

cntA = Counter(map(int, input().split()))
cntB = Counter(map(int, input().split()))
cntC = Counter(map(int, input().split()))

keyA = sorted(list(cntA.keys()))
keyB = sorted(list(cntB.keys()))
keyC = sorted(list(cntC.keys()))

lenA = len(keyA)
lenC = len(keyC)
iA = 0
iC = 0
numA = 0
numC = N
ans = 0
for kB in keyB:
    for i in range(iA, lenA):
        if keyA[i] >= kB:
            iA = i
            break
        numA += cntA[keyA[i]]
    else:
        iA = lenA

    for i in range(iC, lenC):
        if keyC[i] > kB:
            iC = i
            break
        numC -= cntC[keyC[i]]
    else:
        iC = lenC

    ans += numA * numC * cntB[kB]

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

'''
包除原理
すべての条件を満たしている
2^{N-1}から「どれかの条件を満たしていない」を引けば良い
i番目の条件を満たしていない確率はかんたんに計算できる
Sに属していいないやつが全て条件を満たしていない確率については
Sに対応する辺が全て白となる確率を考えれば良い
'''
from collections import deque
N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
M=int(input())
u=[0 for i in range(M)]
v=[0 for i in range(M)]
for i in range(M):
    u[i],v[i]=map(int,input().split())
    u[i]-=1;v[i]-=1
root=[set() for i in range(M)]
for i in range(M):
    q=deque([u[i]])
    parents=[-1 for i in range(N)]
    reached=[0 for i in range(N)]
    while(len(q)>0):
        r=q.popleft()
        reached[r]=1
        for p in G[r]:
            if reached[p]==1:
                continue
            parents[p]=r
            q.append(p)
    x=v[i]
    while(1):
        if parents[x]==-1:
            break
        s=min(x,parents[x])
        t=max(x,parents[x])
        root[i].add((s,t))
        x=parents[x]
#print(root)
ans=0
def cnt(x):
    ans=0
    for i in range(M):
        if x|(2**i)==x:
            ans+=1
    return ans
L=sorted(list(range(2**M)),key=lambda x:cnt(x))
S=[set() for i in range(2**M)]
for i in L:
    if i==0:
        continue
    if cnt(i)==1:
        #print(i,len(bin(i))-3)
        S[i]={j for j in root[len(bin(i))-3]}
        ans+=2**(N-len(S[i])-1)
        continue
    x=-1
    for j in range(M):
        if i|(2**j)==i:
            x=2**j
            break
    y=i^x
    S[i]=S[x]|S[y]
    ans+=(-1)**(cnt(i)+1)*2**(N-len(S[i])-1)
print(2**(N-1)-ans)



### FIXED CODE ###

'''
包除原理
すべての条件を満たしている
2^{N-1}から「どれかの条件を満たしていない」を引けば良い
i番目の条件を満たしていない確率はかんたんに計算できる
Sに属していいないやつが全て条件を満たしていない確率については
Sに対応する辺が全て白となる確率を考えれば良い
'''
from collections import deque
N=int(input())
G=[[] for i in range(N)]
a=[0 for i in range(N-1)]
b=[0 for i in range(N-1)]
edges=dict()
for i in range(N-1):
    a[i],b[i]=map(int,input().split())
    a[i]-=1;b[i]-=1
    G[a[i]].append(b[i])
    G[b[i]].append(a[i])
    edges[(min(a[i],b[i]),max(a[i],b[i]))]=i
M=int(input())
u=[0 for i in range(M)]
v=[0 for i in range(M)]
for i in range(M):
    u[i],v[i]=map(int,input().split())
    u[i]-=1;v[i]-=1
root=[0 for i in range(M)]
for i in range(M):
    q=deque([u[i]])
    parents=[-1 for i in range(N)]
    reached=[0 for i in range(N)]
    while(len(q)>0):
        r=q.popleft()
        reached[r]=1
        for p in G[r]:
            if reached[p]==1:
                continue
            parents[p]=r
            q.append(p)
    x=v[i]
    while(1):
        if parents[x]==-1:
            break
        s=min(x,parents[x])
        t=max(x,parents[x])
        root[i]+=2**edges[(s,t)]
        x=parents[x]
ans=0
def cnt(x):
    ans=0
    for i in range(M):
        if x|(2**i)==x:
            ans+=1
    return ans
q=deque([])
q.append(0)
S=[0 for i in range(2**M)]
reached=[0 for i in range(2**M)]
while(len(q)>0):
    i=q.popleft()
    for j in range(M):
        if i&(2**j)==0:
            S[i|(2**j)]=S[i]|root[j]
            if reached[i|(2**j)]==0:
                q.append(i|(2**j))
                reached[i|(2**j)]=1
    ans+=(-1)**(cnt(i))*2**(N-bin(S[i]).count("1")-1)
print(ans)
### BUGGY CODE ###

from collections import Counter

n = int(input())
A = [int(i) for i in input().split()]
C = Counter(A)
a, b, c = [C[i] for i in range(3, 0, -1)]

DP = [[[-1] * (a + b + c + 1) for i in range(a + b + 1)] for j in range(a + 1)]
DP[0][0][0] = 0

def dfs(i, j, k):
    if DP[i][j][k] != -1:
        return DP[i][j][k]
    
    DP[i][j][k] = 1
    if i > 0: DP[i][j][k] += i / n * dfs(i - 1, j + 1, k)
    if j > 0: DP[i][j][k] += j / n * dfs(i, j - 1, k + 1)
    if k > 0: DP[i][j][k] += k / n * dfs(i, j, k - 1)
    DP[i][j][k] *= n / (i + j + k)

    return DP[i][j][k]

print(dfs(a, b, c))

### FIXED CODE ###

from collections import Counter

n = int(input())
A = [int(i) for i in input().split()]
C = Counter(A)
a, b, c = [C[i] for i in range(3, 0, -1)]

DP = [[[-1] * (a + b + c + 1) for i in range(a + b + 1)] for j in range(a + 1)]
DP[0][0][0] = 0

for i in range(a + 1):
    for j in range(a + b - i + 1):
        for k in range(a + b + c - i - j + 1):
            if i == j == k == 0:
                continue
            DP[i][j][k] = 1
            if i > 0: DP[i][j][k] += i / n * DP[i - 1][j + 1][k]
            if j > 0: DP[i][j][k] += j / n * DP[i][j - 1][k + 1]
            if k > 0: DP[i][j][k] += k / n * DP[i][j][k - 1]
            DP[i][j][k] *= n / (i + j + k)

print(DP[a][b][c])
### BUGGY CODE ###

n,k=map(int,input().split())
xy=[]
x=[]
y=[]
ans=10**100
for i in range(n):
    tmp=[int(j) for j in input().split()]
    xy.append(tmp)
    x.append(tmp[0])
    y.append(tmp[1])

import itertools
for xx in itertools.combinations(x,2):
    for yy in itertools.combinations(y,2):
        p=0
        for i,j in xy:
            if min(xx)<=i and i<=max(xx) and min(yy)<=j and j<=max(yy):
                p+=1
        if p==k:
            ans=min(ans,(max(xx)-min(xx))*(max(yy)-min(yy)))
print(ans)



### FIXED CODE ###

n,k=map(int,input().split())
xy=[]
for i in range(n):
    tmp=[int(j) for j in input().split()]
    xy.append((tmp[0],tmp[1]))
from operator import itemgetter
xy.sort(key=itemgetter(1))
xy.sort(key=itemgetter(0))
xy=tuple(xy)
l=tuple(enumerate(xy))
ans=10**100
for i,(a,b) in l[:n-k+1]:
    for j,(c,d) in l[i+k-1:]:
        l1=sorted(y for x,y in xy[i:j+1])
        l2=l1[k-1:]
        for p,q in zip(l1,l2):
            if p<=b and q>=d:
                ans=min(ans,(c-a)*(q-p))
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import math


def gcd(a, b, c):
    temp = math.gcd(a, b)
    return math.gcd(temp, c)


def main():
    k = int(input())

    total = 0
    temp = {}
    for i in range(1, k + 1):
        for j in range(1, k + 1):
            for l in range(1, k + 1):

                join_str = "".join(sorted([str(i).zfill(3), str(j).zfill(3), str(l).zfill(3)]))
                gcd_val = temp.get(join_str, 0)
                if gcd_val == 0:
                    gcd_val = gcd(i, j, l)
                    temp[join_str] = gcd_val
                total += gcd_val

    return total


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

# -*- coding: utf-8 -*-
import math


def gcd(a, b, c):
    temp = math.gcd(a, b)
    return math.gcd(temp, c)


def main():
    k = int(input())

    total = 0
    temp = {}
    for i in range(1, k + 1):
        for j in range(1, k + 1):
            for l in range(1, k + 1):
                # join_str = "".join(sorted([str(i).zfill(3), str(j).zfill(3), str(l).zfill(3)]))
                # gcd_val = temp.get(join_str, 0)
                # if gcd_val == 0:
                gcd_val = gcd(i, j, l)
                total += gcd_val

    return total


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

#coding: utf-8

N = int(input())


s_list = []
for i in range(N):
    input_string = input()
    tmp_list = []
    for s in input_string:
        tmp_list.append(s)
    tmp_list.sort()
    sorted_string = ""
    for s in tmp_list:
        sorted_string = sorted_string + s
    s_list.append(sorted_string)


count = 0

while len(s_list) != 0:
    for i in range(1, len(s_list)):
        if s_list[0] == s_list[i]:
            count = count + 1

    del(s_list[0])
print(count)


### FIXED CODE ###

#coding: utf-8

from collections import Counter
N = int(input())

s_list = []
for i in range(N):
    input_string = list(input())
    input_string.sort()
    input_string = "".join(input_string)
    s_list.append(input_string)

s_list.sort()

list_counter = Counter(s_list)

count = 0
for key in list_counter.keys():
    tmp_count = list_counter[key]
    if tmp_count < 2:
        pass
    elif tmp_count == 2:
        count += 1
    else:
        permutations = tmp_count * (tmp_count - 1)
        combination = permutations/2
        count += int(combination)

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

try:
	while True:
		j = 0
		n = input()
		ans = [1] * (n + 1);
		ans[0] = ans[1] = 0;
		for i in range(3, n + 1, 2):
			if i * 2 > n:
				break
			if ans[i] != 0:
				for j in range(2 * i, n + 1, i):
					ans[j] = 0
		for k in range(2 * 2, n + 1, 2):
			ans[k] = 0
		print sum(ans)
except EOFError:
	pass

### FIXED CODE ###

def prime_count(n):
	j = 0
	ans = [1] * (n + 1)
	ans[0] = ans[1] = 0
	for i in xrange(3, n + 1, 2):
		if i * 2 > n:
			break
		if ans[i] != 0:
			for j in xrange(2 * i, n + 1, i):
				ans[j] = 0
	for k in xrange(2 * 2, n + 1, 2):
		ans[k] = 0
	print sum(ans)

try:
	while True:
		n = input()
		prime_count(n)
except EOFError:
	pass
### BUGGY CODE ###

n=int(input())
count=0
for i in range(1,n):
    wan=n//i
    for j in range(1,wan+1):
        charo=i*j
        if charo>=n:
            break
        else:
            count+=1
    else:
        continue
print(count)

### FIXED CODE ###

n=int(input())
count=0
for i in range(1,n):
    if i>=n/2:
        count+=1
        continue
    else:
        syou,amari=divmod(n,i)
        if amari==0:
            count+=syou-1
        else:
            count+=syou

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

from collections import deque
from heapq import heappush, heappop

N, M = map(int, input().split())
INF = 10 ** 12

vec = [[] for _ in range(N)]
for _ in range(M) :
    u, v = map(int, input().split())
    vec[u-1].append(v-1)

S, T = map(int, input().split())
S, T = S - 1, T - 1

visited = [False] * N
visited[S] = True
queue_ = [(0, S)]

while queue_ :
    cost, i = heappop(queue_)
    
    queue = deque([(0, i)])
    while queue :
        step, q = queue.popleft()
        if step == 2 : 
            for j in vec[q] :
                if j == T :
                    print(cost + 1)
                    exit()
                if not visited[j] :
                    visited[j] = True
                    heappush(queue_, (cost + 1, j))
        else :
            for j in vec[q] :
                queue.append((step + 1, j))

print(-1)
    

### FIXED CODE ###

from collections import deque

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

vec = [[] for _ in range(N)]
for _ in range(M) :
    u, v = map(int, input().split())
    vec[u-1].append(v-1)

S, T = map(int, input().split())
S, T = S - 1, T - 1

visited = [[False] * N for _ in range(3)]
visited[0][S] = True
queue = deque([(S, 0)])

while queue :
    q, cost = queue.popleft()
    p = (cost + 1) % 3
    for i in vec[q] :
        if p == 0 and i == T :
            print((cost + 1) // 3)
            exit()
        if not visited[p][i] :
            visited[p][i] = True
            queue.append((i, cost + 1))

print(-1)
### BUGGY CODE ###


MOD = 1000000007;

s = input()

n=len(s)

if n<1 or n>10**5:
	print ('Illegal')
	exit()

#a=[-1]*len(s)
#b=np.zeros((n+1, 13), dtype = 'int64')
#p=np.zeros(n,dtype=int)

b=[[0 for i in range(13)] for j in range(n+1)]
#p=[0]*n


x=1
#for i in reversed(range(n)):
#	p[i]=x%13
#	x=p[i]*10
	
for i in range(n):
	p=(10**(n-1-i))%13
	if(s[i]=="?"):
		c=-1
	else:
		c=int(s[i])
	if ( i== 0):
		if (c==-1):
			for j in range(10):
				b[0][(p*j)%13]=1
		else:
			b[0][(p*c)%13]=1
	else:
		if (c==-1):
			for j in range(10):
				for k in range(13):
					b[i][(k+p*j)%13]+=b[i-1][k]
		else:
			for k in range(13):
				b[i][(k+p*c)%13]+=b[i-1][k]

	for k in range(13):b[i][k]%=MOD
#	print (b[i])
#	print (b[i+1])

print (b[n-1][5])



### FIXED CODE ###

MOD = 1000000007;

s = [int(x) if x!="?" else -1 for x in input()]

n=len(s)

r=[0]*13

c=s[0]
if (c!=-1):
	r[c]=1
else:
	for i in range(10):r[i]=1

for i in range(1,n):
	dp=[0]*26
	for j in range(13):dp[j*10%13]+=(r[j]%MOD)
	dp[13:26]=dp[0:13]
	c=s[i]
	r=[0]*13
	if (c==-1):
		w=sum(dp[4:14])
		for j in range(13):
				r[j]+=w
				w=w+dp[j+1]-dp[4+j]
	else:
		for j in range(13):
			r[j]+=dp[13-c+j]
print (r[5]%MOD)
### BUGGY CODE ###



n=int(input())
a=list(map(int,input().split()))
ans=1
for i in range(len(a)):
    ans*=a[i]
if ans > 10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
limit=10**18
a.sort()
result=a[0]
for k in a[1:]:
    result*=k
    if result > limit:
        print(-1)
        exit()
print(result)
### BUGGY CODE ###

def main():
	s = int(input())
	a = list(map(int,input().split()))

	from operator import mul
	from functools import reduce
	
	def cmb(n,r):
		r = min(n-r,r)
		if r == 0: return 1
		over = reduce(mul, range(n, n - r, -1))
		under = reduce(mul, range(1,r + 1))
		return over // under

	import collections
	for i in range(s):
		c = collections.Counter(a[0:i] + a[i+1:s])
		Set = set(a[0:i] + a[i+1:s])
		ans = 0
		for t in Set:
			if c[t] > 1:
				ans += cmb(int(c[t]),2)
		print(ans)

if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	import collections
	s = int(input())
	a = list(map(int,input().split()))
	ac = collections.Counter(a)
	ans = 0
	for i in set(ac):
		at = ac[i]
		ans += (at * (at-1))/2
	for t in a:
		ans_print = ans -((ac[t] * (ac[t] -1))/2) + (((ac[t]-1) * ((ac[t]-1)-1))/2)
		print(int(ans_print))
if __name__ == '__main__':
	main()
### BUGGY CODE ###

n, k = map(int, input().split())
s = input()
l = [0] * (k * 2 + 1)
c = '1'
p = 0
ret = 0
for i in range(len(s)):
    if s[i] != c:
        ret = max(ret, i - l[p])
        l.append(i)
        if c == '1':
            l = l[2:]
        c = s[i]
ret = max(ret, n - l[p])
print(ret)


### FIXED CODE ###

N, K = [int(s) for s in input().split(' ')]
S = input()
ss = []
ssc = []
subs = S[0]
for s in S[1:]:
    if subs[-1] != s:
        ss.append(subs)
        ssc.append(len(subs))
        subs = s
        continue
    subs += s
ss.append(subs)
ssc.append(len(subs))
suma = [0]
for sc in ssc:
    suma.append(suma[-1] + sc)

#print(ss)
max_c = 0
for i in range(len(ss)):
    k = (K * 2 + 1) if ss[i][0] == '1' else (K * 2)
    l = i
    r = min(i + k, len(ss))
    c = suma[r] - suma[l]
    max_c = max(max_c, c)

print(max_c)
### BUGGY CODE ###

def solve():
    N, HP  = map(int, input().split())
    score = 0

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

    #最後まで使う刀保存
    lastf = max(f)
    lastid = f.index(lastf)
    lastn = n[lastid]


    for i in range(len(n)):
        mn = max(n)
        id = n.index(mn)
        if lastf < mn:
            HP -= mn
            n.pop(id)
            score += 1
            if HP <= 0:
                return score
        else:
            break

    score += -(-HP // lastf)
    return score


print(solve())


### FIXED CODE ###

def solve():
    N, HP  = map(int, input().split())
    score = 0

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

    #最後まで使う刀保存
    lastf = max(f)
    lastid = f.index(lastf)
    lastn = n[lastid]
    n.sort(reverse = True)


    for i in range(len(n)):
        mn = n[0]
        id = 0
        if lastf < mn:
            HP -= mn
            n.pop(id)
            score += 1
            if HP <= 0:
                return score
        else:
            break

    score += -(-HP // lastf)
    return score


print(solve())
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
a_ = sorted(a)
if len(a)==2:
    print(a_[1],a_[0])
    exit()
a = sorted(a)[::-1]
import bisect
import math
def combinations_count(n,r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))
ret = 0
for i in range(n//2):
    k = bisect.bisect_left(a_,a[i]//2)
    kl = combinations_count(a[i],a_[k])
    kr = combinations_count(a[i],a_[k+1])
    if kl>kr:
        cmb = kl
        l = [a[i],a_[k]]
    else:
        cmb = kr
        l = [a[i],a_[k+1]]
    if ret<cmb:
        ans = l
        ret = cmb
print(ans[0],ans[1])

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a_ = sorted(a)
if len(a)==2:
    print(a_[1],a_[0])
    exit()
a = a_[::-1]
k = 10**9
for i in range(1,n):
    if k>abs(a[0]/2-a[i]):
        k=abs(a[0]/2-a[i])
        ans = [a[0],a[i]]
print(ans[0],ans[1])
### BUGGY CODE ###

N = int(input())
res = 0
for i in range(N):
    res += i
print(res)


### FIXED CODE ###

N = int(input())
res = int(N * (N - 1)//2)
print(res)
### BUGGY CODE ###

inputNumbers=input()
N=int(inputNumbers.split(" ")[0])
X=int(inputNumbers.split(" ")[1])
Y=int(inputNumbers.split(" ")[2])

result = []
for k in range(1,N):
    result.append(0)

allBranchLength=[]

for i in range(1, N+1):
    for j in range(i+1,N+1):

        if i <= X:
            if j <= X:
                length = j - i
                allBranchLength.append([str(i) + "," + str(j), length])

            if j > X and j < Y:
                length = X - i + min(j-X, Y-j+1)
                allBranchLength.append([str(i) + "," + str(j), length])

            if j >= Y:
                length = (X - i) + 1 + (j - Y)
                allBranchLength.append([str(i) + "," + str(j), length])

        if i > X and i < Y:
            if j > X and j < Y:
                length = min( (i - X) + 1 + (Y - j) , j - i )
                allBranchLength.append([str(i) + "," + str(j), length])

            if j >= Y:
                length = min( (i - X) + 1 + (j - Y) , j - i )
                allBranchLength.append([str(i) + "," + str(j), length])
                
        if i >= Y:
            if j >= Y:
                length = j - i
                allBranchLength.append([str(i) + "," + str(j), length])


for i in range(len(allBranchLength)):
    result[allBranchLength[i][1] - 1] += 1

for i in range(len(result)):
    print(result[i])



### FIXED CODE ###

inputNumbers=input()
N=int(inputNumbers.split(" ")[0])
X=int(inputNumbers.split(" ")[1])
Y=int(inputNumbers.split(" ")[2])

result = []
for k in range(1,N):
    result.append(0)

allBranchLength=[]

for i in range(1, N+1):
    for j in range(i+1,N+1):

        if i <= X:
            if j <= X:
                length = j - i
                result[length - 1] += 1

            if j > X and j < Y:
                length = X - i + min(j-X, Y-j+1)
                result[length - 1] += 1

            if j >= Y:
                length = (X - i) + 1 + (j - Y)
                result[length - 1] += 1

        if i > X and i < Y:
            if j > X and j < Y:
                length = min( (i - X) + 1 + (Y - j) , j - i )
                result[length - 1] += 1

            if j >= Y:
                length = min( (i - X) + 1 + (j - Y) , j - i )
                result[length - 1] += 1
                
        if i >= Y:
            if j >= Y:
                length = j - i
                result[length - 1] += 1


#for i in range(len(allBranchLength)):
#    result[allBranchLength[i][1] - 1] += 1

for i in range(len(result)):
    print(result[i])
### BUGGY CODE ###

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

# １からNまでの値をもつサイコロを振ったときの期待値
def ex(x:int):
    return (x*(x+1)/2)/x

wa=0
saidai_p=0
for i in range(len(p)-(k-1)):
    if sum(p[i:i+k]) >= wa:
        wa=sum(p[i:i+k])
        saidai_p=i

kitaichi_goukei=0
for i in range(k):
    kitaichi_goukei+=ex(p[saidai_p+i])

print (kitaichi_goukei)

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
ex = [1/2*(i+1) for i in p]
total = [0]

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

ans = 0
for i in range(N+1-K):
    tmp = total[i+K] - total[i]
    if ans < tmp:
        ans = tmp

print (ans)