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

import copy
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
S = [[1 if a == '.' else 0 for a in list(input())]  for _ in range(H)]

def main():
    R = copy.deepcopy(S)
    for h in range(H):
        s = 0
        for w in range(W):
            if R[h][w] == 1:
                s += 1
                R[h][w] = s
            else:
                s = 0
        l = 0
        for w in range(W-1, -1, -1):
            if R[h][w] > 0:
                l = max(l, R[h][w])
                R[h][w] = l
            else:
                l = 0

    L = copy.deepcopy(S)
    for w in range(W):
        s = 0
        for h in range(H):
            if L[h][w] == 1:
                s += 1
                L[h][w] = s
            else:
                s = 0
        l = 0
        for h in range(H-1, -1, -1):
            if L[h][w] > 0:
                l = max(l, L[h][w])
                L[h][w] = l
            else:
                l = 0
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, L[h][w]+R[h][w]-1)
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import copy
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
S = [[1 if a == '.' else 0 for a in list(input())]  for _ in range(H)]

def main():
    R = copy.deepcopy(S)
    for h in range(H):
        s = 0
        for w in range(W):
            if R[h][w] == 1:
                s += 1
                R[h][w] = s
            else:
                s = 0
        l = 0
        for w in range(W-1, -1, -1):
            if R[h][w] > 0:
                l = max(l, R[h][w])
                R[h][w] = l
            else:
                l = 0

    L = copy.deepcopy(S)
    for w in range(W):
        s = 0
        for h in range(H):
            if L[h][w] == 1:
                s += 1
                L[h][w] = s
            else:
                s = 0
        l = 0
        for h in range(H-1, -1, -1):
            if L[h][w] > 0:
                l = max(l, L[h][w])
                L[h][w] = l
            else:
                l = 0
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, L[h][w]+R[h][w]-1)
    print(ans)

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

import math
N = int(input())
A_array = list(map(int, input().split()))

A_array.sort()

use_array = [0] * A_array[-1]

ans = 0

for i in range(N):
    a = A_array[i]
    for j in range(1, int(math.sqrt(a)) + 1):
        if a % j == 0:
            if use_array[j - 1] == 1 or use_array[a // j - 1] == 1:
                break
    else:
        use_array[a - 1] = 1
        if i != 0:
            if A_array[i] == A_array[i - 1]:
                continue
        if i != N - 1:
            if A_array[i] == A_array[i + 1]:
                continue
        ans += 1
    use_array[a - 1] = 1

print(ans)


### FIXED CODE ###

import math
N = int(input())
A_array = list(map(int, input().split()))

A_array.sort()

ans = 0

if A_array[0] == 1:
    if N >= 2 and A_array[1] != 1 or N == 1:
        print(1)
    else:
        print(0)
    exit()


ng_array = [0] * (10 ** 6)


for i, a in enumerate(A_array):
    if i != 0 and a == A_array[i - 1]:
        continue
    j = 2
    while a * j <= 10 ** 6:
        ng_array[a * j - 1] = 1
        j += 1


for i in range(N):
    a = A_array[i]
    if i != 0:
        if A_array[i] == A_array[i - 1]:
            continue
    if i != N - 1:
        if A_array[i] == A_array[i + 1]:
            continue
    if ng_array[a-1] == 0:
        ans += 1
print(ans)
### BUGGY CODE ###

#################################
##ワーシャルフロイド法 n~3
#################################
def warshall_floyd(n,d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
##############################
#from scipy.sparse.csgraph import csgraph_from_dense,dijkstra,floyd_warshall
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)
N,M,L =LI()
s = []
t = []
dp = [[inf] * (N) for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c
Q = I()
for i in range(Q):
    a,b = LI()
    s.append(a-1)
    t.append(b-1)

for i in range(N):
    dp[i][i] = 0

#print(warshall_floyd(N,dp))
d1 = [[0] * (N) for _ in range(N)]
d1 = warshall_floyd(N,dp)
#G = csgraph_from_dense(dp)
#d1 = floyd_warshall(G)

newdp = [[inf] * (N) for _ in range(N)]
for i in range(N):
    for j in range(i+1,N):
        if d1[i][j]<=L:
            newdp[i][j] = 1
            newdp[j][i] = 1

for i in range(N):
    newdp[i][i] = 0
#print(newdp)
#print(warshall_floyd(N,newdp))
d2 = [[0] * (N) for _ in range(N)]
d2 = warshall_floyd(N,newdp)
#G2 = csgraph_from_dense(newdp)
#d2 = floyd_warshall(G2)

for i in range(Q):
    ans = d2[s[i]][t[i]]-1
    if ans!= inf:
        print(int(ans))
    else:
        print("-1")


### FIXED CODE ###

#################################
##ワーシャルフロイド法 n~3
#################################
def warshall_floyd(n,d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
##############################
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)
N,M,L =LI()
s = []
t = []
dp = [[inf] * (N) for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c
Q = I()
for i in range(Q):
    a,b = LI()
    s.append(a-1)
    t.append(b-1)

for i in range(N):
    dp[i][i] = 0

#print(warshall_floyd(N,dp))
d1 = [[0] * (N) for _ in range(N)]
d1 = warshall_floyd(N,dp)

newdp = [[inf] * (N) for _ in range(N)]
for i in range(N):
    for j in range(i+1,N):
        if d1[i][j]<=L:
            newdp[i][j] = 1
            newdp[j][i] = 1

for i in range(N):
    newdp[i][i] = 0
#print(newdp)
#print(warshall_floyd(N,newdp))
d2 = [[0] * (N) for _ in range(N)]
d2 = warshall_floyd(N,newdp)

for i in range(Q):
    ans = d2[s[i]][t[i]]-1
    if ans!= inf:
        print(ans)
    else:
        print("-1")
### BUGGY CODE ###

n, m, K = map(int, input().split())
mod = 998244353


def comb(n, r):
    res = 1
    for i in range(1, r+1):
        res = res*(n-i+1) % mod
        res = res*pow(i, mod-2, mod) % mod
    return res


def paint(k):
    res = (m * comb(n-1, k) % mod) * pow(m-1, n-1-k, mod)
    res % mod
    return res

ans = 0
for k in range(K+1):
    ans += paint(k)
    ans %= mod
print(ans)

### FIXED CODE ###

n, m, K = map(int, input().split())
mod = 998244353

fac = [1] * (n + 1)
inv = [1] * (n + 1)

for j in range(1, n + 1):
    fac[j] = fac[j - 1] * j % mod

inv[n] = pow(fac[n], mod - 2, mod)
for j in range(n - 1, -1, -1):
    inv[j] = inv[j + 1] * (j + 1) % mod


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod


def paint(k):
    res = (m * comb(n-1, k)) % mod * pow(m-1, n-1-k, mod)
    res %= mod
    return res

ans = 0
for k in range(K+1):
    ans += paint(k)
    ans %= mod
print(ans)
### BUGGY CODE ###

import sys
n = int(input())

a = (list(map(int, input().split())))
dx = 10 ** 9 + 7

a = [i for i in a if i != 0]

ans = 0
alist = []
for i in range(len(a)-1):
    for j in range(i+1, len(a)):
        t = (a[i] * a[j]) % dx
        alist.append(t)

for i in range(len(alist)):
    ans += alist[i]
    ans %= dx

ans %= dx
print(ans)


### FIXED CODE ###

n = int(input())

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

S = sum(a)

S2 = sum(map(lambda x: x * x, a ))

ans = (S * S - S2) // 2 % 1000000007
print(ans)
### BUGGY CODE ###

N = int(input())
ll = list(map(int, input().split(" ")))


def ni(i):
    return int(bin(i)[2:])


def hantei(l):
    sum_num = str(sum(l))
    if "2" not in sum_num:
        return True
    else:
        return False


for i in range(N):
    ll[i] = ni(ll[i])

count = 0
left = 0
right = 0

for left in range(N):
    while True:
        if right == N+1:
            break
        if hantei(ll[left:right]):
            pass
        else:
            break
        right += 1

    count += right - left - 1

print(count)

### FIXED CODE ###

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

l, r = 0, 0
sum_a = 0
ans = 0
while r < n:
    # 右端を進める
    if sum_a & a[r] == 0:
        sum_a += a[r]
        r += 1
        ans += r - l
    # 右端と左端を進める
    elif l == r:
        l += 1
        r += 1
    # 左端を進める
    else:
        sum_a -= a[l]
        l += 1
    # print('l={}, r={}, size={}, ans={}, {}'.format(l, r, r - l, ans, a[l:r]))
print(ans)
### BUGGY CODE ###

n = int(input(''))
adl = input('')

a = list(map(int,adl.split(' ')))

number = 0

mod = 7+1000000000

amari = 0



for i in range(n):
    aa = 0
    for e in range(n-i-1):
        j = i+e+1
        if i != j:
            aa = aa + a[j]
    number = number + (a[i] * aa)
amari = number % mod
print(amari)


### FIXED CODE ###

n = int(input(''))
adl = input('')

a = list(map(int,adl.split(' ')))

number = 0

mod = 1000000007

amari = 0

all_a = 0

for i in range(n):
    all_a = all_a + a[i]

for i in range(n):
    all_a = all_a - a[i]
    number = number + (a[i] * all_a)
    number = number % mod
amari = number % mod
print(amari)
### BUGGY CODE ###

n,q=map(int,input().split())
s=list(str(input()))
lr=[]
for i in range(q):
    lr.append(list(map(int,input().split())))

for i in range(q):
    tl=s[lr[i][0]-1:lr[i][1]]
    ctr=0
    for k in range(len(tl)-1):
        if tl[k]=="A" and tl[k+1]=="C":
            ctr+=1
        else:
            pass
    print(ctr)


### FIXED CODE ###

n,q=map(int,input().split())
s=list(str(input()))
lr=[]
for i in range(q):
    lr.append(list(map(int,input().split())))
ctr1=0
t_list=[0]
for i in range(n-1):
    if s[i]=="A" and s[i+1]=="C":
        ctr1+=1
        t_list.append(ctr1)
    else:
        t_list.append(ctr1)

for i in range(q):
    left=lr[i][0]
    right=lr[i][1]
    print(t_list[right-1]-t_list[left-1])
### BUGGY CODE ###

N,K = map(int,input().split())
ans,n = 1,1
dp = [1]*N
As = []
for i in range(N):
  Ai = int(input())
  for j,Aj in enumerate(As):
    if abs(Ai-Aj)<=K: dp[i] = max(dp[i],dp[j]+1)
  As.append(Ai)
print(dp[-1])

### FIXED CODE ###

class SegTree(object):
  def __init__(self,op,e,n,init_val):
    self.num = 1<<(n-1).bit_length() 
    self.S = [e]*self.num*2
    self.op = op
    self.e = e
    for i,v in enumerate(init_val): self.S[self.num+i] = v
    for i in range(self.num-1,0,-1):
      self.S[i] = self.op(self.S[i*2], self.S[i*2+1])
      
  def set(self,index,value):
    idx = self.num+index
    self.S[idx] = value
    while idx>0:
      self.S[idx>>1] = self.op(self.S[idx],self.S[idx^1])
      idx>>=1
      
  def prod(self,l,r):
    res = self.e
    l = max(0,l)+self.num
    r = min(r,self.num-1)+self.num
    while l<r:
      if l&1:
        res = self.op(res,self.S[l])
        l += 1
      if r&1:
        res = self.op(self.S[r-1],res)
      l >>= 1
      r >>= 1
    return res
        
N,K = map(int,input().split())
ST = SegTree(max,0,300001,[0]*300001)
ans = 1
for i in range(N):
  A = int(input())
  l,r = max(0,A-K),min(A+K,300000)
  v = ST.prod(l,r+1)+1
  ans = max(ans,v)
  ST.set(A,v)
print(ans)
### BUGGY CODE ###

N = int(input())

def num_divisors_table(n):
    table = [0] * (n + 1)
    
    ans = 0
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            ans += j
    
    return ans

print(num_divisors_table(N))


### FIXED CODE ###

N = int(input())

def num_divisors_table(n):
    table = [0] * (n + 1)
    
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            table[j] += 1
    
    return table

ls = num_divisors_table(N)
ans = 0
for i in range(1, N+1):
    ans += i * ls[i]
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = [int(_) for _ in input().split()]
BC = [[int(_) for _ in input().split()] for _ in range(M)]
ABC = []
for x, y in BC:
    A.extend([y] * x)

A.sort(reverse = True)
print(sum(A[:N]))

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(_) for _ in input().split()]
BC = [[int(_) for _ in input().split()] for _ in range(M)]
# Cの大きい順にソート
BC.sort(key = lambda x: x[1], reverse = True)
ABC = []
for x, y in BC:
    A.extend([y] * x)
    # 2N個以上あっても選ばれないので、そこで打ち切り
    if len(A) > N * 2:
        break

A.sort(reverse = True)
print(sum(A[:N]))
### BUGGY CODE ###

# standard input
S = input()
Q = int(input())
Query = []
num_reverse = 0

S_r = ''.join(reversed(S))

for _ in range(Q):

    q = tuple(map(str, input().split()))

    if int(q[0]) == 1:
        num_reverse += 1

    else:
        if (num_reverse + int(q[1])) % 2 == 0:
            S = S + q[2]
            S_r = q[2] + S_r
        else:
            S = q[2] + S
            S_r = S_r + q[2]

if num_reverse % 2 == 1:
    print(S_r)
else:
    print(S)


### FIXED CODE ###

# standard input
S = input()
Q = int(input())
Query = []
num_reverse = 0

L = ''
R = ''

rev = False

for _ in range(Q):

    q = tuple(map(str, input().split()))

    if q[0] == '1':
        rev = (not rev)

    else:
        if (rev and q[1] == '1') or (not rev and q[1] == '2'):
            R = R + q[2]
        else:
            L = q[2] + L 

if rev:
    print( R[::-1] + S[::-1] + L[::-1])
else:
    print( L + S + R )
### BUGGY CODE ###

n,x=map(int, input().split())
lst=list(map(int, input().split()))
lst=lst*2
ans=10**15
s=0
for i in range(n):
    s=i*x
    for j in range(n):
        s+=min(lst[n+j-i:n+j+1])
    ans=min(ans,s)
print(ans)

### FIXED CODE ###

n,x=map(int, input().split())
lst=list(map(int, input().split()))
ms=lst
lst=lst*2
ans=10**15
s=0
for i in range(n):
    s=i*x
    for j in range(n):
        ms[j]=min(ms[j],lst[n+j-i])
        s+=ms[j]
    ans=min(ans,s)
print(ans)
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1,N+1):
    ans += i
print(ans-N)


### FIXED CODE ###

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

# https://atcoder.jp/contests/abc159/submissions/11139418

def main():
    MOD = 998244353

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

    dp = [[[0] * 3 for _ in range(S + 1)] for _ in range(N + 1)]
    dp[0][0][0] = 1

    for i, x in enumerate(a):
        for j in range(S + 1):
            # 選択しない
            prev = dp[i][j]

            dp[i + 1][j][0] = (dp[i + 1][j][0] + prev[0]) % MOD
            dp[i + 1][j][1] = (dp[i + 1][j][1] + prev[0] + prev[1]) % MOD
            dp[i + 1][j][2] = (dp[i + 1][j][2] + prev[0] + prev[1] + prev[2]) % MOD

            # 選択する
            if j - x < 0: continue
            prev_x = dp[i][j - x]

            dp[i + 1][j][1] = (dp[i + 1][j][1] + prev_x[0] + prev_x[1]) % MOD
            dp[i + 1][j][2] = (dp[i + 1][j][2] + prev_x[0] + prev_x[1]) % MOD

    ret = dp[N][S][2]
    print(ret)


if __name__ == '__main__':
    main()

# 0: 開始していないが開始して選択することができる
# 1: 開始しており選択を選べる
# 2: 閉じており選択できない


### FIXED CODE ###

# https://atcoder.jp/contests/abc159/submissions/11139734

def main():
    MOD = 998244353

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

    dp = [0] * (S + 1)

    ret = 0
    for i, x in enumerate(a):
        dp[0] += 1
        if x > S: continue
        ret = (ret + dp[S - x] * (N - i)) % MOD
        for k in range(S - 1, x - 1, -1):
            dp[k] = (dp[k] + dp[k - x]) % MOD

    print(ret)


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

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

food = [[0,0] for i in range(n)]
for i in range(n):
  a,b = map(int,input().split())
  food[i][0] = a
  food[i][1] = b


dp = [[-10000000 for i in range((n+1)*3000)] for j in range(n+1)]
dp[0][0] = 0


for i in range(n):
  a = food[i][0]
  b = food[i][1]
  for j in range(t):
    eat = dp[i][j]+b
    next_time = j+a
    # print(j,next_time)
    if dp[i+1][next_time] < eat:
      dp[i+1][next_time] = eat
    if dp[i+1][j] < dp[i][j]:
      dp[i+1][j] = dp[i][j]

# for i in range(n):
#   for j in range(10,21):
#     print(dp[i][j],end=" ")
#   print()
print(max(dp[-1]))

### FIXED CODE ###

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

orders.sort(key=lambda x:(x[0],-x[1]))
# print(orders)

dp = [[-1e10 for i in range(t+1)] for j in range(n+1)]
dp[0][0] = 0

for i,od in enumerate(orders):
    for j in range(t+1):
        dp[i+1][j] = dp[i][j]
    for j in range(t):
        nt = j+od[0]
        if nt > t-1:
            nt = t
        if dp[i+1][nt] < dp[i][j]+od[1]:
            dp[i+1][nt] = dp[i][j]+od[1]

# for l in dp:
#     print(l[:11])
# print(dp[-1])
print(max(dp[-1]))
### BUGGY CODE ###

from collections import deque
m = 10**9+7
def bfs():
    X, Y = map(int, input().split())
    que = deque([[0, 0]])
    ans = 0
    while que:
        x, y = que.popleft()
        for i, j in ([1,2], [2,1]):
            nx, ny = x+i, y+j
            if nx < X and ny < Y:
                que.append([nx, ny])
            elif nx == X and ny == Y:
                ans += 1
    return ans
print(bfs()%m)

### FIXED CODE ###

import math
import numpy as np

def cmb(n, r, mod):
  r = min(r, n-r)
  return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 
N = 10**6
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

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

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

if (x+y) % 3 == 0:

  A = np.array([[1, 2],[2, 1]])
  b = np.array([x, y])
  N = np.linalg.solve(A, b)
  if N[0].is_integer() == True and N[1].is_integer() == True and N[0] >=0 and N[1] >=0:
      print(cmb(int(N[0]+N[1]),int(N[0]),mod))
  else:
      print(0)
else:
  print(0)
### BUGGY CODE ###

N=int(input())
V=list(map(int,input().split()))
C=list(map(int,input().split()))
from itertools import combinations
List=[]
for i in range(N):
    List.append(i)
ans=[]
for i in range(1,N+1):
    for j in list(combinations(List,i)):
        tmp=0
        for k in j:
            tmp+=V[k]-C[k]
        if tmp<0:
            tmp=0
        ans.append(tmp)    
print(max(ans))

### FIXED CODE ###

N=int(input())
V=list(map(int,input().split()))
C=list(map(int,input().split()))
ans=0
for i in range(N):
    if V[i]>=C[i]:
        ans+=V[i]-C[i]
print(ans)
### BUGGY CODE ###

N = 60
MOD = 10**9 + 7
n = int(input())
l = [[] for _ in range(n)]
# c1 = [0 for _ in range(N)]
c0 = [0 for _ in range(N)]

a = list(map(int,input().split()))
for i in range(n):
    for j in range(N):
        if a[i] & (1 << j) != 0:
            # c1[j] += 1
            l[i].append(True)
        else:
            c0[j] += 1
            l[i].append(False)

ans = 0
for i in range(n-1):
    for j in range(N):
        if not l[i][j]:
            c0[j] -=1
        # else:
        #     c0[j] -=1
    for j in range(N):
        if l[i][j]:
            ans += (1<<j) * c0[j]
        else:
            ans += (1<<j) * (n-i-1-c0[j])
            #ans += (1<<j) * c1[j]

print(ans % MOD)

### FIXED CODE ###

N = 60
MOD = 10**9 + 7
n = int(input())
# c1 = [0 for _ in range(N)]
c1 = [0 for _ in range(N)]

a = list(map(int,input().split()))
for i in range(n):
    for j in range(N):
        if a[i] & (1 << j) != 0:
            c1[j] += 1
        # else:
        #     c1[j] += 1

ans = 0
for i in range(n-1):
    for j in range(N):
        if a[i] & (1 << j) != 0:
            c1[j] -=1
        # else:
        #     c0[j] -=1
    for j in range(N):
        if a[i] & (1 << j) != 0:
            ans += (1<<j) * (n-i-1-c1[j])
        else:
            ans += (1<<j) * c1[j]
            #ans += (1<<j) * c1[j]

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

n,W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
bag = [0 for _ in range(W+1)]
for w,v in a:
  for i in range(min(w,W+1),W+1)[::-1]:
    bag[i] = max(bag[i], bag[i-w] + v)
print(bag[W])  

### FIXED CODE ###

n,W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
bag = [0 for _ in range(W+1)]
for w,v in a:
  for i in range(min(w,W+1),W+1)[::-1]:
    bag[i] = max(bag[i], bag[i-w] + v)
print(bag[W])
### BUGGY CODE ###

#1からaまでのa種類の目がそれぞれ等確率で出るサイコロの期待値を求める関数
def kitaiti(a):
    prob=1/a
    b=0
    for i in range(1,a+1):
        b+=i
    kitaiti=prob*b
    return kitaiti

N,K=map(int,input().split())
D=list(map(int,input().split()))
DE=list(map(kitaiti,D))

e=0
anse=0
for i in range(N-K+1):
    e=0
    for j in range(i,i+K):
        e+=DE[j]
    if anse<e:
        anse=e
    else:
        pass

print(anse)

### FIXED CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))
pE=list(map(lambda i :(1+i)/2,p))
pA=[sum(pE[0:K])]
inter=sum(pE[0:K])
for i in range(0,N-K):
    inter=inter+pE[K+i]-pE[i]
    pA.append(inter)

ans=max(pA)
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
branch = set(tuple(map(int,input().split())) for i in range(m))
que = range(n)
flag = -1
friend = [{0}]

for a,b in branch:
    for i in range(len(friend)):
        if (a in friend[i]) and (b in friend[i]):
            break
        if (a in friend[i]) or (b in friend[i]):
            friend[i].add(a)
            friend[i].add(b)
            if flag >= 0:
                friend[flag] = friend[flag]|friend[i]
                friend.pop(i)
                break
            flag = i
    if flag == -1:
        friend.append({a,b})
    else: flag = -1

len_friend = list(len(i) for i in friend)
print(max(len_friend))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)

class Graph:
    def __init__(self,n,side):
        self.side = side
        self.neighbor = [set() for i in range(n+1)]
        self.visited = [False]*(n+1)
        self.group =[0]*n
        self.product()
    def product(self):
        for a,b in self.side:
            self.neighbor[a].add(b)
            self.neighbor[b].add(a)
    def dfs(self,x,a):
        self.group[a] += 1
        self.visited[x] = True
        for i in self.neighbor[x]:
            if self.visited[i]:continue
            self.dfs(i,a)
    def all_dfs(self):
        a = 0
        for i in range(1,n+1):
            if not self.visited[i]:
                self.dfs(i,a)
                a += 1

n,m = map(int,input().split())
side = list(tuple(map(int,input().split()))for i in range(m))
graph1 = Graph(n,side)
graph1.all_dfs()
print(max(graph1.group))
### BUGGY CODE ###

[n,k]=list(map(int,input().split()))
akarusa=list(map(int,input().split()))

for i in range(k):
    akarusanext=[0]*n
    for j in range(n):
        kagen=max(j-akarusa[j],0)
        jogen=min(j+akarusa[j],n-1)
        for k in range(kagen,jogen+1):
            akarusanext[k]+=1
    akarusa=akarusanext
    if min(akarusa)==n:
        break

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


### FIXED CODE ###

[n,k]=list(map(int,input().split()))
akarusa=list(map(int,input().split()))


for i in range(k):
    imos=[0]*n
    for j in range(n):
        kagen=max(j-akarusa[j],0)
        jogen=min(j+akarusa[j],n-1)
        imos[kagen]+=1
        if jogen+1<n:
            imos[jogen+1]-=1
    akarusanext=imos
    for j in range(1,n):
        akarusanext[j]+=akarusanext[j-1]
    
    if akarusa==akarusanext:
        break
    else:
        akarusa=akarusanext

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