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

from collections import deque

N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
px = [list(map(int, input().split())) for _ in range(Q)]

#print(N, Q, ab, px)
class Tree:
    def __init__(self):
        # n番目のノードの値
        self.value = [0 for _ in range(N+1)]
        # n番目の, 親から含めたノードの値
        self.total_value = [0 for _ in range(N+1)]
        # n番目のノードの一つ下の辺リスト
        self.edge = [[] for _ in range(N+1)]

    def build(self, a, b):
        #print("Tree build ", a, " ", b)
        self.edge[a].append(b)
        self.edge[b].append(a)


    def add(self, p, x):
        # 木の値を更新していく
        self.value[p] += x

    # 値を親から子に向かって更新する
    def reflesh(self):
        stack = deque()
        stack.append((1, 0))
        while stack:
            st = stack.pop()
            node, parent = st[0], st[1]
            children = self.edge[node]
            for child in children:
                if child == parent:
                    continue
                #print("c n", child, node)
                self.value[child] += self.value[node]
                stack.append((child, node))


tree = Tree()
for ab_ in ab:
    tree.build(*ab_)

for px_ in px:
    tree.add(*px_)

tree.reflesh()
#print(" ".join([str(tree.value[x]) for x in range(1,N+1)]))
print(" ".join([str(tree.value[x]) for x in range(1,N+1)]))
#for i in range(1,N+1):
    #print(tree.edge[i], end=",")
#    print(tree.value[i], end=" ")

### FIXED CODE ###

from collections import deque

N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
px = [list(map(int, input().split())) for _ in range(Q)]

#print(N, Q, ab, px)
class Tree:
    def __init__(self):
        # n番目のノードの値
        self.value = [0 for _ in range(N+1)]
        # n番目の, 親から含めたノードの値
        self.total_value = [0 for _ in range(N+1)]
        # n番目のノードの一つ下の辺リスト
        self.edge = [[] for _ in range(N+1)]

    def build(self, a, b):
        #print("Tree build ", a, " ", b)
        self.edge[a].append(b)
        self.edge[b].append(a)


    def add(self, p, x):
        # 木の値を更新していく
        self.value[p] += x

    # 値を親から子に向かって更新する
    def reflesh(self):
        stack = deque()
        stack.append((1, 0))
        while stack:
            st = stack.pop()
            node, parent = st[0], st[1]
            children = self.edge[node]
            for child in children:
                if child == parent:
                    continue
                #print("c n", child, node)
                self.value[child] += self.value[node]
                stack.append((child, node))


tree = Tree()
for ab_ in ab:
    tree.build(*ab_)

for px_ in px:
    tree.add(*px_)

tree.reflesh()
#print(" ".join([str(tree.value[x]) for x in range(1,N+1)]))
print(" ".join([str(tree.value[x]) for x in range(1,N+1)]))
#for i in range(1,N+1):
    #print(tree.edge[i], end=",")
#    print(tree.value[i], end=" ")
### BUGGY CODE ###

n,k = map(int,input().split())
A = list(map(int,input().split()))
B = []
b = 1
ans = 1
while ans:
  a = b
  b = A[a-1]
  B.append(b)
  if len(B) == k:
    ans = 0
print(B[k-1])


### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
pos = 0
visit = [0] * N
move = []
roop = []
while visit[pos]!=2:
    if visit[pos]==0:
        move.append(pos)
    else:
        roop.append(pos)
    visit[pos] += 1
    pos = A[pos] - 1
if len(move)>K:
    print(move[K]+1)
else:
    print(roop[(K-(len(move)-len(roop)))%len(roop)]+1)
### BUGGY CODE ###

import collections
N, P = map(int, input().split())

i=2
a=[]
ans=1
while(True):
    if(P%i==0):
        P=P//i
        a.append(i)
    else:
        break

i=3 
while(True):
    if(P%i==0):
        P=P//i
        a.append(i)
        c=1
    else:
        i+=2
        c=0

    if((P<i**N)&(c==0)):
        break

dct=collections.Counter(a)

li=dct.items()

for tt in li:
    if tt[1]>=N:
        ans*=tt[0]**(tt[1]//N)

print(ans)    

    

### FIXED CODE ###

import collections

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

a=[]
while p % 2 == 0:
  p //= 2
  a.append(2)
f = 3
while f * f <= p:
  if p % f == 0:
    a.append(f)
    p //= f
  else:
    f += 2
if p != 1:
  a.append(p)

dct=collections.Counter(a)

ans=1

li=dct.items()

for tt in li:
  if tt[1]//n>=1:
    ans*=tt[0]**(tt[1]//n)
print(ans)
### BUGGY CODE ###

import sys
def b(bs, cs):
    #print(bs, xs[len(bs):])
    d = set()
    bl, cl = len(bs), len(cs)
    bi, ci = 0, 0
    while True:
      if bs[bi] > cs[ci]:
        bi += 1
        bs.append(cs[ci])
        del cs[ci]
      else:
        ci += 1
      if bi == bl or ci == len(cs):
        break
    if len(bs) != 2 * bl:
      print("No")
      sys.exit()
    return bs, cs

n=int(input())
xs = sorted(list(map(int,input().split())))[::-1]
bs, cs = xs[:1], xs[1:]
for _ in range(n):
    bs, cs = b(sorted(bs)[::-1], cs)

print("Yes")

### FIXED CODE ###

import sys
def b(bs, cs):
    d = set()
    bl, cl = len(bs), len(cs)
    bi, ci = 0, 0
    ncs = []
    while True:
      if bs[bi] > cs[ci]:
        bs.append(cs[ci])
        bi += 1
      else:
        ncs.append(cs[ci])
      ci += 1
      if bi == bl or ci == cl:
        break
    if len(bs) != 2 * bl:
      print("No")
      sys.exit()
    return bs, ncs + cs[ci:]

n=int(input())
xs = sorted(list(map(int,input().split())))[::-1]
bs, cs = xs[:1], xs[1:]
for _ in range(n):
    bs, cs = b(sorted(bs)[::-1], cs)

print("Yes")
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
X = sorted(x)

for i in x:
    I = X.index(i)
    l,r = I, n-I
    if I+1 <= n//2:
       print(X[I+n//2-l])
    else:
        print(X[n//2-1])

### FIXED CODE ###

import statistics
n = int(input())-1
a = list(map(int, input().split()))
N = sorted([[x,y] for y, x in enumerate(a)])

ans = [0] * (n+1)
for i in range(n+1):
    if i < n//2+1: 
        ans[N[i][1]] = N[n//2+1][0]
    else: ans[N[i][1]] = N[n//2][0]
for x in ans: print(x)
### BUGGY CODE ###

N,Q = list(map(int, input().split()))
S = list(input())
L = []
for _ in range(Q):
    temp = list(map(int, input().split()))
    L.append(temp)
for i in range(Q):
    ans = 0
    r,l = L[i]
    for j in range(r-1,l-1):
        if S[j] == "A" and S[j + 1] == "C":
            ans += 1
    print(ans)

### FIXED CODE ###

def main():
    import sys
    import re
    input = sys.stdin.readline
    N,Q = list(map(int, input().split()))
    S = list(input())
    L = []
    for _ in range(Q):
        temp = list(map(int, input().split()))
        L.append(temp)
    dp = [0] * N
    for i in range(1,N):
        if S[i] == "C" and S[i-1] == "A":
            dp[i] = dp[i-1] + 1
        else:
            dp[i] = dp[i-1]
    for j in range(Q):
        l,r = L[j]
        print(dp[r-1] - dp[l-1])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def solve(k):
  def gcd(a, b):
    if a < b:
      a,b = b,a
    while b:
      a, b = b, a%b
    return a

  ans = 0
  for a in range(1, k+1):
    for b in range(1, k+1):
      for c in range(1, k+1):
        ans += gcd(gcd(a,b),c)
  return ans

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', 'i8(i8)')(solve)
    cc.compile()

if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    #from my_module import solve
    print(solve(int(input())))

### FIXED CODE ###

import numba

@numba.njit(numba.i8(numba.i8), cache=True)
def solve(k):
  def gcd(a, b):
    if a < b:
      a,b = b,a
    while b:
      a, b = b, a%b
    return a

  ans = 0
  for a in range(1, k+1):
    for b in range(1, k+1):
      for c in range(1, k+1):
        ans += gcd(gcd(a,b),c)
  return ans

print(solve(int(input())))
### BUGGY CODE ###

from enum import Enum
from queue import Queue
import collections
import numpy as np


import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

L,R = map(int,input().split())
min = BIG_NUM
for i in range(L,R+1):
    for j in range(i+1,R+1):
        tmp = (i*j)%2019
        if tmp < min:
            min = tmp
        if min == 0:
            break

print(min)


### FIXED CODE ###

from enum import Enum
from queue import Queue
import collections
import numpy as np


import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

L,R = map(int,input().split())
min = BIG_NUM
if (R/2019 - L/2019)>=1.0:
    print(0)
else:
    for i in range(L,R+1):
        for j in range(i+1,R+1):
            tmp = (i*j)%2019
            if tmp < min:
                min = tmp
            if min == 0:
                break
    print(min)
### BUGGY CODE ###

import math

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()
    return divisors

n = int(input())

l = make_divisors(n)
ans = n-1
for i in range(0, len(l)):
  for j in range(0, len(l)):
    a = l[i]
    b = l[j]
    if a * b == n:
      ans = min(ans, (a+b-2))

print(ans)


### FIXED CODE ###

import math

n = int(input())
ans = n-1

for i in range(1, math.floor(math.sqrt(n))+1):
  if n % i == 0:
    ans = min(ans, (i+(n/i)-2))
      
print(int(ans))
### BUGGY CODE ###

import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NNN = (10**5)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

import sys
from collections import defaultdict
input = sys.stdin.readline

N = int(input())
G = [[] for _ in range(N+1)]
for v in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

v2i = [0 for _ in range(N+1)]
def itt(v, p):
    cn = 0
    ms = []
    for u in G[v]:
        if u == p:
            continue
        un = itt(u, v)
        ms.append(un)
        cn += un
    if p != None:
        ms.append(N-1-cn)
    v2i[v] = ms
    return cn+1
itt(1, None)
r = 0
for v in range(1, N+1):
    ff = v2i[v]
    for f in ff:
        r += power(2, f) - 1
print((div(N*power(2,N-1)-N-r, power(2, N)))%mod)


### FIXED CODE ###

import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))

import sys
input = sys.stdin.readline


N = int(input())

d2 = [1]
inverse = [0, 1]
for _ in range(N):
    d2.append(2*d2[-1]%mod)
for i in range( 2,  10):
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )

G = [[] for _ in range(N+1)]
for v in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

v2i = [0 for _ in range(N+1)]
def itt(v, p):
    cn = 0
    ms = []
    for u in G[v]:
        if u == p:
            continue
        un = itt(u, v)
        ms.append(un)
        cn += un
    if p != None:
        ms.append(N-1-cn)
    v2i[v] = ms
    return cn+1
itt(1, None)
r = 0
for v in range(1, N+1):
    ff = v2i[v]
    for f in ff:
        r += d2[f] - 1 % mod
r = N*d2[N-1]-N-r
for _ in range(N):
    r = r*500000004 % mod
print(r)
### BUGGY CODE ###

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

dp = [10**10] * N

dp[0] = 0
for i in range(1,N):
    for j in range(1,K+1):
        if i - j >= 0:
            dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]))
        else:
            break
print(dp[N-1])

### FIXED CODE ###

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

dp = [10**10] * N

dp[0] = 0
for i in range(N):
    for k in range(1, K+1):
        if i+k < N:
            dp[i+k] = min(dp[i+k], dp[i] + abs(h[i]-h[i+k]))
        else:
            break
print(dp[N-1])
### BUGGY CODE ###

s = input()
origin = len(s)
le = 0
while len(s) != le:
    le = len(s)
    s = s.replace('10','').replace('01','')
    
print(origin-len(s))

### FIXED CODE ###

s = input()
cnt_one = s.count('1')
cnt_zero = len(s) - cnt_one
print(min(cnt_zero, cnt_one)*2)
### BUGGY CODE ###

import itertools

N,M,R = map(int,input().split())
r = list(map(lambda x:int(x)-1,input().split()))
ABC = [list(map(int,input().split())) for _ in range(M)]
INF = 10**7
d = [[INF]*N for _ in range(N)]

for A,B,C in ABC:
    d[A-1][B-1] = C
    d[B-1][A-1] = C
for k in range(N):
    for i in range(N):
        for j in range(i+1,N):
            d[i][j] = min(d[i][j],d[i][k]+d[k][j])
            d[j][i] = d[i][j]
ans = INF * M
for r in itertools.permutations(r):
    S = 0
    for i,ri in enumerate(r[:-1]):
        S += d[ri][r[i+1]]
    ans = min(ans,S)
print(ans)

### FIXED CODE ###

import itertools

N,M,R = map(int,input().split())
r = list(map(lambda x:int(x)-1,input().split()))
ABC = [list(map(int,input().split())) for _ in range(M)]
INF = 10**7
d = [[INF]*N for _ in range(N)]

for A,B,C in ABC:
    d[A-1][B-1] = C
    d[B-1][A-1] = C
for k in range(N):
    for i in range(N):
        for j in range(i+1,N):
            d[i][j] = min(d[i][j],d[i][k]+d[k][j])
            d[j][i] = d[i][j]
ans = INF * M
for r in itertools.permutations(r):
    S = 0
    for i,ri in enumerate(r[:-1]):
        S += d[ri][r[i+1]]
    ans = min(ans,S)
print(ans)
### BUGGY CODE ###

import fractions
n = int(input())
l = list(map(int,input().split()))
if n == 1:
    print(1)
    exit()
ans = l[0]*l[1]/fractions.gcd(l[0],l[1])
for i in range(2,n):
    ans = ans*l[i]/fractions.gcd(ans,l[i])

mod = 10**9+7
a = 0
for i in range(n):
    a += ans//l[i]
    a %= mod
print(int(a%mod))


### FIXED CODE ###

import fractions
n = int(input())
l = list(map(int,input().split()))
if n == 1:
    print(1)
    exit()

def lcm(a,b):
    return a*b//fractions.gcd(a,b)
ans = l[0]
for i in range(1,n):
    ans = lcm(ans,l[i])
    

mod = 10**9+7
a = 0
for i in range(n):
    a += ans//l[i]
    
print(a%mod)
### BUGGY CODE ###

n= int(input())
l = list(map(int, input().split()))
print(*[l.count(i) for i in range(1,n+1)],sep='\n')

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = [0]*n
for i, a in enumerate(a):
     ans[a-1] += 1
print(*ans, sep="\n")
### BUGGY CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

s = ns()
n = len(s)
a = []
b = 2019
for i in range(10000):
    b+=2019
    c = str(b)
    if '0' not in c:
        a.append(c)

ans = 0
for i in range(n):
    k = [4,5,6,7,8]
    for j in k:
        if i+j <= n:
            ss = s[i:i+j]
            if ss in a:
                ans += 1

print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

from collections import defaultdict

s = ns()
d = defaultdict(int)
d[0] += 1
k = 1
n = 0
for i in range(len(s))[::-1]:
    n += int(s[i])*k%2019
    n%=2019
    d[n] += 1
    k = (k*10)%2019

ans = 0

for j in d.values():
    if j > 1:
        ans += j*(j-1)//2

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

n = int(input())
plist = list(map(int,input().split()))


counter = 0

for i in range(len(plist)):
    islow = True
    for j in range(plist.index(plist[i])):
        if not islow:
            break
        elif plist[i] <= plist[j]:
            continue
        else:
            islow = False
    if islow:
        counter += 1

print(counter)        

### FIXED CODE ###

n = int(input())
plist = list(map(int,input().split()))

islow = True
counter = 0
min = 0

for i in range(len(plist)):
    islow = True
    if i == 0:
        counter += 1
        min = plist[i]
        current_min = i
    elif min > plist[i]:
        counter += 1
        min = plist[i]
        current_min = i
        
print(counter)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)

f_inf = sys.maxsize

N, M, P = map(int, input().split())
ABC_d = {}
for m in range(M):
    A, B, C = map(int, input().split())
    if A in ABC_d:
        ABC_d[A].append([B, C - P])
    else:
        ABC_d[A] = [[B, C - P]]

cost = [-f_inf] * N
cost[0] = 0

max_num_sum = (N * (N + 1)) // 2

def solve(pos, cnt, num_sum):
    global cost

    if not(pos in ABC_d): return
    if cnt > N or num_sum > max_num_sum:
        cost[pos-1] = f_inf;

    for B, C in ABC_d[pos]:
        if cost[B - 1] == f_inf or cost[B - 1] >= cost[pos - 1] + C:
            pass
        elif cost[pos-1] == f_inf:
            cost[B-1] = f_inf
            solve(B, cnt + 1, num_sum + B)
        elif cost[B - 1] < cost[pos - 1] + C:
            cost[B - 1] = cost[pos - 1] + C
            solve(B, cnt + 1, num_sum + B)


solve(1, 1, 1)

if (cost[-1] == sys.maxsize):
    print (-1)
else:
    print (max(0, int(cost[-1])))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)

f_inf = sys.maxsize

N, M, P = map(int, input().split())
ABC_d = {}
for m in range(M):
    A, B, C = map(int, input().split())
    if A in ABC_d:
        ABC_d[A].append([B, C - P])
    else:
        ABC_d[A] = [[B, C - P]]

cost = [-f_inf] * N
cost[0] = 0

def solve(pos, cnt):
    global cost

    if not(pos in ABC_d): return
    if cnt > N: cost[pos-1] = f_inf;

    for B, C in ABC_d[pos]:
        if cost[B - 1] == f_inf or cost[B - 1] >= cost[pos - 1] + C:
            pass
        elif cost[pos-1] == f_inf:
            cost[B-1] = f_inf
            solve(B, cnt + 1)
        elif cost[B - 1] < cost[pos - 1] + C:
            cost[B - 1] = cost[pos - 1] + C
            solve(B, cnt + 1)

solve(1, 1)

if (cost[-1] == sys.maxsize):
    print (-1)
else:
    print (max(0, int(cost[-1])))
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = collections.defaultdict(list)
    for l,r,d in a:
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        if b[i] != False:
            if c == False:
                return True
            return b[i] == c
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if not g(r,c+d):
                return False
        return True

    for i in range(n):
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())





### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    e = [[] for _ in range(n)]
    if m > 0:
        for _ in range(m):
            l,r,d = LI()
            e[l-1].append((r-1,d))
            e[r-1].append((l-1,-d))

    b = [None] * n

    for i in range(n):
        if not b[i] is None:
            continue
        b[i] = 0
        q = [i]
        qi = 0
        nq = []
        while True:
            if len(q) == qi:
                if not nq:
                    break
                q = nq
                qi = 0
                nq = []
            j = q[qi]
            qi += 1
            c = b[j]
            for r,d in e[j]:
                if b[r] is None:
                    b[r] = c+d
                    nq.append(r)
                else:
                    if b[r] != c+d:
                        return 'No'

    return 'Yes'


print(main())
### BUGGY CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
index = 0
num = 0
ans = 0
for i in range(N-K+1):
    tmp = sum(p[i:i+K])
    if num < tmp:
        index = i
        num = tmp
for i in range(index, index+K):
    ans += 0.5*p[i]*(p[i]+1)/p[i]
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
ans = 0
dp = [0]*N
dp[0] = sum(p[:K])
for i in range(N-K):
    dp[i+1] = dp[i] - p[i] + p[i+K]
index = dp.index(max(dp))
for i in range(index, index+K):
    ans += 0.5*p[i]*(p[i]+1)/p[i]
print(ans)
### BUGGY CODE ###

n = int(input())
pref = []
suff = []

for i in range(n):
	s = input()
	pos = neg = 0
	for ch in s:
		if ch == '(':
			pos += 1
		elif pos == 0:
			neg += 1
		else:
			pos -= 1
	if pos >= neg:
		pref.append([pos, neg])
	else:
		suff.append([pos, neg])


pref.sort(key=lambda x: x[1])
suff.sort(key=lambda x: x[0], reverse=True)

totPos = 0

for pos, neg in pref:
	if neg > totPos:
		print("No")
		exit(0)
	totPos -= neg
	totPos += pos

for pos, neg in suff:
	if neg > totPos:
		print("No")
		exit(0)
	totPos -= neg
	totPos += pos

if totPos != 0:
	print("No")
else:
	print("Yes")


### FIXED CODE ###

n = int(input())
ara = [input() for _ in range(n)]
pref = []
suff = []

for s in ara:
	pos = neg = 0
	for ch in s:
		if ch == '(':
			pos += 1
		elif pos == 0:
			neg += 1
		else:
			pos -= 1
	if pos >= neg:
		pref.append([pos, neg])
	else:
		suff.append([pos, neg])


pref.sort(key=lambda x: x[1])
suff.sort(key=lambda x: x[0], reverse=True)

totPos = 0

ara = pref + suff

for pos, neg in ara:
	if neg > totPos:
		print("No")
		exit(0)
	totPos -= neg
	totPos += pos


if totPos != 0:
	print("No")
else:
	print("Yes")
### BUGGY CODE ###

def check_all_distinct(A):
  already_seen_chars = list()
  for character in A:
    if character not in already_seen_chars:
      already_seen_chars.append(character)
    else: return "NO"
  return "YES"


if __name__ == "__main__":
  N = int(input())
  A = input().split()
  print(check_all_distinct(A))

### FIXED CODE ###

N = int(input())
A = input().split()
if len(A) != len(set(A)):
  print("NO")
else:
  print("YES")
### BUGGY CODE ###

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

if n <= k:
    print(0)

    exit()

H = sorted(h)

for i in range(k):
    H.remove(H[-1])

print(sum(H))

### FIXED CODE ###

n, k = map(int, input().split())
H = sorted(list(map(int, input().split())), reverse=True)#reverse=Trueは逆順
# print(H)
# print(H[k:])#後ろからkこぶんとる
print(sum(H[k:]))