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

# import numpy as np

N, M = map(int, input().split())
# a = np.array(list(map(int, input().split())))
a = list(map(int, input().split()))

for _ in range(M):
    # a[a.argmax()] //= 2
    a.sort()
    a[-1] //= 2
print(sum(a))

### FIXED CODE ###

import heapq

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

q = []
for i in range(N):
    # 最も大きい値を取り出して1/2したいので、ここで反転させておき、最終的に足す時に戻す
    heapq.heappush(q, -a[i])
for i in range(M):
    l = heapq.heappop(q)
    heapq.heappush(q, -(-l//2))
print(-sum(q))
### BUGGY CODE ###

n,k = list(map(int, input().split()))
org = list(map(int, input().split()))
h = [10**10 for _ in range(n+k+1)]
for i in range(n):
  h[i] = org[i] 
dp = [10**10 for _ in range(n+k+1)]

dp[0] = 0
for i in range(n):
  for j in range(1, k+1):
    dp[i+j] = min([dp[i+j], dp[i] + abs(h[i] - h[i+j])])
print(dp[n-1])

### FIXED CODE ###

n,k = list(map(int, input().split()))
org = list(map(int, input().split()))
h = [10**10 for _ in range(n+k+1)]
for i in range(n):
  h[i] = org[i] 
dp = [10**10 for _ in range(n+k+1)]

dp[0] = 0
for i in range(n):
  for j in range(1, k+1):
    dp[i+j] = min([dp[i+j], dp[i] + abs(h[i] - h[i+j])])
print(dp[n-1])
### BUGGY CODE ###

N = int(input())  # 1 <= N <= 4000
S = input()  # [RGB]{N}
L = {
    'R': [i for i, v in enumerate(S) if v == 'R'],
    'G': [i for i, v in enumerate(S) if v == 'G'],
    'B': [i for i, v in enumerate(S) if v == 'B']
}

ans = 0
for i in range(N):
    for j in range(i+1, N):
        if S[i] != S[j]:
            other = list({'R', 'G', 'B'} - {S[i], S[j]})[0]
            ans += len([k for k in L[other] if (k > j) and (j - i != k - j)])
print(ans)

### FIXED CODE ###

N = int(input())  # 1 <= N <= 4000
S = input()  # [RGB]{N}
L = {
    'R': tuple(i for i, v in enumerate(S) if v == 'R'),
    'G': tuple(i for i, v in enumerate(S) if v == 'G'),
    'B': tuple(i for i, v in enumerate(S) if v == 'B')
}
R_length = len(L['R'])
G_length = len(L['G'])
B_length = len(L['B'])

ans = R_length * G_length * B_length
for i in range(N):
    for j in range(i+1, N):
        k = j + j - i
        if k >= N:
            break
        if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
            ans -= 1
print(ans)
### BUGGY CODE ###

n, m, k = list(map(int, input().split(" ")))
a = list(map(int, input().split(" ")))
b = list(map(int, input().split(" ")))

# dp = [[[-1 for _ in range(k)] for _ in range(m+1)] for _ in range(n+1)]

if k >= sum(a) + sum(b):
	print (m+n)
# r = helper(0, 0, a, b, k, dp)
else:
	r = 0
	stack = [(0, 0, k)]
	dic = {}
	dic[(0, 0)] = k

	while len(stack) != 0:
		i, j, kk = stack.pop()
		if i == n:
			if j < m:
				if b[j] > kk:
					r = max(r, i + j)
					continue
				if b[j] <= kk:
					if (i, j+1) not in dic:
						stack.append((i, j+1, kk - b[j]))
						dic[(i, j+1)] = kk - b[j]
					elif (kk - b[j]) > dic[(i, j+1)]:
						stack.append((i, j+1, kk - b[j]))
						dic[(i, j+1)] = kk - b[j]
		elif j == m:
			if i < n:
				if a[i] > kk:
					r = max(r, i+j)
					continue
				if a[i] <= kk:
					if (i+1, j) not in dic:
						stack.append((i+1, j, kk - a[i]))
						dic[(i+1, j)] = kk - a[i]
					elif (kk - a[i]) > dic[(i+1, j)]:
						stack.append((i+1, j, kk - a[i]))
						dic[(i+1, j)] = kk - a[i]
		else:
			if min(a[i], b[j]) > kk:
				r = max(r, i + j)
			if a[i] <= kk:
				if (i+1, j) not in dic:
					stack.append((i+1, j, kk-a[i]))
					dic[(i+1, j)] = kk - a[i]
				elif dic[(i+1, j)] < (kk - a[i]):
					stack.append((i+1, j, kk-a[i]))
					dic[(i+1, j)] = kk - a[i]
			if b[j] <= kk:
				if (i, j+1) not in dic:
					stack.append((i, j+1, kk - b[j]))
					dic[(i, j+1)] = kk - b[j]
				elif dic[(i, j+1)] < (kk - b[j]):
					stack.append((i, j+1, kk - b[j]))
					dic[(i, j+1)] = kk - b[j]

	print (str(r))



### FIXED CODE ###

n, m, k = list(map(int, input().split(" ")))
a = list(map(int, input().split(" ")))
b = list(map(int, input().split(" ")))

sa = [0]
for i in range(n):
	if (sa[-1] + a[i]) > k:
		break
	sa.append(sa[-1] + a[i])
sb = [0]
for i in range(m):
	if (sb[-1] + b[i]) > k:
		break
	sb.append(sb[-1] + b[i])

r = 0
j = 0
cur = sa[-1]

for i in range(len(sa)-1, -1, -1):
	while j < len(sb):
		if sa[i] + sb[j] > k:
			break
		j += 1
	r = max(r, i + j - 1)
print (r)
### BUGGY CODE ###

from math import gcd
from functools import reduce
n = int(input())
a = list(map(int, input().split()))

tmp = [set() for _ in range(10**6+1)]
for i in range(2, 10**6//2+1):
    for j in range(i, 10**6+1, i):
        tmp[j].add(i)

# acc = [set() for _ in range(n)]
# for i, v in enumerate(a):
#     if i == 0:
#         acc[i] = tmp[v]
#     else:
#         acc[i] = acc[i-1] | tmp[v]

flag = False
for i in range(n-1):
    if len(tmp[a[i]] & tmp[max(a)]) > 0:
        flag = True
        break

if flag == False:
    print("pairwise coprime")
else:
    if reduce(gcd, a) == 1:
        print("setwise coprime")
    else:
        print("not coprime")

### FIXED CODE ###

from math import gcd
from functools import reduce
n = int(input())
a = list(map(int, input().split()))

# sieve[n]は、その数を最初にふるいに落とした数を格納
def prime_factor_table(n):
    # sieveとはふるいの意味
    sieve = [i for i in range(n+1)]
    # n以下の整数を最初にふるい落とす数(√n以下に必ず存在)を求める.
    for i in range(2, int(n**0.5)+1):
        if sieve[i] == i:
            for j in range(2*i, n+1, i):
                if sieve[j] == j:
                    sieve[j] = i
    return sieve

sieve = prime_factor_table(10**6+1)

def prime_factor(n):
    # 素数は英語でprime number
    prime = set()
    while n > 1:
        prime.add(sieve[n])
        n //= sieve[n]
    return prime

for i, v in enumerate(a):
    if i == 0:
        tmp = prime_factor(v)
    else:
        prime = prime_factor(v)
        for j in prime:
            if j in tmp:
                if reduce(gcd, a) == 1:
                    print("setwise coprime")
                    exit()
                else:
                    print("not coprime")
                    exit()
            tmp.add(j)
print("pairwise coprime")
### BUGGY CODE ###

import itertools
n,m,q=map(int, input().split())
 
tmp = 0
max = 0
c = []
 
for i in range(q):
    c.append([int(j) for j in input().split()])
 
nums = range(1, m + 1)
for retsu in itertools.combinations_with_replacement(nums, n): 
    for i in range(q):
        if int(retsu[c[i][1]-1]) - int(retsu[c[i][0]-1]) == c[i][2]:
            tmp = tmp + c[i][3]
        if max < tmp:
            max = tmp
    tmp = 0
 
print(max)

### FIXED CODE ###

import itertools
n,m,q=map(int, input().split())
 
tmp = 0
max = 0
a = []
b = []
c = []
d = []
 
for i in range(q):
  A, B, C, D = map(int, input().split())
  a.append(A)
  b.append(B)
  c.append(C)
  d.append(D)
 
nums = range(1, m + 1)
 
for retsu in itertools.combinations_with_replacement(nums, n): 
    for i in range(q):
        if int(retsu[b[i]-1]) - int(retsu[a[i]-1]) == c[i]:
            tmp = tmp + d[i]
        if max < tmp:
            max = tmp
    tmp = 0
 
print(max)
### BUGGY CODE ###

K = int(input())
import math
from functools import reduce
def gcd_list(numbers):
    return reduce(math.gcd, numbers)
tmp_sum = 0
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      tmp_list = [i,j,k]
      tmp_sum += gcd_list(tmp_list)
print(tmp_sum)


### FIXED CODE ###

K = int(input())
import math
from functools import reduce
def gcd_list(numbers):
    return reduce(math.gcd, numbers)
tmp_sum = 0
for i in range(1,K+1):
  for j in range(i,K+1):
    for k in range(j,K+1):
      if i != j and j != k:
        tmp_list = [i,j,k]
        tmp_sum += gcd_list(tmp_list)*6
      elif i == j and j == k:
        tmp_list = [i,j,k]
        tmp_sum += gcd_list(tmp_list)
      else:
        tmp_list = [i,j,k]
        tmp_sum += gcd_list(tmp_list)*3
print(tmp_sum)
### BUGGY CODE ###

n,m,l=map(int,input().split())

#基本的にワーシャルフロイドの場合、行列式のリストで距離を保管する

d = [[10**20 for i in range(n+1)] for i in range(n+1)]

for i in range(m):
    x,y,z = map(int,input().split())
    #有向グラフか無向グラフかによってここで場合わけが生じる
    d[x][y] = z
    d[y][x] = z
    
for i in range(n+1):
    d[i][i] = 0 #自身のところに行くコストは０

def warshall_floyd(d):
    #d[i][j]=i番目の頂点からj番目の頂点までの最短距離
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

d=warshall_floyd(d)

e = [[10**20 for i in range(n+1)] for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,n+1):
        if d[i][j]<=l:
            e[i][j]=1
for i in range(n+1):
    e[i][i]=0
    
f=warshall_floyd(e)

q=int(input())

for _ in range(q):
    s,t=map(int,input().split())
    if e[s][t]<10**20:
        print(e[s][t]-1)
    else:
        print(-1)
    



### FIXED CODE ###

n,m,l=map(int,input().split())

#基本的にワーシャルフロイドの場合、行列式のリストで距離を保管する
from scipy.sparse import csr_matrix
from scipy.sparse import csgraph 
d = [[10**12 for i in range(n+1)] for i in range(n+1)]
for i in range(m):
    x,y,z = map(int,input().split())
    #有向グラフか無向グラフかによってここで場合わけが生じる
    d[x][y] = z
    d[y][x] = z
    
for i in range(n+1):
    d[i][i] = 0 #自身のところに行くコストは０
q=int(input())
que=[]
for _ in range(q):
    s,t=map(int,input().split())
    que.append((s,t))
       
csr=csr_matrix(d)
K=csgraph.shortest_path(csr,method="FW",directed=True)
e = [[10**12 for i in range(n+1)] for i in range(n+1)]

for i in range(1,n+1):
    for j in range(1,n+1):
        if K[i][j]<=l:
            e[i][j]=1
            
for i in range(n+1):
    e[i][i]=0
    

A=csr_matrix(e)
ANS=csgraph.shortest_path(A,method="FW",directed=True)

for some in que:
    s,t=some[0],some[1]
    if int(ANS[s][t])<10**12:
        print(int(ANS[s][t])-1)
    else:
        print(-1)
### BUGGY CODE ###

from collections import Counter
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


def f(c1, c2, c3):
    if dp[c1][c2][c3] != -1:
        return dp[c1][c2][c3]

    s = c1 + c2 + c3

    res = n
    if c1 > 0:
        res += f(c1 - 1, c2, c3) * c1
    if c2 > 0:
        res += f(c1 + 1, c2 - 1, c3) * c2
    if c3 > 0:
        res += f(c1, c2 + 1, c3 - 1) * c3
    res /= s
    dp[c1][c2][c3] = res
    return res


n = int(input())
a = tuple(map(int, input().split()))
c = Counter(a)

c1 = c[1]
c2 = c[2]
c3 = c[3]

dp = tuple(
    tuple(
        [-1] * (n + 1) for _ in range(n + 1)
    ) for _ in range(n + 1))
dp[0][0][0] = 0
# dp[x][y][z]:=1,2,3個の皿がx,y,z残っているときの期待値

print(f(c1, c2, c3))

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p


### FIXED CODE ###

def main():
    from collections import Counter

    n = int(input())
    a = tuple(int(x) for x in input().split())

    c = Counter(a)
    c1 = c[1]
    c2 = c[2]
    c3 = c[3]

    x1 = 310 ** 2
    x2 = 310

    dp = [0.0] * (310 ** 3)
    dp[0] = 0.0
    # dp[x * x1 + y * x2 + z]:=1,2,3個の皿がx,y,z残っているときの期待値

    for r3 in range(c3 + 1):
        d3 = c3 - r3
        for r2 in range(c2 + d3 + 1):
            for r1 in range(c1 + d3 + c2 - r2 + 1):
                ind = r1 * x1 + r2 * x2 + r3
                if ind != 0:
                    dp[ind] = (n \
                               + (dp[ind - x1] * r1 if r1 > 0 else 0) \
                               + (dp[ind + x1 - x2] * r2 if r2 > 0 else 0) \
                               + (dp[ind + x2 - 1] * r3 if r3 > 0 else 0)) \
                              / (r1 + r2 + r3)

    print(dp[c1 * x1 + c2 * x2 + c3])


if __name__ == '__main__':
    main()

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p

# if mainの追加
# 初期値None->-1.0にした
# checked配列を辞めた
# チェック済みかどうかの判定を-1.0と一致するかの比較にした

# カウントはCounterを使う方が速い
# 1次元にした
# resの加算を複数回に分けると
# 三項演算子より遅くなる
# 再帰関数を辞めた
### BUGGY CODE ###

import sys
input = sys.stdin.readline

#n=list(map(int,input().split()))
n = int(input()) 
num = [input() for i in range(n)] 


for i in range(n):
    print(max(num[:i]+num[i+1:]))
    
    

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
n = int(input()) 
num = [input() for _ in range(n)] 
num = np.array(num).astype("int64")
#ma=max(num)
#ind=num.index(ma)
sorted_num=sorted(num)
ma=sorted_num[-1]
ma2=sorted_num[-2]
for i in range(n):
    if ma != num[i]:
        print(str(ma).strip())
    else:
        print(str(ma2).strip())
### BUGGY CODE ###

import math, sys


def erastos(n):
    n += 1
    try:
        v = [0 if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else 1 for i in range(n)]
        v[0] = v[1] = 0
        v[2] = v[3] = v[5] = 1
    except IndexError:
        return [0, 0, 1, 1, 0, 1][:n]
    sqrt = math.sqrt(n)
    for serial in range(3, n, 2):
        if serial > sqrt:
            return v
        for s in range(serial ** 2, n, serial):
            v[s] = 0
if __name__ == '__main__':
    while True:
        try:
            n = int(input())
        except:
            break
        v = erastos(n)
        primes = [i for i, b in enumerate(v) if b == True]
        print(len(primes))

### FIXED CODE ###

import sys

primes = [1] * 500000
primes[0] = 0

for i in range(3, 1000, 2):
    if primes[i // 2]:
        primes[(i * i) // 2::i] = [0] * len(primes[(i * i) // 2::i])

for i in sys.stdin:
    n = int(i)
    if n < 4:
        print(n - 1)
    else:
        print(sum(primes[:(n + 1) // 2]) + 1)
### BUGGY CODE ###

from bisect import bisect_left,bisect_right

TO_ACII = 97

N = int(input())
S = ["0"] + list(input())
Q = int(input())

ABC = [[]for i in range(0,26,1)]#該当文字a:0 b:1 ...z:26 が何文字目に出てきたかを保持する配列

for i in range(1,N+1,1):
    ABC[ord(S[i])-TO_ACII].append(i)

ans = []
for i in range(0,Q,1):
    q = list(input().split())
    if q[0]=="1":#文字変更
        changed = S[int(q[1])]
        ABC[ord(changed)-TO_ACII].pop(bisect_left(ABC[ord(changed)-TO_ACII],int(q[1])))
        ABC[ord(q[2])-TO_ACII].insert(bisect_left(ABC[ord(q[2])-TO_ACII],int(q[1])),int(q[1]))
        S[int(q[1])]=q[2]
    else:
        tmpans = 0
        for i in range(0,26,1):

            if bisect_right(ABC[i],int(q[1])-1)<len(ABC[i]) and int(q[2]) >= ABC[i][bisect_right(ABC[i],int(q[1])-1)]:
                tmpans+=1
        ans.append(tmpans)

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


### FIXED CODE ###

from bisect import bisect_left,bisect_right

TO_ACII = 97

N = int(input())
S = ["0"] + list(input())
Q = int(input())

ABC = [[]for i in range(0,26,1)]#該当文字a:0 b:1 ...z:26 が何文字目に出てきたかを保持する配列

for i in range(1,N+1,1):
    ABC[ord(S[i])-TO_ACII].append(i)

ans = []
for i in range(0,Q,1):
    q = list(input().split())
    if q[0]=="1":#文字変更
        changed = S[int(q[1])]
        ABC[ord(changed)-TO_ACII].pop(bisect_left(ABC[ord(changed)-TO_ACII],int(q[1])))
        ABC[ord(q[2])-TO_ACII].insert(bisect_left(ABC[ord(q[2])-TO_ACII],int(q[1])),int(q[1]))
        S[int(q[1])]=q[2]
    else:
        tmpans = 0
        for i in range(0,26,1):

            if bisect_right(ABC[i],int(q[1])-1)<len(ABC[i]) and int(q[2]) >= ABC[i][bisect_right(ABC[i],int(q[1])-1)]:
                tmpans+=1
        ans.append(tmpans)

for i in range(0,len(ans),1):
    print(ans[i])
### BUGGY CODE ###

L = input()
n1 = L.count('1')

m=0
d=[]
for i, c in enumerate(reversed(L)):
    if c=='1':
        m+=1
        d.append((i, n1-m))

mod = 10**9+7
s = 2**n1 % mod
for dd in d:
    s += ((3**dd[0] % mod) * (2**dd[1] % mod)) % mod

print(s % mod)


### FIXED CODE ###

def modpow(a, n, mod):
    res=1
    while n>0:
        if n & 1:
            res = res * a % mod
        n = n>>1
        a = a * a % mod
    return res


L = input()
n1 = L.count('1')

m=0
d=[]
for i, c in enumerate(reversed(L)):
    if c=='1':
        m+=1
        d.append((i, n1-m))

mod = 10**9+7
s = modpow(2, n1, mod)
for dd in d:
    s += (modpow(3,dd[0],mod) * modpow(2,dd[1],mod)) % mod

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

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

def mod_inverse(a, p):
    mod = 1
    p_bin = bin(p-2)
    for i in range(len(p_bin) - 1, 1, -1):
        if i == len(p_bin) - 1:
            mul = a
            mul %= p
            mod *= (mul ** int(p_bin[i]))
            mod %= p
        else:
            mul = mul ** 2
            mul %= p
            mod *= (mul ** int(p_bin[i]))
            mod %= p
    return mod

def combination(n, k, p):
    a = 1
    for i in range(n, n - k, -1):
        a *= i
        a %= p
    b = 1
    for i in range(k):
        b *= (i + 1)
        b %= p
    return (a * mod_inverse(b, p)) % p

a.sort()
max_x = 0
min_x = 0
for i in range(n - k + 1):
    temp = combination(k - 1 + i, k - 1, mod)
    max_x += (temp * a[k - 1 + i])
    min_x += (temp * a[n - k - i])
    max_x %= mod
    min_x %= mod
print((max_x - min_x) % mod)

### FIXED CODE ###

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

fact = [1] * (n + 1)
revfact = [1] * (n + 1)
for i in range(n):
    fact[i + 1] = ((i + 1) * fact[i]) % mod
revfact[n] = pow(fact[n], mod - 2, mod)
for i in reversed(range(n)):
    revfact[i] = ((i + 1) * revfact[i + 1]) % mod
def combination(n, k, p):
    return (fact[n] * revfact[k] * revfact[n - k]) % p

a.sort()
max_x = 0
min_x = 0
for i in range(n - k + 1):
    temp = combination(k - 1 + i, k - 1, mod)
    max_x += (temp * a[k - 1 + i])
    min_x += (temp * a[n - k - i])
    max_x %= mod
    min_x %= mod
print((max_x - min_x) % mod)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
lr = [0] * Q
for i in range(Q):
  lr[i] = list(map(int, input().split()))

b, t = 0, [0]*N
v = S.find('AC', b)
while v != -1:
    t[v] = 1
    b += 2
    v = S.find('AC', b)

for i in range(Q):
  st = lr[i][0] - 1
  if S[st] == 'C':
    k = sum(t[st:lr[i][1]]) - 1
  else:
    k = sum(t[st:lr[i][1]])
  print(k)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
lr = [0] * Q
for i in range(Q):
  lr[i] = list(map(lambda x: int(x) - 1, input().split()))
 
b, t = 0, [0]*N
for i in range(1, N):
  if S[i-1] == 'A' and S[i] == 'C':
    t[i] = t[i-1] + 1
  else: t[i] = t[i-1]
 
for i in range(Q):
  print(t[lr[i][1]] - t[lr[i][0]])
### BUGGY CODE ###

import math
N, M, K = map(int, input().split())
sosu = 10 ** 9 + 7

def P(n, r):
    return math.factorial(n)//math.factorial(n-r)

def C(n, r):
    return P(n, r)//math.factorial(r)
dis = 0
for i in range(1,N):
    dis += i * (N-i) * M * M
    dis = dis % sosu
for j in range(1,M):
    dis += j * (M-j) * N * N
    dis = dis % sosu
#print(dis)

if K >= 3:
    dis = dis * C(N*M-2, K-2) % sosu
print(dis)

### FIXED CODE ###

import math
N, M, K = map(int, input().split())
sosu = 10 ** 9 + 7

def P(n, r):
    return math.factorial(n)//math.factorial(n-r)

def C(n, r):
    return P(n, r)//math.factorial(r)


dis = M * M * N * N * (N+1) // 2 % sosu
dis = dis - M * M * N * (N+1) * ( 2* N + 1) // 6 % sosu
dis = dis + N * N * M * M * (M+1) //2 % sosu
dis = dis - N * N * M * (M+1) * (2*M + 1) // 6 % sosu

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

mod = sosu #出力の制限
N = N * M
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 )


if K >= 3:
    dis = dis * cmb(N-2, K-2, mod) % sosu
if dis >= 0:
    print(dis)
else:
    print(dis + sosu)
### BUGGY CODE ###

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

ans=0
for i in range(n-k+1):
 sp=0
 for j in range(i,i+k):
  sp+=((p[j]*(p[j]+1))*0.5)*(1/p[j])
# sp/=100
 ans=max(ans,sp)

print(ans)

### FIXED CODE ###

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

b=[0]
for i in range(1,n+1):
 b.append(p[i-1]+b[i-1])

mm=0
inx=-1
for i in range(len(b)-k):
 if b[i+k]-b[i]>=mm:
  inx=i
  mm=b[i+k]-b[i]


ans=0
for j in range(inx,inx+k):
  ans+=((p[j]*(p[j]+1))*0.5)*(1/p[j])

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

from bisect import*
import sys;input=sys.stdin.readline

def doevent(lis):
    global stop
    a,b=lis
    if b>=0:
        if stop=={-1}:
            stop=set()
        stop.add(b)
    else:
        if -b in stop:
            stop.remove(-b)
        if stop==set():
            stop={-1}
    return min(stop)

n,q=map(int,input().split())
event=[]
stop=set([-1])
def main():
    for i in range(n):
        s,t,x=map(int,input().split())
        event.append((s-x,x))
        event.append((t-x,-x))
    event.sort(key=lambda x:x[0])
    minlist=[doevent(i)for i in event] #時間をindexとしたminlist

    for i in range(q):
        print(minlist[bisect_right(event,(int(input()),10**9))-1])
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))
    
event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop
        
print('\n'.join(map(str, ans)))
### BUGGY CODE ###

import copy
h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]
c=[[0]*w for i in range(h)]
for i in range(h):
  for j in range(w):
    c[i][j]=abs(a[i][j]-b[i][j])
dp=[[[] for i in range(w)] for j in range(h)]
dp[0][0].append(c[0][0])
for i in range(h):
  for j in range(w):
    f=0
    if i<h-1:
      l=[]
      for k in range(len(dp[i][j])):
        if -160*80<=dp[i][j][k]+c[i+1][j]<=160*80:
          l.append(dp[i][j][k]+c[i+1][j])
        if -160*80<=l[k]-c[i+1][j]<=160*80:
          l.append(dp[i][j][k]-c[i+1][j])
      l=list(set(l))
      dp[i+1][j]=l+dp[i+1][j]
      dp[i+1][j]=list(set(dp[i+1][j]))
    f=0
    if j<w-1:
      l=[]
      for k in range(len(dp[i][j])):
        if -160*80<=dp[i][j][k]+c[i][j+1]<=160*80:
          l.append(dp[i][j][k]+c[i][j+1])
        if -160*80<=dp[i][j][k]-c[i][j+1]<=160*80:
          l.append(dp[i][j][k]-c[i][j+1])
      l=list(set(l))
      dp[i][j+1]=l+dp[i][j+1]
      dp[i][j+1]=list(set(dp[i][j+1]))
for i in range(len(dp[h-1][w-1])):
  dp[h-1][w-1][i]=abs(dp[h-1][w-1][i])
print(min(dp[h-1][w-1]))

### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
  h,w=map(int,input().split())
  a=[list(map(int,input().split())) for i in range(h)]
  b=[list(map(int,input().split())) for i in range(h)]
  dp=[[[0]*(80*(h+w+1)+1) for i in range(w)] for j in range(h)]
  dp[0][0][abs(a[0][0]-b[0][0])]=1
  for i in range(h):
    for j in range(w):
      c=abs(a[i][j]-b[i][j])
      if i!=0 or j!=0:
        for k in range(80*(i+j+1)+1):
          dp[i][j][k]=dp[i-1][j][abs(k-c)]|dp[i-1][j][k+c]|dp[i][j-1][abs(k-c)]|dp[i][j-1][k+c]
  for i in range(80*(h+w+1)+1):
    if dp[h-1][w-1][i]==1:
      print(i)
      break

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

n,m = map(int,input().split(" "))
def bar_M(t):
    return int(t)%m
array = list(map(bar_M,input().split(" ")))

array_sum = [0 for i in range(n+1)]
for i in range(1,n+1):
    array_sum[i] = (array_sum[i-1] + array[i-1])%m

nums = set(array_sum)
sums = []
for i in nums:
    sums.append(array_sum.count(i))
ans = 0
for i in sums:
    ans+=int((i-1)*i/2)
print(ans)

### FIXED CODE ###

n,m = map(int,input().split(" "))
array = list(map(int,input().split(" ")))

array_sum,sums = [0,0],{0:1}
for i in range(1,n+1):
    array_sum[0] = array_sum[1]
    array_sum[1] = (array_sum[0] + array[i-1])%m
    sums[array_sum[1]] = sums.get(array_sum[1],0) + 1

ans = 0
for i in sums.values():
    ans+=int((i-1)*i/2)
print(ans)