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

def main():
    N = int(input())
    S = []
    for i in range(N):
        s = input()
        s = sorted(s)
        s = ''.join(s)
        S.append(s)
    S.sort()
    SS = sorted(list(set(S)))
    SN = []
    M = len(SS)
    for i in range(M - 1):
        sn = S.index(SS[i + 1])
        SN.append(sn)
        S = S[sn:]
    SN.append(len(S))

    res = 0
    for sn in SN:
        res += sn * (sn - 1) // 2

    print(res)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N = int(input())
    S = []
    for i in range(N):
        s = input()
        s = sorted(s)
        s = ''.join(s)
        S.append(s)
    S.sort()
    SS = sorted(list(set(S)))
    SN = []
    M = len(SS)
    l = 0
    r = len(S)
    for i in range(M):
        for j in range(l, r):
            if S[j] != SS[i]:
                r = j
                break
        SN.append(r - l)
        l = r
        r = len(S)        

    res = 0
    for sn in SN:
        res += sn * (sn - 1) // 2

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

from math import factorial

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

# N,M = 100000,10**9-3
# 素因数分解(小さい方から順に割っていく)
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

# 組み合わせ
def combination(N,M):
    return factorial(N)//(factorial(M)*factorial(N-M))

fs = factorize(M)
fset = list(set(fs))
ans = 1
for f in fset:
    cnt = fs.count(f)
    ans *= combination(cnt+N-1,cnt)
print(ans%(10**9+7))

### FIXED CODE ###

from math import factorial
N, M = map(int,input().split())

# 素因数分解(小さい方から順に割っていく。sqrt(2)まで)
def factorize(n):
    i = 2
    table = [0]
    cnt= [0]
    while i * i <= n:
        while n % i == 0:
            n /= i
            if table[-1] != i:
                table.append(i)
                cnt.append(0)
            cnt[-1] += 1
        i += 1
    if n > 1:
        table.append(n)
        cnt.append(1)
    return table,cnt


fs,ns = factorize(M)
ans = 1
for n in ns[1:]:
    a = 1
    for i in range(N,n+N):
        a *= i
    ans *= a//factorial(n)
print(ans%(10**9+7))
### BUGGY CODE ###

import numpy as np
st=input().split()
N=int(st[0]);K=int(st[1])
S=set([])
st=input().split()
P=[0]*(N+1)
for i in range(N):
    k=int(st[i])
    S.add(k)
    P[k]+=1
out=0
Q=list(sorted(np.array(P)))
while(True):
    if Q[0]==0:
        Q.remove(0)
    else:
        break
for i in range(max([len(S)-K,0])):
    out+=Q[i]
print(out)




### FIXED CODE ###

import numpy as np
st=input().split()
N=int(st[0]);K=int(st[1])
S=set([])
st=input().split()
P=[0]*(N+1)
Q=[0]*(N+1)
for i in range(N):
    k=int(st[i])
    S.add(k)
    P[k-1]+=1
    Q[P[k-1]-1]-=1
    Q[P[k-1]]+=1
out=0
change=0
count=0
if len(S)<=K:
    print(0)
else:
    for i in range(1,N+1):
        flag=1
        for j in range(Q[i]):
            change+=i
            count+=1
            if count==max([len(S)-K,0]):
                flag=0
                break
        if flag==0:
            break
    print(change)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    if i+1 in a:
        print(a[i:].count(i+1))
    else:
        print('0')


### FIXED CODE ###

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

MOD = 998244353
factorial = None
inverse_factorial = None


def modpow(a, p):
    ans = 1
    while p:
        if p&1 == 1:
            ans = (ans*a)%MOD
        a = (a*a)%MOD
        p >>= 1
    return ans


def nCr(n, r):
    if r == 0 or r == n:
        return 1
    return (((factorial[n]*inverse_factorial[n-r])%MOD)*inverse_factorial[r])%MOD


def init_nCr(max_n):
    global factorial, inverse_factorial
    factorial = [1]*(max_n+1)
    inverse_factorial = [0]*(max_n+1)
    for i in range(1, max_n+1):
        factorial[i] = (factorial[i-1]*i)%MOD
        inverse_factorial[i] = modpow(factorial[i], MOD-2)


init_nCr(2*10**5+1)


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M, K = read_ints()
    answer = 0
    for k in range(0, K+1):
        answer = (answer+M*modpow(M-1, N-1-k)*nCr(N-1, k))%MOD
    return answer


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


### FIXED CODE ###

MOD = 998244353
factorial = None
inverse_factorial = None


def modpow(a, p):
    ans = 1
    while p:
        if p&1 == 1:
            ans = (ans*a)%MOD
        a = (a*a)%MOD
        p >>= 1
    return ans


def nCr(n, r):
    if r == 0 or r == n:
        return 1
    return (((factorial[n]*inverse_factorial[n-r])%MOD)*inverse_factorial[r])%MOD


def init_nCr(max_n):
    global factorial, inverse_factorial
    factorial = [1]*(max_n+1)
    inverse_factorial = [0]*(max_n+1)
    for i in range(1, max_n+1):
        factorial[i] = (factorial[i-1]*i)%MOD
        inverse_factorial[i] = modpow(factorial[i], MOD-2)


init_nCr(2*10**5+1)


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M, K = read_ints()
    answer = 0
    for k in range(0, K+1):
        answer = (answer+M*modpow(M-1, N-1-k)*nCr(N-1, k))%MOD
    return answer


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

N, M = map( int, input().split())
A = list( map( int, input().split()))
SUM = [0]
for i in range(N):
    SUM.append(SUM[-1]+A[i])
ans = 0
for l in range(N):
    for r in range(l+1,N+1):
        if (SUM[r] - SUM[l])%M == 0:
            ans += 1
print(ans)

### FIXED CODE ###

N, M = map( int, input().split())
A = list( map( int, input().split()))
D = {0:1}
a = 0
ans = 0
for i in range(N):
    a = (a+A[i])%M
    ans += D.get(a,0)
    D[a] = 1 + D.get(a,0)
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**7)
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())

def main():
    n = II()
    a_s = LI()
    kaizyo = [1]
    kaizyo_append = kaizyo.append
    keta = [0 for i in range(60)]
    ans = 0
    for i in range(60):
        kaizyo_append(kaizyo[i] * 2 % MOD)
    for i in a_s:
        for j, v in enumerate(format(i, 'b')[::-1]):
            keta[j] += int(v)
    for i, v in enumerate(keta):
        c = v * (n-v) % MOD
        ans += c * kaizyo[i] % MOD
        ans = ans % MOD

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


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**7)
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())

def main():
    n = II()
    a_s = LI()
    kaizyo = [1]
    kaizyo_append = kaizyo.append
    keta = [0 for i in range(60)]
    ans = 0
    for i in range(60):
        kaizyo_append(kaizyo[i] * 2 % MOD)
    for i in a_s:
        for j in range(60):
            v, i = i % 2, i // 2
            keta[j] += v
    for i, v in enumerate(keta):
        c = v * (n-v) % MOD
        ans += c * kaizyo[i] % MOD
        ans = ans % MOD

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

a=int(input())
b=list(map(int,input().split()))
x=1;
if 0 in b:
  print(0)
else:
	for i in b:
  		x=x*i
	if x>10**18:
  		print(-1)
	else:
  		print(x)

### FIXED CODE ###

a=int(input())
b=list(map(int,input().split()))
x=1;
if 0 in b:
  print(0)
  exit()
for i in b:
  x=x*i
  if x>10**18:
  	print(-1)
  	exit()
print(x)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = list(map(int, input().split()))


# ans = np.prod(a)
# if ans > 10**18:
#     print(-1)
#     exit()

# print(ans)

ans = 1
for i in a:
    ans = ans*i

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


print(ans)


### FIXED CODE ###

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


ans = 1
if 0 in a:
    print(0)
    exit()

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

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

def tot(x):
	tot= 0
	for d in x:
		tot+= d
	return tot

n = int(input())
start= list(map(int, input().split()))
q= int(input())
for _ in range(q):
	b,c= map(int, input().split())
	for index in range(len(start)):
		if start[index]==b:
			start[index]=c
	print(tot(start))

### FIXED CODE ###

n = int(input())
l= list(map(int, input().split()))
table= {}
for num in l:
	if num in table:
		table[num]+=1
	else:
		table[num]=1

tot= 0
for num in l:
	tot+= num

q= int(input())
for _ in range(q):
	b,c= map(int, input().split())
	if b in table:
		if c in table:
			table[c]+= table[b]
			tot+= table[b]*(c-b)
		else:
			table[c]=table[b]
			tot+= table[b]*(c-b)
	table[b]=0
	print(tot)
### BUGGY CODE ###

H,N =map(int, input().split())
a = [] 
M = 0 
for i in range(N):
	t = list(map(int, input().split()))
	a.append(t)
	M = max(M,t[0])
dp = [100000000]*(H+1+M)
dp[0] = 0
for i in range(H):
	for j,k in a:
		dp[i+j] = min(dp[i+j],dp[i]+k)

print(min(dp[H:]))

### FIXED CODE ###

H,N =map(int, input().split())
a = [] 
M = 0 
for i in range(N):
	t = list(map(int, input().split()))
	a.append(t)
	M = max(M,t[0])
dp = [100000000]*(H+1+M)
dp[0] = 0
for i in range(H):
	for j,k in a:
		dp[i+j] = min(dp[i+j],dp[i]+k)

print(min(dp[H:]))
### BUGGY CODE ###

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

### FIXED CODE ###

N = int(input())
ans = 0
if N%2 == 0:
    ans = N//2 * (N-1)
else:
    ans = (N-1)//2 * N
print(ans)
### BUGGY CODE ###

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

A = A + [0]
K = min(K, 50)
for k in range(K):
    t = [0]*(N+1)
    for i in range(N):
        l = max(i-A[i], 0)
        r = min(i+A[i], N-1)
        t[l] += 1
        t[r+1] -= 1

    S = [0]*N
    S[0] = t[0]
    for i in range(1, N):
        S[i] = S[i-1] + t[i]

    A = S.copy()
print(*S)

### FIXED CODE ###

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

A = A + [0]
K = min(K, 50)
for k in range(K):
    t = [0]*(N+1)
    for i in range(N):
        l = max(i-A[i], 0)
        r = min(i+A[i], N-1)
        t[l] += 1
        t[r+1] -= 1

    S = [0]*N
    S[0] = t[0]
    for i in range(1, N):
        S[i] = S[i-1] + t[i]

    A = S.copy()
print(*S)
### BUGGY CODE ###

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

A_sum = [0] + [sum(A[:i+1]) for i in range(len(A))]
B_sum = [0] + [sum(B[:i+1]) for i in range(len(B))]

res = 0
for i in range(len(A_sum)):
    low = 0
    high = len(B_sum)
    while high - low > 1:
        mid = (low + high) // 2
        if A_sum[i] + B_sum[mid] <= K:
            low = mid
        else:
            high = mid
    if A_sum[i] + B_sum[low] <= K:
        res = max(res, i + low)

print(res)


### FIXED CODE ###

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

A_sum = [0]
for i in range(N):
    A_sum.append(A_sum[i] + A[i])
B_sum = [0]
for i in range(M):
    B_sum.append(B_sum[i] + B[i])
B_sum.append(10**10)

res = 0
for i in range(len(A_sum)):
    low = 0
    high = len(B_sum)
    while high - low > 1:
        mid = (low + high) // 2
        if A_sum[i] + B_sum[mid] <= K:
            low = mid
        else:
            high = mid
    if A_sum[i] + B_sum[low] <= K:
        res = max(res, i + low)

print(res)
### BUGGY CODE ###

import sys 
sys.setrecursionlimit(10**6)
s = input()
def dfs(t):
    if t==s:
        return True
    if len(t)>=len(s):
        return False
    for i in ['dream', 'dreamer', 'erase', 'eraser']:
        if dfs(t+i):
            return True
    return False
if dfs(''):
    print('YES')
else:
    print('NO')

### FIXED CODE ###

import sys 
sys.setrecursionlimit(10**6)
s = input()
def dfs(s):
    while True:
        f = True
        for i in ['erase', 'eraser', 'dream', 'dreamer']:
            if s[-len(i):]==i:
                s = s[:-len(i)]
                if s=='':
                    return True
                f = False
        if f: return False
    
if dfs(s):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

import collections
N = int(input())

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


for i in range(N):
    ans = 0
    a_slice = a[:i] + a[i+1:]
    c = collections.Counter(a_slice)
    counter = c.most_common()
    for j in range(len(counter)):
        ans += int(counter[j][1] * (counter[j][1] - 1) / 2)
    
    print(ans)

### FIXED CODE ###

import numpy as np

c = np.zeros(int(2e5))
c_1 = np.ones(int(2e5))

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

for i in range(n):
    c[a[i] - 1] += 1

ans = int(sum(c * (c - c_1) / 2))

for i in range(n):
    print(ans - int(c[a[i]-1]-1))
### BUGGY CODE ###

R, C, K = map(int, input().split())

grid = [[0 for c in range(C)] for r in range(R)]

for k in range(K):
    r, c, v = map(int, input().split())
    grid[r-1][c-1] = v

dp = [[[-1000 for c in range(C)] for r in range(R)] for k in range(4)]

if grid[0][0] > 0:
    dp[1][0][0] = grid[0][0]
dp[0][0][0] = 0

for r in range(R):
    for c in range(C):
        if c >= 1:
            dp[0][r][c] = max(dp[0][r][c], dp[0][r][c-1])
            dp[1][r][c] = max(dp[1][r][c], dp[1][r][c-1])
            dp[2][r][c] = max(dp[2][r][c], dp[2][r][c-1])
            dp[3][r][c] = max(dp[3][r][c], dp[3][r][c-1])
        if r >= 1:
            dp[0][r][c] = max(dp[0][r][c], dp[0][r-1][c], dp[1][r-1][c], dp[2][r-1][c], dp[3][r-1][c])
        v = grid[r][c]
        if v > 0:
            if c >= 1:
                dp[1][r][c] = max(dp[1][r][c], dp[0][r][c-1] + v)
                dp[2][r][c] = max(dp[2][r][c], dp[1][r][c-1] + v)
                dp[3][r][c] = max(dp[3][r][c], dp[2][r][c-1] + v)
            if r >= 1:
                dp[1][r][c] = max(dp[1][r][c], dp[0][r-1][c]+v, dp[1][r-1][c]+v, dp[2][r-1][c]+v, dp[3][r-1][c]+v)

print(max(dp[0][R-1][C-1], dp[1][R-1][C-1], dp[2][R-1][C-1], dp[3][R-1][C-1]))


### FIXED CODE ###

R, C, K = map(int, input().split())

grid = [[0 for c in range(C)] for r in range(R)]

for k in range(K):
    r, c, v = map(int, input().split())
    grid[r-1][c-1] = v

dp = [[[-1000 for c in range(C)] for r in range(R)] for k in range(4)]

if grid[0][0] > 0:
    dp[1][0][0] = grid[0][0]
dp[0][0][0] = 0

for r in range(R):
    for c in range(C):
        if c >= 1:
            dp[0][r][c] = max(dp[0][r][c], dp[0][r][c-1])
            dp[1][r][c] = max(dp[1][r][c], dp[1][r][c-1])
            dp[2][r][c] = max(dp[2][r][c], dp[2][r][c-1])
            dp[3][r][c] = max(dp[3][r][c], dp[3][r][c-1])
        if r >= 1:
            dp[0][r][c] = max(dp[0][r][c], dp[0][r-1][c], dp[1][r-1][c], dp[2][r-1][c], dp[3][r-1][c])
        v = grid[r][c]
        if v > 0:
            if c >= 1:
                dp[1][r][c] = max(dp[1][r][c], dp[0][r][c-1] + v)
                dp[2][r][c] = max(dp[2][r][c], dp[1][r][c-1] + v)
                dp[3][r][c] = max(dp[3][r][c], dp[2][r][c-1] + v)
            if r >= 1:
                dp[1][r][c] = max(dp[1][r][c], dp[0][r-1][c]+v, dp[1][r-1][c]+v, dp[2][r-1][c]+v, dp[3][r-1][c]+v)

print(max(dp[0][R-1][C-1], dp[1][R-1][C-1], dp[2][R-1][C-1], dp[3][R-1][C-1]))
### BUGGY CODE ###

from collections import deque
INF = float('inf')
import sys
input = sys.stdin.readline
N, K = map(int, input().split())

H = deque(list(map(int, input().split())))
max_K = 100
for _ in range(max_K):
  H.append(INF)

dp = [INF] * (N + max_K)
dp[0] = 0

for n in range(N):
  for offset in range(1, K + 1):
    new_index = n + offset
    cost = dp[n] + abs(H[n] - H[new_index])
    if (dp[new_index] > cost):
      dp[new_index] = cost

print(dp[N - 1])


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int, input().split())

# H = deque(list(map(int, input().split())))
max_K = 100
H = list(map(int, input().split()))
H += [0] * max_K
# for _ in range(max_K):
#   H.append(0)

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

for n in range(N):
  for offset in range(1, K + 1):
    new_index = n + offset
    cost = dp[n] + abs(H[n] - H[new_index])
    if (dp[new_index] > cost):
      dp[new_index] = cost

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

n,q = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n)]
D = [int(input()) for i in range(q)]

E = []
F = {}
for i in range(n):
    s = A[i][0]
    t = A[i][1]
    x = A[i][2]
    F[x] = 0
    E.append([s-x, x, 1])
    E.append([t-x, x, -1])
E.append([10**10, 10**10, 1])

E.sort()

# print(E)

from heapq import heappush, heappop
Q = []

for i in range(q):
    j = 0
    while E[j][0] <= D[i]:
        if E[j][2] == 1:
            F[E[j][1]] = 1
            heappush(Q, E[j][1])
        else:
            F[E[j][1]] = 0
        j += 1
    
    while len(Q) > 0:
        ans = heappop(Q)
        if F[ans] == 1:
            heappush(Q, ans)
            break
    if len(Q) == 0:
        print(-1)
    else:
        print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,q = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n)]
D = [int(input()) for i in range(q)]

E = []
F = {}
for i in range(n):
    s = A[i][0]
    t = A[i][1]
    x = A[i][2]
    F[x] = 0
    E.append((s-x, x, 1))
    E.append((t-x, x, -1))
E.append((10**10, 10**10, 1))

E.sort()

# print(E)

from heapq import heappush, heappop
Q = []

j = 0
for i in range(q):
    # print(F,j)
    while E[j][0] <= D[i]:
        if E[j][2] == 1:
            F[E[j][1]] += 1
            heappush(Q, E[j][1])
        else:
            F[E[j][1]] -= 1
        j += 1
    
    while len(Q) > 0 and F[Q[0]] == 0:
        _ = heappop(Q)
    if len(Q) == 0:
        print(-1)
    else:
        print(Q[0])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
n, q = map(int, input().split(' '))
inf = [[] for _ in range(n+1)]
ab = [[x for x in map(int, input().split(' '))] for _ in range(n-1)]
for a,b in ab:
    inf[a].append(b)
    inf[b].append(a)
point = [0]*(n+1)
px = [[x for x in map(int, input().split(' '))] for _ in range(q)]
for p,x in px:
    point[p] += x
def add_p(num, oya):
    for k in inf[num]:
        if k != oya:
            point[k] += point[num]
            add_p(k, num)  
for i in inf[1]:
    point[i] += point[1]
    add_p(i,1)
point.pop(0)
print(*point)

### FIXED CODE ###

def main():
    n, q = map(int, input().split(' '))
    import sys
    from collections import deque
    sys.setrecursionlimit(10**7)

    visit = [True for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    next_visit = deque()
    next_visit.append(0)
    visit[0] = False
    counter = 1
    while counter < n:
        t = next_visit.pop()
        for s in dic[t]:
            if visit[s]:
                point[s] += point[t]
                visit[s] = False
                counter += 1
                next_visit.append(s)
    print(*point)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

a,b,k = map(int, input().split())

ans = []

for i in range(a,b+1):
  if a<= i <= a+k-1 or b-k+1 <= i <= b:
    ans.append(i)

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


### FIXED CODE ###

a,b,k = map(int, input().split())

A = list(range(a,min(a+k,b+1)))
B = list(range(max(a,b-k+1),b+1))
ans = list(set(A)|set(B))
ans.sort()
for i in range(len(ans)):
  print(ans[i])
### BUGGY CODE ###

import numpy as np
import sys
sys.setrecursionlimit(20000000)

def calculate(h, w, arr):
    L = np.zeros([h, w])
    U = np.zeros([h, w])
    D = np.zeros([h, w])
    R = np.zeros([h, w])

    for ih in range(h):
        for iw in range(w):
            if ih == 0:
                U[ih][iw] = 1
            if iw == 0:
                L[ih][iw] = 1

            if arr[ih][iw] == "#":
                L[ih][iw] = 0
                U[ih][iw] = 0

            else:
                if iw > 0:
                    L[ih][iw] = L[ih][iw - 1] + 1
                if ih > 0:
                    U[ih][iw] = U[ih - 1][iw] + 1


    for ih in range(h):
        for iw in range(w):
            rih = h - 1 - ih
            riw = w - 1 - iw

            if rih == h - 1:
                D[rih][riw] = 1
            if riw == w - 1:
                R[rih][riw] = 1

            if arr[rih][riw] == "#":
                D[rih][riw] = 0
                R[rih][riw] = 0
            else:
                if riw < w - 1:
                    R[rih][riw] = R[rih][riw + 1] + 1
                if rih < h - 1:
                    D[rih][riw] = D[rih + 1][riw] + 1

    max = 0
    for ih in range(h):
        for iw in range(w):
            if arr[ih][iw] == "#":
                continue
            value = L[ih][iw] + R[ih][iw] + U[ih][iw] + D[ih][iw] - 3
            if value > max:
                max = value
    print(int(max))


S = input().split(" ")
H = int(S[0])
W = int(S[1])

arr = []
for i in range(H):
    q = list(input())
    arr.append(q)

calculate(H, W, arr)


### FIXED CODE ###

def calculate(h, w, arr):
    L = [[0]*w for i in range(h)]
    U = [[0]*w for i in range(h)]
    D = [[0]*w for i in range(h)]
    R = [[0]*w for i in range(h)]

    for ih in range(h):
        for iw in range(w):
            if ih == 0:
                U[ih][iw] = 1
            if iw == 0:
                L[ih][iw] = 1

            if arr[ih][iw] == 1:
                L[ih][iw] = 0
                U[ih][iw] = 0

            else:
                if iw > 0:
                    L[ih][iw] = L[ih][iw - 1] + 1
                if ih > 0:
                    U[ih][iw] = U[ih - 1][iw] + 1

            rih = h - 1 - ih
            riw = w - 1 - iw

            if rih == h - 1:
                D[rih][riw] = 1
            if riw == w - 1:
                R[rih][riw] = 1

            if arr[rih][riw] == 1:
                D[rih][riw] = 0
                R[rih][riw] = 0
            else:
                if riw < w - 1:
                    R[rih][riw] = R[rih][riw + 1] + 1
                if rih < h - 1:
                    D[rih][riw] = D[rih + 1][riw] + 1

    max = 0
    for ih in range(h):
        for iw in range(w):
            value = L[ih][iw] + R[ih][iw] + U[ih][iw] + D[ih][iw] - 3
            if value > max:
                max = value
    print(int(max))


S = input().split(" ")
H = int(S[0])
W = int(S[1])

arr = []
for i in range(H):
    q = input()
    tmp = []
    for qs in q:
        if qs == "#":
            tmp.append(1)
        if qs == ".":
            tmp.append(0)
    arr.append(tmp)

calculate(H, W, arr)
### BUGGY CODE ###

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

s=input()
lr=[]

for _ in range(q):
    l,r=map(int,input().split())
    lr.append((l,r))
    
def count_x(s):
    count=0
    for i in range(len(s)):
        if s[i]=="x":
            count+=1
    return count

for l,r in lr:
    total=0
    print(count_x(s[l-1:r].replace("AC","x")))

### FIXED CODE ###

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

s=input()
lr=[]
for _ in range(q):
    l,r=map(int,input().split())
    lr.append((l,r))

data=[0]
count=0
for i in range(1,len(s)):
    if s[i-1]=="A" and s[i]=="C":
        count+=1
    data.append(count)

for l,r in lr:
    print(data[r-1]-data[l-1])
### BUGGY CODE ###

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

max_v = 0
max_i = 0
for x in range(n - k + 1):
    s = sum([p[x+i] for i in range(k)])
    if max_v < s:
        max_v = s
        max_i = x
sums = 0.0
for x in p[max_i:max_i+k]:
    sums += (x + 1) / 2

print("{:.6f}".format(sums))

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int,input().split()))
b = [(1 + p[i])/2 for i in range(n)]

ttl = sum(b[:k])
res = ttl
for i, v in enumerate(b[k:]):
    ttl += v - b[i]
    res = max(res, ttl)

print("{:.10f}".format(res))