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

N,M,K=map(int,input().split())
G=[]
F=[set([]) for _ in range(N)]
B=[set([]) for _ in range(N)]
for _ in range(M):
  a,b=map(int,input().split())
  F[a-1].add(b)
  F[b-1].add(a)
  p,i=True,0
  for g in G:
    if (a in g or b in g) and p:
      g|={a,b}
      j=i
      p=False
    elif a in g or b in g:
      G[j]|=g|{a,b}
      G.remove(g)
    i+=1
  if p:
    G.append({a,b})
for _ in range(K):
  a,b=map(int,input().split())
  B[a-1].add(b)
  B[b-1].add(a)
ans=[0]*N
for g in G:
  for i in g:
    ans[i-1]=len(g-F[i-1]-B[i-1]-{i})
print(*ans)


### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1]*n
        self.rank = [0]*n

    def find(self, x):
        if self.par[x-1] < 0:
            return x
        else:
            self.par[x-1] = self.find(self.par[x-1])
            return self.par[x-1]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        elif self.rank[x-1] > self.rank[y-1]:
            self.par[x-1] += self.par[y-1]
            self.par[y-1] = x
        else:
            self.par[y-1] += self.par[x-1]
            self.par[x-1] = y
            if self.rank[x-1] == self.rank[y-1]:
                self.rank[y-1] += 1

    def same(self, x, y):
        return self.find(x)==self.find(y)

    def count(self, x):
        return -self.par[self.find(x)-1]

from collections import deque

N,M,K=map(int,input().split())
U=UnionFind(N)
q=deque([])
for _ in range(M):
  a,b=map(int,input().split())
  U.union(a,b)
  deque.append(q,(a,b))
G=[set([]) for _ in range(N)]
for _ in range(M):
  a,b=deque.pop(q)
  if U.same(a,b):
    G[a-1].add(b)
    G[b-1].add(a)
for _ in range(K):
  a,b=map(int,input().split())
  if U.same(a,b):
    G[a-1].add(b)
    G[b-1].add(a)
ans=[0]*N
for i in range(1,N+1):
  ans[i-1]=U.count(i)-len(G[i-1])-1
print(*ans)
### BUGGY CODE ###

from sys import exit
import copy
import random
import time 
#import numpy as np
#from collections import deque


d, = map(int, input().split())
c= list(map(int, input().split()))
s=[list(map(int, input().split())) for _ in range(d)]
#  t=[int(input()) for _ in range(d)]


def calc_score(arr):
    ans=0
    last=[0 for _ in range(26)]
    for i in range(d):
        ans+=s[i][arr[i]-1]
        for l in range(26):
            ans-=c[l]*(i+1-last[l])
        last[arr[i]-1]=i+1
    return ans


t0=time.time()
TL=2
score=float("inf")*(-1)
while time.time()-t0<TL:
    sche_tmp=[random.randrange(1,27) for _ in range(365)]
    s_tmp=calc_score(sche_tmp)
    print(s_tmp)
    if s_tmp>=score:
        score=s_tmp
        sche=copy.copy(sche_tmp)


for i in sche:
    print(i)






### FIXED CODE ###

from sys import exit
import copy
#import numpy as np
#from collections import deque


d, = map(int, input().split())
c= list(map(int, input().split()))
s=[list(map(int, input().split())) for _ in range(d)]
#  t=[int(input()) for _ in range(d)]

sche=[0 for _ in range(d)]
last=[0 for _ in range(26)]

score=0
for day in range(1,d+1):
    idx=day-1
    d_tmp=0
    i_tmp=0
    for t in range(26):    
        delta=0
        l_tmp=copy.copy(last)
        delta+=s[idx][t]
        l_tmp[t]=day
        for l in range(26):
            delta-=c[l]*(day-l_tmp[l])
        if delta>=d_tmp:
            d_tmp=delta
            i_tmp=t
    sche[idx]=i_tmp
    score+=d_tmp
    last[i_tmp]=day
    # print(score)
    print(i_tmp+1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)

    weights = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        weights[p-1] += x

    ans = [0] * N
    ans[0] = weights[0]
    visited = [False] * N
    def f(a, node):
        visited[node] = True
        for nt in G[node]:
            if visited[nt]:
                continue
            b = a + weights[nt]
            ans[nt] = b
            f(b, nt)
        return  0

    f(weights[0], 0)
    return ' '.join(map(str, ans))


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


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    G = [set() for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        G[a-1].add(b-1)
        G[b-1].add(a-1)

    weights = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        weights[p-1] += x

    ans = [0] * N
    ans[0] = weights[0]
    visited = [False] * N
    def f(a, node):
        visited[node] = True
        for nt in G[node]:
            if visited[nt]:
                continue
            b = a + weights[nt]
            ans[nt] = b
            f(b, nt)
        return  0

    f(weights[0], 0)
    return ' '.join(map(str, ans))


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

import math
ans = 0
c = 0
K = int(input())
for i in range(1,K+1):
    for j in range(1,K+1):
        for m in range(1,K+1):
            c = math.gcd(i,j)
            ans += math.gcd(c,m) 
print(ans)
            

### FIXED CODE ###

import math
ans = 0
c = 0
K = int(input())
for i in range(1,K+1):
    for j in range(1,K+1):
        c = math.gcd(i,j)
        for m in range(1,K+1):
            ans += math.gcd(c,m) 
print(ans)
### BUGGY CODE ###

N = int(input())
n = [i + 1 for i in range(N)]
print(sum(n) - max(n))

### FIXED CODE ###

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

import sys
sys.setrecursionlimit(10**6)

N, Q = map(int, input().split())
link = [[] for _ in range(N)]
a = [0] * (N-1)
b = [0] * (N-1)
for i in range(N-1):
    a[i], b[i] = map(int, input().split())

cost = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    cost[p-1] += x

for i in range(N-1):
    link[a[i]-1].append([b[i]-1, cost[i]])

nums = [0] * N
def dfs(v, c):
    for nv in link[v]:
        nums[nv[0]] += c + cost[nv[0]]
        dfs(nv[0], c + cost[nv[0]])
    return

nums[0] = cost[0]
dfs(0, cost[0])

print(*nums)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(v, p):
    for u in link[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)

N, Q = map(int, input().split())
link = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    link[a-1].append(b-1)
    link[b-1].append(a-1)

ans = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x

dfs(0, -1)

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

s = [int(e) for e in input().split()]
x = int(s[0])
y = int(s[1])
a = int(s[2])
b = int(s[3])
c = int(s[4])
a_l = [int(e) for e in input().split()]
b_l = [int(e) for e in input().split()]
c_l = [int(e) for e in input().split()]

a_l.sort(reverse=True)
b_l.sort(reverse=True)
c_l.sort(reverse=True)

apple = []
a_app=a_l[0:x]
b_app=b_l[0:y]

for c_app in c_l:
    if a_app[-1]<b_app[-1]:
        if a_app[-1]<c_app:
            a_app[-1]=c_app
    else:
        if b_app[-1]<c_app:
            b_app[-1]=c_app
    a_l.sort(reverse=True)
    b_l.sort(reverse=True)

apple_count=sum(a_app)+sum(b_app)

print(apple_count)

### FIXED CODE ###

import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
x, y, a, b, c = nm()
p = nl()
q = nl()
r = nl()
p.sort()
q.sort()
l = p[-x:] + q[-y:]
l.sort()
r.sort()
for i in range(c):
    if l[i] < r[-1]:
        l[i] = r.pop()
    else:
        break
print(sum(l))
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    s = "".join(input().split())
    q = int(input())
    queries = [list(input().split()) for _ in range(q)]
    for query in queries:
        if query[0] == "1":
            s = s[::-1]
            continue
        if query[1] == "1":
            s = query[2] + s
        else:
            s = s + query[2]
    print(s)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    s = input().strip()
    q = int(input())
    queries = [input().split() for _ in range(q)]
    pre = []
    post = []
    flg = True
    for query in queries:
        if query[0] == "1":
            flg = not flg
            continue
        if query[1] == "1":
            if flg:
                pre.append(query[2])
            else:
                post.append(query[2])
        else:
            if flg:
                post.append(query[2])
            else:
                pre.append(query[2])
    pre.reverse()
    pre.append(s)
    pre.extend(post)
    s = "".join(pre)
    if not flg:
        s = s[::-1]
    print(s)


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

a=list(map(int,input().split()))
m=0
for i in range(a[3]):
    if a[0]>0:
        m+=1
        a[0]-=1
    elif a[1]>0:
        a[1]-=1
    elif a[2]>0:
        m-=1
        a[2]-=1

print(m)

### FIXED CODE ###

s=list(map(int,input().split()))
a=s[0]
b=s[1]
c=s[2]
k=s[3]
m=0

if k>a:
    m+=a
    k-=a
    if k>b:
        k-=b
        if k>c:
            m-=c
        else:
            m-=k
else:
    m=k


print(m)
### BUGGY CODE ###

import heapq


N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [float('inf')]*N
dp[0] = 0
i = 1


while not i==N:
    l = min(K,i)
    data = []
    for j in range(1,l+1):
        heapq.heappush(data, dp[i-j]+abs(h[i] - h[i-j]))
    dp[i] = heapq.heappop(data)
    i+=1
    
print(dp[N-1])

### FIXED CODE ###

def test():
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    dp = [float('inf')]*N
    dp[0] = 0
 
    for i in range(1, N):
        dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(max(i-K, 0), i))
 
    print(dp[-1])
 
if __name__ == '__main__':
    test()
### BUGGY CODE ###

n=int(input())
lst=list(map(int, input().split()))
ans = 1
for i in lst:
    ans = ans * i

if ans > 10**18:
    print(-1)
    exit()

print(ans)
    


### FIXED CODE ###

n=int(input())
lst=list(map(int, input().split()))
ans = 1
if 0 in lst:
    print(0)
    exit()

for i in lst:
    ans = ans * i
    if ans > 10**18:
        print(-1)
        exit()


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

A,B = map(int, input().split())
num_set = set()
i=2
while True:
    if(A%i==0 and B%i==0):
        num_set.add(i)
        A = A//i
        B = B//i
        i =2
    elif(A ==i or B == i):
        break
    else:
        i = i+1
print(len(num_set)+1)

### FIXED CODE ###

def prime_factor(n):
    ass = set()
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.add(i)
            n = n//i
    if n != 1:
        ass.add(n)
    return ass

A,B = map(int, input().split())
num_set = set()

A_set = prime_factor(A)
B_set = prime_factor(B)

num_set = A_set.intersection(B_set)

#while True:
#    if(A%i==0 and B%i==0):
#        num_set.add(i)
#        A = A//i
#        B = B//i
#        if(coprime2(A,B)==1):
#            break
#    else:
#        i = i+1
print(len(num_set)+1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)

N, K = list(map(lambda x: int(x), input().split()))
ashiba = [int(s) for s in input().split()]

l = [float('inf')] * N
l[0] = 0

for i in range(N):
	if K > N - i - 1:
		K = N - i - 1
	for j in range(i + 1,i + K + 1):
		cost = abs(ashiba[j] - ashiba[i]) + l[i]
		if l[j] > cost:
			l[j] = cost

print(l[N - 1])

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(x) for x in input().split()]

dp = [float('inf')] * N
dp[0] = 0

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

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

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

now_N = 10 ** 19
while True:
  N = min( abs( N - K ), now_N )
  if now_N == N:
    break
  now_N = N
print( now_N )

### FIXED CODE ###

N, K = map( int, input().split() )
 
now_N = 10 ** 19
while True:
  N = min( abs( N % K ),abs( K - N ), now_N )
  if now_N == N:
    break
  now_N = N
print( now_N )
### BUGGY CODE ###

import heapq
import math

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1

field = []
for _ in range(h):
    field.append(list(input()))
visited = [[[False for _ in range(4)] for _ in range(w)] for _ in range(h)]
costs = [[[99999999 for _ in range(4)] for _ in range(w)] for _ in range(h)]


def calc(cost, d):
    ns = []

    # その方向に進む
    if d == 0:
        ns.append((1, 1, 0, d))
    elif d == 1:
        ns.append((1, 0, 1, d))
    elif d == 2:
        ns.append((1, -1, 0, d))
    elif d == 3:
        ns.append((1, 0, -1, d))

    # 方向転換
    if cost % k == 0:
        dcost = 0
    else:
        dcost = k - cost % k
    if d != 0:
        ns.append((dcost, 0, 0, 0))
    if d != 1:
        ns.append((dcost, 0, 0, 1))
    if d != 2:
        ns.append((dcost, 0, 0, 2))
    if d != 3:
        ns.append((dcost, 0, 0, 3))

    return ns


heap = []
heapq.heappush(heap, (0, (x1, y1, 0)))
costs[x1][y1][0] = 0

while heap:
    cost, (x, y, d) = heapq.heappop(heap)
    if visited[x][y][d]:
        continue
    visited[x][y][d] = True
    for dcost, dx, dy, next_d in calc(cost, d):
        if x + dx >= h or x + dx < 0 or y + dy >= w or y + dy < 0 or field[x + dx][y + dy] == '@' or visited[x + dx][y + dy][next_d]:
            continue
        if costs[x + dx][y + dy][next_d] > cost + dcost:
            costs[x + dx][y + dy][next_d] = cost + dcost
            heapq.heappush(heap, (cost + dcost, (x + dx, y + dy, next_d)))

res = min([costs[x2][y2][d] for d in range(4)])
if res == 99999999:
    print(-1)
else:
    print(math.ceil(res / k))


### FIXED CODE ###

from collections import deque
import sys

read = sys.stdin.read
readline = sys.stdin.readline

h, w, k = map(int, readline().split())
x1, y1, x2, y2 = map(int, readline().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1

field = [readline() for _ in range(h)]
costs = [[-1] * w for _ in range(h)]

q = deque([(x1, y1)])
costs[x1][y1] = 0

while q:
    x, y = q.popleft()
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        for i in range(1, k + 1):
            px, py = x + dx * i, y + dy * i
            if not(0 <= px < h and 0 <= py < w) or field[px][py] == '@':
                break
            if 0 <= costs[px][py] < costs[x][y] + 1:
                break
            if costs[px][py] == -1:
                q.append((px, py))
            costs[px][py] = costs[x][y] + 1

print(costs[x2][y2])
### BUGGY CODE ###

#! cat input | python3 main.py

n, k = map(int, input().split())
a = list(map(int, input().split()))
if n == 1:
    if a[0] == k:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
    __import__("sys").exit()
a.sort()
ma = max(a)
def isfact(n):
    if n == 2: return True
    for i in (2, n**0.5 + 1):
        if n % i == 0:
            return False
    return True
def calcfacts():
    r = []
    for i in range(2, 10**5):
        if isfact(i):
            r.append(i)
    return r
allfacts = calcfacts()

def prim_fact(n):
    facts = []
    ti = 0
    t = allfacts[ti]
    nn = n ** 0.5 + 1
    while True:
        if n % t == 0:
            facts.append(t)
            n //= t
        else:
            ti += 1
            t = allfacts[ti]
        if t >= n or t > nn:
            if n != 1:
                facts.append(n)
            break
    return facts


def f(a, k, ma):
    minv = float("inf")
    for i, v in enumerate(a[1:]):
        if v - a[i] != 0:
            minv = min(minv, v - a[i])
    minv = min(minv, a[0])

    sets = []
    setn = set()
    for v in a:
        s = set(prim_fact(v))
        sets.append(s)
        for i in s: setn.add(i)
    for v in setn:
        for s in sets:
            if v not in s:
                break
        else:
            minv = min(minv, v)
            break
    else:
        return False

    if minv == 1:
        return False

    a = a[:]
    for i in range(0, ma + minv, minv):
        if i == k:
            return False
        if i < a[0]:
            continue
        if i == a[0]:
            del a[0]
        else:
            return False
    return True

if ma < k:
    print("IMPOSSIBLE")
elif f(a, k, ma):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")


### FIXED CODE ###

a, b = map(int, input().split())
array = list(map(int, input().split()))
impossible = "IMPOSSIBLE"
possible = "POSSIBLE"

array = list(set(array))

if len(array) == 1:
    if b == array[0]:
        print(possible)
    else:
        print(impossible)
    exit(0)

array.sort()

btw = [v1 - v2 for v1, v2 in zip(array[1:], array[0:])]
n = sorted(btw)[0]

same = len(set(btw)) == 1 or all([v % n == 0 for v in btw])

if b in array:
    print(possible)
elif array[-1] < b:
    print(impossible)
elif same and (b - array[0]) % n == 0:
    print(possible)
else:
    print(impossible)
### BUGGY CODE ###

from pprint import pprint
import queue

def solve(n, a, b):
    a_pq = queue.PriorityQueue()
    for i, a_i in enumerate(a):
        a_pq.put((a_i, i))
    b_pq = queue.PriorityQueue()
    for i, b_i in enumerate(b):
        b_pq.put((b_i, i))

    state = queue.Queue()
    state.put((0, b[:]))
    while not state.empty():
        count, b_tmp = state.get()
        b_tmp_pq = queue.PriorityQueue()
        for b_tmp_i in b_tmp:
            b_tmp_pq.put(b_tmp_i)
        # print("next:" + str(count))
        # pprint(b_tmp)
        while not b_tmp_pq.empty():
            b_i = b_tmp_pq.get()
            i_b = b_tmp.index(b_i)
            # print(i_b, b_i)
            i_a = (i_b - 1 + n) % n
            i_c = (i_b + 1) % n
            b_cand = b_i
            if b_cand - b_tmp[i_a] - b_tmp[i_c] < a[i_b]:
                continue

            while b_cand - b_tmp[i_a] - b_tmp[i_c] >= a[i_b]:
                b_cand = b_cand - b_tmp[i_a] - b_tmp[i_c]
                count += 1

            b_next = b_tmp[:]
            b_next[i_b] = b_cand
            if b_next == a:
                return count
            # print(count + 1)
            state.put((count, b_next))
            break
    
    return -1


if __name__ == '__main__':

    n = int(input().strip())
    a = list(map(int, input().strip().split(" ")))
    b = list(map(int, input().strip().split(" ")))
    print(solve(n, a, b))

### FIXED CODE ###

from pprint import pprint
import heapq

def solve(n, a, b):
    b_pq = []
    b_rev = {}
    delete = []
    for i, b_i in enumerate(b):
        if b_i == a[i]:
            continue
        heapq.heappush(b_pq, (-1 * b_i, i))

    count = 0
    while b_pq:
        tmp = heapq.heappop(b_pq)
        # pprint(tmp)
        b_i = tmp[0] * -1
        i_b = tmp[1]
        # print(i_b, b_i)
        i_a = (i_b - 1 + n) % n
        i_c = (i_b + 1) % n
        b_cand = b_i
        if b_cand - b[i_a] - b[i_c] < a[i_b]:
            continue

        #while b_cand - b[i_a] - b[i_c] >= a[i_b]:
        #    b_cand = b_cand - b[i_a] - b[i_c]
        #    count += 1
        tmp_count =  (b_cand - a[i_b]) // (b[i_a] + b[i_c])
        b_cand -= (b[i_a] + b[i_c]) * tmp_count
        count += tmp_count

        b[i_b] = b_cand
        if b_cand != a[i_b]:
            heapq.heappush(b_pq, (-1 * b_cand, i_b))
        # print("count: ", count)
        # pprint(b)
         

        if b_cand == a[i_b] and b == a:
            return count
    
    return -1


if __name__ == '__main__':

    n = int(input().strip())
    a = list(map(int, input().strip().split(" ")))
    b = list(map(int, input().strip().split(" ")))
    print(solve(n, a, b))
### BUGGY CODE ###

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

#DP[keta][limit]で考える

def ANS(keta,limit):
    
    if keta==-1:
        return 0

    A1=0
    A0=0
    for a in A:
        if a & (1<<keta)==0:
            A1+=1<<keta
        else:
            A0+=1<<keta
    
    if limit==1:               
        return max(A0,A1)+ANS(keta-1,1)

    if limit==0:
        if K & (1<<keta)==0:
            return A0+ANS(keta-1,0)
        else:
            return max(A0+ANS(keta-1,1),A1+ANS(keta-1,0))

print(ANS(50,0))

### FIXED CODE ###

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

for i in range(50):
    if K<(1<<i):
        break

keta=i

NOW=1
ANS=0

for i in range(keta-1,-1,-1):
    #print(i)
    if NOW==1 and K & (1<<i)!=0:
        #print("")
        A0=0
        A1=0
        for a in A:
            if a & (1<<i) ==0:
                A1+=(1<<i)
            else:
                A0+=(1<<i)

        if A1>A0:
            ANS+=(1<<i)
        else:
            ANS+=0
            NOW=0

    elif NOW==1 and K&(1<<i)==0:
        A0=0
        for a in A:
            if a & (1<<i) !=0:
                A0+=(1<<i)

        ANS+=0

    elif NOW==0:
        A0=0
        A1=0
        for a in A:
            if a & (1<<i) ==0:
                A1+=(1<<i)
            else:
                A0+=(1<<i)

        if A1>A0:
            ANS+=(1<<i)
        else:
            ANS+=0

#print(ANS)
SUM=0
for a in A:
    SUM+=ANS^a

print(SUM)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split())) #サイコロの最大値

# 期待値の配列を作る
e = []
max_m = 0
f = []
e = [(1+p[i])/2  for i in range(n)]
for j in range(n-k+1):
    m = sum(e[j:j+k])
    max_m = max(max_m, m)
    # if max_m < m:
    #     max_m = m

print(max_m)

### FIXED CODE ###

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

e = []
max_ = 0
sum_ = 0
f = []
e = [(1+p[i])/2  for i in range(n)]
for i in range(n):
    if i < k:
        sum_ += e[i]
        max_ = sum_
    else:
        sum_ = sum_ + e[i] - e[i - k]
        max_ = max(max_, sum_)

print(max_)