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

inf = 10 ** 7
N, M = map(int, input().split())
P = [list(map(int,input().split())) for i in range(M)]
a = [[] for i in range(N)]
for i in P:
    a[i[0]-1].append(i[1]-1)
    a[i[1]-1].append(i[0]-1)
path = [-1] * N
path[0] = 0
checked = [False] * N
stack = [(0,0)]
while (len(stack) != 0):
    kk = stack.pop(0)
    now = kk[0]
    pre = kk[1]
    if  not checked[now]:    
        nextP = a[now]
        checked[now] = True
        path[now] = pre
        for i in nextP:
            stack.append((i,now))
if False in checked:
    print("No")
else:
    print("Yes")
    for i in path[1:]:
        print(i + 1)





### FIXED CODE ###

from collections import deque
inf = 10 ** 7
N, M = map(int, input().split())
P = [list(map(int,input().split())) for i in range(M)]
a = [[] for i in range(N)]
for i in P:
    a[i[0]-1].append(i[1]-1)
    a[i[1]-1].append(i[0]-1)
path = [-1] * N
path[0] = 0
checked = [False] * N
stack = deque([(0,0)])
while (len(stack) != 0):
    kk = stack.popleft()
    now = kk[0]
    pre = kk[1]
    if  not checked[now]:    
        nextP = a[now]
        checked[now] = True
        path[now] = pre
        for i in nextP:
            stack.append((i,now))
if False in checked:
    print("No")
else:
    print("Yes")
    for i in path[1:]:
        print(i + 1)
### BUGGY CODE ###

import sys


def main():
    N = int(input())
    a = list(map(int, input().split()))
    num = 0
    blocks = 0

    while True:
        flag=0
        num += 1
        for i in range(0, len(a)):
            if(num==a[i]):
                blocks += i
                del a[:i+1]
                flag=1
                break


        if(flag==0):
            if(num==1):
                print('-1')
                sys.exit()

            blocks += len(a)
            print(blocks)
            sys.exit()

main()

### FIXED CODE ###

import sys

def main():
    N = int(input())
    a = list(map(int,input().split()))
    num = 1

    for i in a:
        if(i==num):
            num += 1

    if(num!=1):
        print(len(a) - num + 1)
    else:
        print('-1')

main()
### BUGGY CODE ###

abx=list(map(int,input().split()))
a=abx[0]
b=abx[1]
x=abx[2]
cnt=0
for i in range(a,b+1):
    if i%x==0:
        cnt=cnt+1

print(cnt)


### FIXED CODE ###

a, b, x = [int(n) for n in input().split()]
 
qa = a // x
qb = b // x
ra = a % x
rb = b % x
res = qb - qa
if ra == 0:
    res += 1
 
print(res)
### BUGGY CODE ###

input = int(input())
buf = input
result = 1
for i in range(2,input+1):
    if buf%i==0:
        result *= (1 - 1/i)
    while buf%i==0:
        buf /= i
result *= input
print(int(result))

### FIXED CODE ###

def phi(n):
    r = n
    i = 2
    while i*i <= n:
        if n%i==0:
            r -= r/i
            while n%i==0:
                n /= i
        i += 1
    if n>1: r-= r/n
    return r

n = int(input())
print(int(phi(n)))
### BUGGY CODE ###

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

dict = {}
for i in list:
    dict[i]= list.index(i)+1
for i in range(1, n+1):
    print(dict[i], end = " ")

### FIXED CODE ###

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

dict = {}
count = 1

for i in list:
    dict[i]= count
    count += 1
for i in range(1, n+1):
    print(dict[i], end = " ")
### BUGGY CODE ###

import sys
from collections import defaultdict
def wi(): return list(map(int, sys.stdin.readline().split()))
def i(): return int(sys.stdin.readline())
def mi(n): return [wi() for _ in range(n)]#MatrixInt

def main():
    n, q = wi()
    ab = mi(n - 1)
    px = mi(q)
    numdict = {}
    for i in range(n + 1):
        numdict[i] = []

    parli = [0] * (n + 1)
    parli[1] = 1
    for i in range(n - 1):
        if parli[ab[i][0]] == 0:
            parli[ab[i][0]] = 1
        else:
            numdict[ab[i][0]].append(ab[i][1])
        if parli[ab[i][1]] == 0:
            parli[ab[i][1]] = 1
        else:
            numdict[ab[i][1]].append(ab[i][0])

    plsdict = defaultdict(int)
    for i in range(q):
        plsdict[px[i][0]] += px[i][1]



    queue = []
    queue.append(1)
    while queue != []:
        po = queue.pop()
        for kk in numdict[po]:
            queue.append(kk)
            plsdict[kk] += plsdict[po]

    for i in range(1, n + 1):
        print(plsdict[i],"" , end="")

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import defaultdict
def wi(): return list(map(int, sys.stdin.readline().split()))
def i(): return int(sys.stdin.readline())
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def mip(n): return [wip() for _ in range(n)]

def main():
    n, q = wi()
    ab = mip(n - 1)
    px = mip(q)
    for i in range(q):
        px[i][1] += 1


    cost = [0] * n
    for i in range(q):
        cost[px[i][0]] += px[i][1]

    son = [[] for _ in range(n)]
    for i in range(n - 1):
        son[ab[i][0]].append(ab[i][1])
        son[ab[i][1]].append(ab[i][0])

    flagli = [0] * n
    flagli[0] = 1
    queue = []
    queue.append(0)
    while queue != []:
        po = queue.pop()
        for kk in son[po]:
            if flagli[kk] == 0:
                flagli[kk] = 1
                queue.append(kk)
                cost[kk] += cost[po]

    for i in range(n):
        print(cost[i],"" , end="")

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

def read():
	return [int(i) for i in input().split(" ")]
N = int(input())
T = read()
A = read()
t = [(i != j, i) for i, j in zip(T, [None] + T)]
a = [(i != j, i) for i, j in zip(A, (A + [None])[1:])]
P = 1
for p, q in zip(t, a):
	if(p[0]):
		if(q[0]):
			if(p[1] != q[1]):
				print(0)
				exit()
		elif(q[1] < p[1]):
			print(0)
			exit()
	elif(q[0]):
		if(p[1] < q[1]):
			print(0)
			exit()
	else:
		P *= min(p[1], q[1])
print(P % (10 ** 9 + 7))


### FIXED CODE ###

def read():
	return [int(i) for i in input().split(" ")]
N = int(input())
T = read()
A = read()
t = [(i != j, i) for i, j in zip(T, [None] + T)]
a = [(i != j, i) for i, j in zip(A, (A + [None])[1:])]
P = 1
for p, q in zip(t, a):
	if(p[0]):
		if(q[0]):
			if(p[1] != q[1]):
				print(0)
				exit()
		else:
			if(q[1] < p[1]):
				print(0)
				exit()
	elif(q[0]):
		if(p[1] < q[1]):
			print(0)
			exit()
	else:
		P = P * min(p[1], q[1]) % (10 ** 9 + 7)
print(P)
### BUGGY CODE ###

from collections import deque

n,x,y = map(int, input().split())
dp = [[100000000 for j in range(n)] for i in range(n)]
re = [0]*n
for i in range(n):
  for j in range(n):
    if i==j:
      dp[i][j] = 0
    if abs(i-j)==1:
      dp[i][j] = 1
    if i==x-1 and j==y-1:
      dp[i][j] = 1
    if i==y-1 and j==x-1:
      dp[i][j] = 1
    

for k in range(n):
  for i in range(n):
    for j in range(n):
      dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);


for i in range(n):
  for j in range(i):
    re[dp[i][j]] +=1
    
for i in range(n-1):
  print(re[i+1])

### FIXED CODE ###

n,x,y = map(int, input().split())
p = [[100000000 for j in range(n)] for i in range(n)]
dp = [(-1,0),(1,0),(0,-1),(0,1)]
c = [[] for i in range(n)]

for i in range(n):
  for j in range(n-i):
    j += i
    if i==j:
      p[i][j] = 0
    if abs(i-j)==1:
      p[i][j] = 1
      c[1].append((i,j))
    if i==x-1 and j==y-1:
      p[i][j] = 1
      c[1].append((i,j))
    if i==y-1 and j==x-1:
      p[i][j] = 1
      c[1].append((i,j))
    
print(len(c[1]))

for i in range(n-2):
  i += 2
  for (a,b) in c[i-1]:
    for (da,db) in dp:
      aa = a + da
      bb = b + db
      if not (0 <= aa < n and 0 <= bb < n):
        continue
      if p[aa][bb] > i:
        p[aa][bb] = i
        c[i].append((aa,bb))
  print(len(c[i]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

mod = 10 ** 9 + 7
ans = 0
ni = 1

for i in range(60):
    x = sum([1 for j in range(N) if (A[j] >> i) & 1])
    buff = x * (N - x) % mod
    buff = buff * ni % mod
    ans += buff
    ans %= mod
    ni = ni * 2 % mod

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

mod = 10 ** 9 + 7
ans = 0
ni = 1

for i in range(60):
    x = sum([1 for j in range(N) if (A[j] >> i) & 1])
    buff = x * (N - x) * ni
    ans += buff
    ni = ni * 2

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

import collections
q=collections.deque()
h,w=map(int,input().split())
arr=[[] for _ in range(h+2)]
for i in range(w+2):
  arr[0].append(True)
for i in range(h):
  arr[i+1].append(True)
  for j in input():
    if j=='#':
      arr[i+1].append(True)
    else:
      arr[i+1].append(False)
  arr[i+1].append(True)
for i in range(w+2):
  arr[h+1].append(True)
dx=[-1,0,1,0]
dy=[0,-1,0,1]
for i in range(1,h+1):
  for j in range(1,w+1):
    if arr[i][j]:
      q.append([i,j])
ans=0
while 1:
  nq=collections.deque()
  for y,x in q:
    for i in range(4):
      if not arr[y+dy[i]][x+dx[i]]:
        nq.append([y+dy[i],x+dx[i]])
        arr[y+dy[i]][x+dx[i]]=True
  if len(nq)==0:
    print(ans)
    break
  else:
    q=nq
    ans+=1

### FIXED CODE ###

import collections
q=collections.deque()
h,w=map(int,input().split())
arr=[[] for _ in range(h+2)]
for i in range(w+2):
  arr[0].append('#')
for i in range(h):
  arr[i+1].append('#')
  for j in input():
    arr[i+1].append(j)
  arr[i+1].append('#')
for i in range(w+2):
  arr[h+1].append('#')
dx=[-1,0,1,0]
dy=[0,-1,0,1]
for i in range(1,h+1):
  for j in range(1,w+1):
    if arr[i][j]=='#':
      q.append([i,j,0])
while 1:
  y,x,cnt=q.popleft()
  for i in range(4):
    if arr[y+dy[i]][x+dx[i]]=='.':
      q.append([y+dy[i],x+dx[i],cnt+1])
      arr[y+dy[i]][x+dx[i]]='#'
  if len(q)==0:
    print(cnt)
    break
### BUGGY CODE ###

n = int(input())
c = list(input())

end = []
for i in range(n+1):
    end.append("R"*i + "W"*(n-i))
#print(end)

newc = "".join(c)
ans = 0
if newc in end:
    print(ans)
    exit()
while newc not in end:
    for i in range(n):
        if c[i] == "W":
            c[i] = "R"
            break
    for i in reversed(range(n)):
        if c[i] == "R":
            c[i] = "W"
            break
    newc = "".join(c)
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
c = list(input())

x = c.count("R")

ans = 0
for i in range(x):
    if c[i] == "W":
        ans += 1

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

n = int(input())

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

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

### FIXED CODE ###

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

seki = 1
if 0 in a:
  print(0)
else:

  for i in range(n):
    seki*=a[i]
    if seki > 10**18:
      break
  if seki > 10**18:
    print('-1')
  else:
    print(seki)
### BUGGY CODE ###

import bisect
# from collections import Counter, defaultdict, deque, namedtuple
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n, k = list(map(int,ipti().split()))
    s = input()
    s_first = s[0]
    s_last = s[-1]

    s_groupby = itertools.groupby(s)
    len_group = []

    if s_first == "0":
        len_group.append(0)

    for key, group in s_groupby:
        list_group = list(group)
        len_group.append(len(list_group))

    if s_last == "0":
        len_group.append(0)

    range_num = 2*k + 1
    ans = 0

    if range_num >= len(len_group):
        ans = sum(len_group)
    else:
        begin = 0
        end = 0
        while end != len(len_group):
            end = begin + range_num
            ans = max(ans,sum(len_group[begin:end]))
            begin += 2

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect
# from collections import Counter, defaultdict, deque, namedtuple
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n, k = list(map(int,ipti().split()))
    s = input()

    lg = [0] * (n+3)

    s_first = s[0]
    s_last =s[-1]

    idx = 0

    if s_first == "0":
        lg[0] = 0
        idx = 1

    s_groupby = itertools.groupby(s)

    for _, group in s_groupby:
        lg[idx] = len(list(group))
        idx += 1

    if s_last == "0":
        idx += 1

    rn = 2*k + 1

    if rn >= idx:
        print(n)
        sys.exit()

    temp = sum(lg[0:rn])
    ans = temp

    for i in range(2, idx-rn+1, 2):
        temp -= (lg[i-2] + lg[i-1])
        temp += (lg[i-2+rn] + lg[i-1+rn])
        ans = max(ans, temp)

    print(ans)

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

import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    i = L
    while i < N :
        if ANS[i] : 
            i += 1
            continue
        else : 
            ANS[i] = min(Whole[i+1-L:i+1])
            if None not in ANS[i:i+L] :
                i += L
                continue
            i+=1
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.99
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
# import sys
# sys.setrecursionlimit(10 ** 5+1)
# import numpy as np
# import IPython

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


N, M = ds_in()

child = {i+1: [] for i in range(N)}
parent = {i+1: [] for i in range(N)}
inflow = {i+1: 0 for i in range(N)}
for _ in range(N+M-1):
    a, b = ds_in()
    child[a].append(b)
    parent[b].append(a)
    inflow[b] += 1

t_index = {i: [] for i in range(max(inflow.values()) + 1)}
for edge, count in inflow.items():
    t_index[count].append(edge)

sorted_edges = []
while len(sorted_edges) < N:
    par = t_index[0].pop()
    sorted_edges.append(par)
    for chi in child[par]:
        t_index[inflow[chi]].remove(chi)
        inflow[chi] -= 1
        t_index[inflow[chi]].append(chi)

for i in range(1, N+1):
    if i == sorted_edges[0]:
        print(0)
    else:
        par = -1
        for p in parent[i]:
            par = max(par, sorted_edges.index(p))
        print(sorted_edges[par])


### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
# import sys
# sys.setrecursionlimit(10 ** 5+1)
import numpy as np
# import IPython

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


N, M = ds_in()

child = {i+1: [] for i in range(N)}
parent = {i+1: [] for i in range(N)}
inflow = {i+1: 0 for i in range(N)}
for _ in range(N+M-1):
    a, b = ds_in()
    child[a].append(b)
    parent[b].append(a)
    inflow[b] += 1

candidates = []
for i, j in inflow.items():
    if j == 0:
        candidates.append(i)

sorted_edges = []
while len(sorted_edges) < N:
    par = candidates.pop()
    sorted_edges.append(par)
    for chi in child[par]:
        inflow[chi] -= 1
        if inflow[chi] == 0:
            candidates.append(chi)


sorted_index = np.zeros(N+1, dtype=int)
sorted_index[sorted_edges] = np.arange(N)

for i in range(1, N+1):
    if i == sorted_edges[0]:
        print(0)
    else:
        print(parent[i][np.argmax(sorted_index[parent[i]])])
### BUGGY CODE ###

N=int(input())
*A,=map(int,input().split())
t=10**9+7
S=[a%t for a in A]

ans=0
for i in range(N):
    for j in range(i+1,N):
       ans+=(S[i]*S[j])%t
print(ans%t) 

### FIXED CODE ###

N=int(input())
*A,=map(int,input().split())
t=10**9+7
S=[a%t for a in A]
g=sum(S)

ans=0
for i in range(N):
       g-=S[i]
       ans+=S[i]*g%t
print(ans%t)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
ans = []
for i in range(q):
    a,b = map(int,input().split())
    ans.append(s[a-1:b].count('AC'))
for i in range(q):
    print(ans[i])

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
ans = []
a = [0]*(10**5+1)
add = 0
check = False
for i in range(n):
    if check and s[i] == 'C':
        add +=1
    if s[i] == 'A':
        check = True
    else:
        check = False
    
    a[i] += add
for i in range(q):
    b,c = map(int,input().split())
    ans.append(a[c-1]-a[b-1])
for i in range(q):
    print(ans[i])
### BUGGY CODE ###

import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
a = LI()

asort = sorted(a)

d = defaultdict(int)
for i in range(N):
    d[a[i]] += 1

ans = [0]*N
max_ = 0
for i in range(N):
    if a[i] > max_:
        diff = a[i]-max_
        num = N-bisect_left(asort,a[i])
        ans[i] = num*diff
        for j in range(max_+1,a[i]):
            ans[i] += (j-max_)*d[j]
        max_ = a[i]

ans[0] = sum(a)-sum(ans[1:])

for i in range(N):
    print(ans[i])

### FIXED CODE ###

import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
a = LI()

asort = sorted(a)

d = defaultdict(int)
for i in range(N):
    d[a[i]] += 1
keys = sorted(list(d.keys()))

ans = [0]*N
max_ = 0
place = 0
for i in range(N):
    if a[i] > max_:
        diff = a[i]-max_
        num = N-bisect_left(asort,a[i])
        ans[i] = num*diff
        for j in range(place,len(keys)):
            if keys[j] <= max_:
                continue
            elif keys[j] >= a[i]:
                place = j
                break
            else:
                ans[i] += (keys[j]-max_)*d[keys[j]]
        max_ = a[i]

ans[0] = sum(a)-sum(ans[1:])

for i in range(N):
    print(ans[i])
### BUGGY CODE ###

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
point = [K]*N

for a in A:
  point = list(map(lambda x: x-1, point))
  point[a-1] += 1

for po in point:
  if po > 0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
num = K-Q
point = [num]*N

for a in A:
  point[a-1] += 1

for po in point:
  if po > 0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

# coding: utf-8


def solve(arg: str) -> str:
    a, b = map(int, arg.split())
    div = [1]
    for n in range(2, min(a, b) + 1):
        if a % n == 0 and b % n == 0:
            if(all([n % m != 0 for m in div if m != 1])):
                div.append(n)

    return str(len(div))


if __name__ == "__main__":
    print(solve(input()))


### FIXED CODE ###

# coding: utf-8
import fractions


def solve(arg: str) -> str:
    a, b = map(int, arg.split())
    div = [1]

    g = fractions.gcd(a, b)
    n = 2
    while n*n <= g:
        if g % n == 0:
            div.append(n)
            while g % n == 0:
                g = int(g/n)
        n += 1
    if g != 1:
        div.append(g)

    return str(len(div))


if __name__ == "__main__":
    print(solve(input()))
### BUGGY CODE ###

n,k=map(int,input().split())
P=list(map(int,input().split()))
R=[0]*(n-k+1)
ma=0
for i in range(n-k+1):
    R[i]=sum(P[i:i+k])
    ma=max(ma,R[i])
print((ma+k)/2)

### FIXED CODE ###

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

S=[0]*(n+1)
S[1]=P[0]
for i in range(2,n+1):
        S[i]=S[i-1]+P[i-1]
ma=0
for i in range(k,n+1):
       s=S[i]-S[i-k]
       if ma<s:
              ma=s
print((ma+k)/2)
### BUGGY CODE ###

import collections
import itertools
import functools
import math

if __name__ == "__main__":
    k, s = map(int, input().split())
    res = 0
    for i in range(k + 1):
        for j in range(k + 1):
            for k in range(k + 1):
                res += int(i + j + k == s)

    print(res)

### FIXED CODE ###

import collections
import itertools
import functools
import math
import scipy.special

if __name__ == "__main__":
    k, s = map(int, input().split())
    res = 0
    for i in range(k + 1):
        for j in range(k + 1):
            if 0 <= s - i - j <= k:
                res += 1
    print(res)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []

for i in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

X = np.array([0]*(10**5))
Y = np.array([i  for i in range(1, (10**5)+1)])

for j in range(N):
    X[A[j]-1] += 1

for i in range(Q):
    a = X[B[i]-1]
    X[B[i]-1] = 0
    X[C[i]-1] += a
    print(X@Y)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
X = [0] * (10**5)

for i in range(N):
    X[A[i]-1] += 1

ans = sum(A)

for j in range(Q):
    b, c = map(int, input().split())
    a = X[b-1]
    X[b-1] = 0
    X[c-1] += a
    ans = ans - a*b + c*a
    print(ans)
### BUGGY CODE ###

import bisect

N = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        p = l[:i]
        a, b = l[i], l[j]
        low = b - a + 1
        high = a + b
        ans += bisect.bisect_left(p, high) - bisect.bisect_left(p, low)
print(ans)

### FIXED CODE ###

import bisect

N = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        p = l[:i]
        a, b = l[i], l[j]
        low = b - a + 1
        high = a + b
        ans += bisect.bisect_left(p, high) - bisect.bisect_left(p, low)
print(ans)
### BUGGY CODE ###

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

wv = list(map(int, input().split()) for _ in range(N))

dp = [0] * (W+1)

for w, v in wv:
    for j in range(W, w-1, -1):
        DP = dp[j-w] + v
        dp[j] = max(dp[j], DP)

print(max(dp))


### FIXED CODE ###

def dp():
    n, W = map(int, input().split())
    wv = (map(int, input().split()) for _ in range(n))
    dp = [0] * (W+1)

    for w, v in wv:
        for j in range(W, w-1, -1):
            DP = dp[j-w] + v
            if dp[j] < DP:
                dp[j] = DP
    return max(dp)
print(dp())