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

n, k = map(int, input().split())
p = list(map(int, input().split()))
l = []
m = []
s = []
j = 0
for i in range(1, 1001):
    j += i
    s.append(j)

for i in range(n-k+1):
    ans = 0
    a = p[i:i+k]
    for b in a:
        ans += s[b-1]/b
    l.append(ans)
print(max(l))

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
l = []
y = 0
for x in range(1, 1001):
    y += x
    l.append(y/x)
m = []
for i in p:
    m.append(l[i-1])
s = [0]
z = 0
for i in m:
    z += i
    s.append(z)
ans = 0
for i in range(n-k+1):
    ans = max(ans, s[i+k] - s[i])
print(ans)
### BUGGY CODE ###

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

if N < B:
    print((A*N)//B)
    exit()

ans = 0
for x in range(N+1):
    q, r = divmod(x, B)
    ans = max(ans, (A*r)//B - (A-1)*q)
    # 終了判定
    if ans == B-1:
        break

print(ans)


### FIXED CODE ###

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

if N < B:
    print((A*N)//B)
else:
    qa, ra = divmod(A, B)
    rx = B-1
    print(qa*rx + (ra*rx)//B)
### BUGGY CODE ###

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

diff_m = 0
diff_p = []
mcount = 0

if sum(B) > sum(A):
    print(-1)

else:
    for i in range(N):
        difftmp = A[i] - B[i]
        
        if difftmp < 0:
            diff_m += difftmp
            mcount += 1
        
        else:
            diff_p.append(difftmp)
    

    if diff_m == 0:
        print(0)

    else:
        diff_p.sort(reverse = True)

        for j in range(0,N):
            a = sum(diff_p[:j])
 

            if diff_m + a >= 0:
                print(j+mcount)
                break

            else:
                continue


### FIXED CODE ###

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

diff_m = 0
diff_p = []
mcount = 0

if sum(B) > sum(A):
    print(-1)

else:
    for i in range(N):
        difftmp = A[i] - B[i]
        
        if difftmp < 0:
            diff_m += difftmp
            mcount += 1
        
        else:
            diff_p.append(difftmp)
    

    if diff_m == 0:
        print(0)

    else:
        diff_p.sort(reverse = True)

        for j in range(0,N):
            diff_m = diff_m + diff_p[j]
 

            if diff_m >= 0:
                print(j+1 + mcount)
                break

            else:
                continue
### BUGGY CODE ###

a,b,n=map(int,input().split())
import math
ans=0
d=min(n,b)
e=b-1
for i in range(d):
    ans=max(ans,math.floor(a*i/b)-a*math.floor(i/b))
if b>d:
    print(math.floor(a*d/b)-a*math.floor(d/b))
else:
    print(math.floor(a*e/b)-a*math.floor(e/b))

### FIXED CODE ###

a,b,n=map(int,input().split())
import math
ans=0
d=min(n,b)
e=b-1
if b>d:
    print(math.floor(a*d/b)-a*math.floor(d/b))
else:
    print(math.floor(a*e/b)-a*math.floor(e/b))
### BUGGY CODE ###

import math

def combinations_count(n):
    return math.factorial(n) // (math.factorial(n - 2) * math.factorial(2))

n = int(input())
a = list(map(int,input().split()))
n_list = [[] for i in range(n)]
len_list = [0 for i in range(n)]

for i in range(n):
    n_list[a[i]-1].append(i)

for i in range(n):
    if len(n_list[i]) == 0:
        len_list[i] == 0
    elif len(n_list[i]) == 1:
        len_list[i] == 1
    else:
        len_list[i] = combinations_count(len(n_list[i]))

sum_len = sum(len_list)

for i in range(n):
    if len_list[a[i]-1] == 0:
        print(sum_len)
    elif len_list[a[i]-1] == 1 or len_list[a[i]-1] == 2:
        print(sum_len - 1)
    else:
        print(sum_len - len_list[a[i]-1] + combinations_count(len(n_list[a[i]-1]) - 1))


### FIXED CODE ###

import math

def combinations_count(n):
    return math.factorial(n) // (math.factorial(n - 2) * math.factorial(2))

n = int(input())
a = list(map(int,input().split()))
n_list = [0 for i in range(n)]
len_list = [0 for i in range(n)]

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

sum_len = 0

for i in range(n):
    if n_list[i] == 0:
        len_list[i] == 0
    elif n_list[i] == 1:
        len_list[i] == 1
    else:
        len_list[i] = combinations_count(n_list[i])
    sum_len += len_list[i]

for i in range(n):
    if len_list[a[i]-1] == 0:
        print(sum_len)
    elif len_list[a[i]-1] == 1 or len_list[a[i]-1] == 2:
        print(sum_len - 1)
    else:
        print(sum_len - (n_list[a[i]-1] - 1))
### BUGGY CODE ###

def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    for i in range(k):
        memo = [0] * (n + 1)
        for j, aa in enumerate(a):
            memo[max(0, j - aa)] += 1
            memo[min(n, j + aa + 1)] -= 1
        for j in range(n):
            memo[j + 1] += memo[j]
        a = memo[:-1]
        if set(a) == {n}:
            break
    print(*a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    for i in range(k):
        memo = [0] * (n + 1)
        for j, aa in enumerate(a):
            memo[max(0, j - aa)] += 1
            memo[min(n, j + aa + 1)] -= 1
        for j in range(n):
            memo[j + 1] += memo[j]
        a = memo[:-1]
        if a == [n] * n:
            break
    print(*a)


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

n,W=map(int,input().split())
items=[list(map(int,input().split())) for i in range(n)]
w=[items[i][0] for i in range(n)]
v=[items[i][1] for i in range(n)]

memo=[[-1]*(W+1) for i in range(n+1)]
def dfs(i,j):
  if i==n:
    return 0
  if memo[i][j]!=-1:
    return memo[i][j]
  else:
    if  j<w[i]:
      memo[i][j]=dfs(i+1,j)
      return memo[i][j]
    else:
      memo[i][j]=max(dfs(i+1,j),dfs(i+1,j-w[i])+v[i])
      return memo[i][j]
print(dfs(0,W))

### FIXED CODE ###

import sys
input=sys.stdin.readline

n,W=map(int,input().split())
items=[list(map(int,input().split())) for i in range(n)]
import numpy as np

dp=np.zeros([n+1,W+1],dtype=np.int64)
for i in range(n):
  w=items[i][0]
  v=items[i][1]
  dp[i+1][:w]=dp[i][:w]
  dp[i+1][w:]=np.maximum(dp[i][w:],dp[i][:-w]+v)
print(dp[-1][-1])
### BUGGY CODE ###

import sys
from fractions import gcd
import math
import collections
def input():
    return sys.stdin.readline()[:-1]
def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass


def main():
    n=int(input())
    a=list(map(int,input().split()))
    mod=10**9+7
    # li=[0]*(max(a)+1)
    dic={}
    li=[]
    for i in range(n):
        tmp=collections.Counter(prime_factor(a[i]))
        li.append(tmp)
        # print(tmp)
        for j in list(tmp.keys()):
            if not j in dic:
                dic[j]=tmp[j]
            else:
                dic[j]=max(dic[j],tmp[j])
    ans=1
    # print(dic)
    for i in dic.keys():
        # print(dic[i],i)
        ans*=i**dic[i]
    # print(ans)
    cnt=0
    for i in range(n):
        tmp=1
        # print(li[i])
        for j in dic.keys():
            if j in li[i]:
                tmp*=j**(dic[j]-li[i][j])
            else:
                tmp*=j**dic[j]
            tmp%=mod
        cnt+=tmp
        cnt%=mod
    print(cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque
import heapq
import math
import bisect
from itertools import permutations
from itertools import accumulate
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7

dic={}
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# print(factorization(12))
for i in range(n):
    tmp=factorization(a[i])
    for j in range(len(tmp)):
        if not tmp[j][0] in dic:
            dic[tmp[j][0]]=tmp[j][1]
        else:
            dic[tmp[j][0]]=max(dic[tmp[j][0]],tmp[j][1])
l=1
for i in dic.keys():
    l*=i**dic[i]
    l%=mod
# print(l)
ans=0
for i in range(n):
    ans+=l*pow(a[i],mod-2,mod)
    ans%=mod
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()

r = 0
g = 0
b = 0

for i in range(n):
    if s[i] == 'R':
        r += 1
    elif s[i] == 'G':
        g += 1
    else:
        b += 1
ans = r * b * g

for c in range(n):
    center = s[c]
    for dif in range(n):
        if dif + c > n - 1 or c - dif < 0:
            continue
        left = s[c - dif]
        right = s[c + dif]
        if left != center and center != right and right != left:
            ans -= 1
print(ans)

### FIXED CODE ###


n = int(input())
s = list(input())
cr = [0] * n
cg = [0] * n
cb = [0] * n
for i in range(n):
    if i == 0:
        if s[i] == 'R':
            cr[i] += 1
        elif s[i] == 'G':
            cg[i] += 1
        else:
            cb[i] += 1
    else:
        cr[i] = cr[i-1]
        cg[i] = cg[i-1]
        cb[i] = cb[i-1]
        if s[i] == 'R':
            cr[i] += 1
        elif s[i] == 'G':
            cg[i] += 1
        else:
            cb[i] += 1
ans = 0
for i in range(n-2):
    a = s[i]
    for j in range(i+1, n-1):
        b = s[j]
        if a == b:
            continue
        diff = j - i
        c = list({'R', 'G', 'B'} - {a, b})[0]
        if c == 'R':
            ans += cr[-1] - cr[j]
        elif c == 'G':
            ans += cg[-1] - cg[j]
        else:
            ans += cb[-1] - cb[j]
        if j + diff < n:
            if s[j + diff] == c:
                ans -= 1
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
reverse = 1


for i in range(Q):
    q = list(input().split())

    if (len(q) == 1):
        reverse *= - 1
    else:
        judge = int(q[1])
        cha = q[2]
        
        if (reverse == 1):
            if (judge == 1):
                S = cha + S
            else:
                S = S + cha
        elif (reverse == -1):
            if (judge == 1):
                S = S + cha
            else:
                S = cha + S
                

if (reverse == -1):
    S = S[::-1]

print(S)

### FIXED CODE ###

from collections import deque

S = deque(input())
Q = int(input())
reverse = 1


for i in range(Q):
    
    q = input()
    
    if (q == '1'):
        reverse *= -1
    else:
        integer, judge, cha = q.split()
        
        if (judge == '1'):
            if (reverse == 1):
                S.appendleft(cha)
            else:
                S.append(cha)
        
        elif (judge == '2'):
            if (reverse == 1):
                S.append(cha)
            else:
                S.appendleft(cha)

if (reverse == -1):
    S.reverse()

print(''.join(list(S)))
### BUGGY CODE ###

x,k = map(int,input().split())
arr = list(map(int,input().split()))
 
dp = [0]*len(arr)
 
for i in range(1,len(arr)):
  dp[i] = min(dp[j] + abs(arr[i]-arr[j]) for j in range(max(i-k,0),i))
print(dp[-1])


### FIXED CODE ###

n, k = [int(e) for e in input().split()]
arr = [int(e) for e in input().split()]
dp = [0]*len(arr)
 
for i in range(1,len(arr)):
  dp[i] = min(dp[j] + abs(arr[i]-arr[j]) for j in range(max(i-k,0),i))
print(dp[-1])
### BUGGY CODE ###

H,W,M=map(int,input().split())
Y=[0 for i in range(H+1)]
X=[0 for i in range(W+1)]
HW=[[0 for i in range(330000)] for j in range(330000)]
for i in range(M):
    h,w=map(int,input().split())
    Y[h]+=1
    X[w]+=1
    HW[h][w]+=1

LY=[]
LX=[]
MY=max(Y)
MX=max(X)
for i in range(H+1):
    if Y[i]==MY:
        LY.append(i)
for i in range(W+1):
    if X[i]==MX:
        LX.append(i)

import sys
for i in range(len(LY)):
    for j in range(len(LX)):
        if not HW[LY[i]][LX[j]]:
            print(MY+MX)
            sys.exit()

print(MY+MX-1)

### FIXED CODE ###

H,W,M=map(int,input().split())
Y=[0 for i in range(H+1)]
X=[0 for i in range(W+1)]
HW=[]
for i in range(M):
    h,w=map(int,input().split())
    Y[h]+=1
    X[w]+=1
    HW.append([h,w])

LY=[]
LX=[]
MY=max(Y)
MX=max(X)
for i in range(H+1):
    if Y[i]==MY:
        LY.append(i)
for i in range(W+1):
    if X[i]==MX:
        LX.append(i)

count=0
for i in range(M):
    if Y[HW[i][0]]==MY and X[HW[i][1]]==MX:
        count+=1

if count==len(LY)*len(LX):
    print(MY+MX-1)
else:
    print(MY+MX)
### BUGGY CODE ###

import sys
 
input = sys.stdin.readline
 
N, M = (int(i) for i in input().split())
input_list = [[int(i) for i in input().split()] for i in range(M)] 
 
m_list = [[] for j in range(N)]
 
for inputs in input_list:
    m_list[inputs[0]-1].append(inputs[1])
 
for arr in m_list:
    arr.sort()
 
for inputs in input_list:
    num = m_list[inputs[0]-1].index(inputs[1]) + 1
    print(str(inputs[0]).zfill(6) + str(num).zfill(6))

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
N, M = (int(i) for i in input().split())
py_list = [[int(i) for i in input().split()] + [0] for i in range(M)] 
m_list = [[] for j in range(N+1)]
 
sorted_py_list = sorted(py_list, key=lambda x:x[1])

city_list = {}
for py in sorted_py_list:
    city_list[py[0]] = city_list[py[0]]+1 if py[0] in city_list else 1
    py[2] = city_list[py[0]]
 
for py in py_list:
    print(str(py[0]).zfill(6) + str(py[2]).zfill(6))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

cnt = 0
dice = [(i+1)/2 for i in p]

ans = 0
for i in range(n - k + 1):
    exp = sum(dice[i:i + k])
    ans = max(ans, exp)
    
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

cnt = 0
dice = [(i+1)/2 for i in p]

ans = sum(dice[:k])
exp = sum(dice[:k])

for i in range(k, n):
    exp = exp-dice[i-k]+dice[i]
    ans = max(ans, exp)
print(ans)
### BUGGY CODE ###

N = int(input())

sum_N = 0

while N >= 10:
  sum_N += N % 10
  N = N //10

if (sum_N+N) % 9 == 0:
  print('Yes')
else:
  print('No')
  

### FIXED CODE ###

N = int(input())

if N%9 ==0:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

N, P = map(int, input().split())
p = P**(1/N)
if p % 1 == 0:
    print(int(p))
    exit()

p = (int(p) + 1)//2

dic = {}

def my(N,p,s=2):
    for i in range(s,p+1):
        if p % i == 0:
            dic[i] = dic.get(i,0) + 1
            p = p//i
            s = i
            
            break
    
    if p == 1:
        res = 1
        for j,k in dic.items():
            res *= j**(k//N)
        print(res)
        exit()
    else:
        my(N,p,s)

my(N,P)

### FIXED CODE ###

N, P = map(int, input().split())
p = P**(1/N)
if p % 1 == 0:
    print(int(p))
    exit()

lim = int(p) + 1

dic = {}

def my(N,newP):
    for i in range(2,lim+1):
        while newP % i == 0:
            dic[i] = dic.get(i,0) + 1
            newP = newP // i
        if newP < i or i == lim:
            res = 1
            for j,k in dic.items():
                res *= j**(k//N)
            print(res)
            exit()
my(N,P)
### BUGGY CODE ###

import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  q=[]

  field=[S() for _ in range(h)]
  counter=[[inf]*w for _ in range(h)]

  sharp_cnt=0
  for x in field:
    sharp_cnt+=x.count('#')

  q.append((0,0,0))

  while len(q)>0:
    y,x,cnt=q.pop()
    counter[y][x]=cnt

    for dy,dx in dd:
      ny=y+dy
      nx=x+dx

      if 0<=ny and 0<=nx and ny<h and nx<w:
        if field[ny][nx]!='#':
          if counter[ny][nx]>cnt:
            q.append((ny,nx,cnt+1))

  step_cnt=counter[h-1][w-1]+1

  if step_cnt==inf+1:
    return -1

  return h*w-sharp_cnt-step_cnt

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  q=[]

  field=[S() for _ in range(h)]
  counter=[[inf]*w for _ in range(h)]

  sharp_cnt=0
  for x in field:
    sharp_cnt+=x.count('#')

  q.append((0,0,1))

  while len(q)>0:
    y,x,cnt=q.pop()
    if counter[y][x]<cnt:
      continue
    counter[y][x]=cnt

    for dy,dx in dd:
      ny=y+dy
      nx=x+dx

      if 0<=ny and 0<=nx and ny<h and nx<w:
        if field[ny][nx]!='#':

          if counter[ny][nx]>cnt+1:
            q.append((ny,nx,cnt+1))

  step_cnt=counter[h-1][w-1]

  if step_cnt==inf:
    return -1

  return h*w-sharp_cnt-step_cnt

# main()
print(main())
### BUGGY CODE ###

n,k = map(int,input().split())
a_li = list(map(int,input().split()))
ans = 1
for i in range(k):
    ans *= a_li[i]
for i in range(k,n):
    num = ans // a_li[i-k]
    num *= a_li[i]
    if num > ans:
        print("Yes")
    else:
        print("No")
    ans = num

### FIXED CODE ###

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

for i in range(k,n):
    if a_li[i-k] < a_li[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import heapq
N, M = map(int, input().split())
E = [[] for _ in range(N)]
RE = [[] for _ in range(N)]
S = [0] * N
for _ in range(M):
  l, r, d = map(int, input().split())
  S[l - 1] = 1
  E[l - 1].append([d, r - 1])
  RE[r - 1].append([d, l - 1])
D = [None] * N
def dijkstra(i):
  D[i] = 0
  Q = [[0, i]]
  while Q:
    d, s = heapq.heappop(Q)
    for dist, adj in E[s]:
      if D[adj] == None:
        D[adj] = D[s] + dist
        heapq.heappush(Q, [D[adj], adj])
      elif D[adj] == 'Error' or D[adj] != D[s] + dist:
        D[s] = 'Error'
        break
    else:
      for dist, adj in RE[s]:
        if D[adj] == None:
          D[adj] = D[s] - dist
          heapq.heappush(Q, [D[adj], adj])
        elif D[adj] == 'Error' or D[adj] != D[s] - dist:
          D[s] = 'Error'
          break
      else:
        continue
    break
for i in range(N):
  if D[i] == 'Error':
    print('No')
    break
  elif D[i] == None:
    dijkstra(i)
else:
  for d in D:
    if d == 'Error':
      print('No')
      break
  else:
    print('Yes')

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
E = [[] for _ in range(N)]
RE = [[] for _ in range(N)]
S = [0] * N
for _ in range(M):
  l, r, d = map(int, input().split())
  S[l - 1] = 1
  E[l - 1].append([d, r - 1])
  RE[r - 1].append([d, l - 1])
D = [None] * N
def dijkstra(i):
  D[i] = 0
  Q = [[0, i]]
  while Q:
    d, s = heapq.heappop(Q)
    for dist, adj in E[s]:
      if D[adj] == None:
        D[adj] = D[s] + dist
        heapq.heappush(Q, [D[adj], adj])
      elif D[adj] == 'Error' or D[adj] != D[s] + dist:
        D[s] = 'Error'
        break
    else:
      for dist, adj in RE[s]:
        if D[adj] == None:
          D[adj] = D[s] - dist
          heapq.heappush(Q, [D[adj], adj])
        elif D[adj] == 'Error' or D[adj] != D[s] - dist:
          D[s] = 'Error'
          break
      else:
        continue
    break
for i in range(N):
  if D[i] == 'Error':
    print('No')
    break
  elif D[i] == None:
    dijkstra(i)
else:
  for d in D:
    if d == 'Error':
      print('No')
      break
  else:
    print('Yes')
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W, k = map(int, input().split())
    grid = [[0] * W for _ in range(H)]
    for _ in range(k):
        r, c, v = map(int, input().split())
        grid[r - 1][c - 1] = v

    dp = [[[-f_inf] * W for _ in range(H)] for _ in range(4)]
    dp[0][0][0] = 0
    for h in range(H):
        for w in range(W):
            # アイテムを取る場合
            for i in reversed(range(3)):
                if dp[i][h][w] >= 0:
                    dp[i + 1][h][w] = max(dp[i + 1][h][w], dp[i][h][w] + grid[h][w])
            # アイテムを取らない場合
            for i in range(4):
                if dp[i][h][w] >= 0:
                    if h + 1 < H:
                        dp[0][h + 1][w] = max(dp[0][h + 1][w], dp[i][h][w])
                    if w + 1 < W:
                        dp[i][h][w + 1] = max(dp[i][h][w + 1], dp[i][h][w])
    res = 0
    for i in range(4):
        res = max(res, dp[i][-1][-1])
    print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W, k = map(int, input().split())
    grid = [[0] * W for _ in range(H)]
    for _ in range(k):
        r, c, v = map(int, input().split())
        grid[r - 1][c - 1] = v

    # dp[i][h][w]:h行目のアイテムをi個取得した時の、座標(h,w)における価値の最大値
    dp = [[[0] * W for _ in range(H)] for _ in range(4)]
    dp[1][0][0] = grid[0][0]
    for h in range(H):
        for w in range(W):
            for i in range(4):
                # 下に移動する場合
                if h + 1 < H:
                    # アイテムを取らない
                    dp[0][h + 1][w] = max(dp[0][h + 1][w], dp[i][h][w])
                    # アイテムを取る
                    dp[1][h + 1][w] = max(dp[1][h + 1][w], dp[i][h][w] + grid[h + 1][w])
                # 右に移動する場合
                if w + 1 < W:
                    # アイテムを取らない
                    dp[i][h][w + 1] = max(dp[i][h][w + 1], dp[i][h][w])
                    # アイテムを取る（但し、4個以上所持してはいけない）
                    if i + 1 < 4:
                        dp[i + 1][h][w + 1] = max(dp[i + 1][h][w + 1], dp[i][h][w] + grid[h][w + 1])
    res = 0
    for i in range(4):
        res = max(res, dp[i][-1][-1])
    print(res)


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

from operator import mul
from functools import reduce

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

MOD = 10 ** 9 + 7
N, K = map(int, input().split())
if K == 1:
    print(0)
    exit()

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

N = len(A)
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)

ans = 0
sum_num = 0
for i in range(N - (K - 1)):
    for j in range(i+K-1, N):
        ans += (A[j] - A[i]) * cmb(j-i-1, K-2, MOD)
print(ans % MOD)


### FIXED CODE ###

MOD = 10 ** 9 + 7

def ncr(n, r, mod=MOD):
    return (fct[n] * invf[r] * invf[n - r]) % mod


def make_tables(n, mod=MOD):
    fct = [1 for _ in range(n + 1)]
    invf = [1 for _ in range(n + 1)]

    for i in range(2, n + 1):
        fct[i] = (fct[i - 1] * i) % mod
        invf[i] = divmod(fct[i])
    return fct, invf


def divmod(a, mod=MOD):
    return pow(a, mod - 2, mod)


N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
for i in range(N):
    A[i] %= MOD

fct, invf = make_tables(N, mod=MOD)

ans = 0
for i in range(N - K + 1):
    ans += ((A[-1-i] - A[i]) % MOD * ncr(N - i - 1, K - 1)) % MOD
print(ans % MOD)
### BUGGY CODE ###

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

MaxX1=min(A[-1],A[1])*2

for i in range(0,MaxX1+2,2):
    X=[i]*N
    for j in range(N-1):
        X[j+1]=2*A[j]-X[j]
        AJ=[0]*N
        for k in range(N):
            AJ[k-1]=X[k-1]/2+X[k]/2
        if AJ==A:
            print(" ".join(map(str,X)))
            exit()

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
X=[0]*n
S=sum(A)
A2=0
for i in range(1,n-1,2):
  A2+=A[i]
X[0]=S-2*A2
for i in range(1,n):
  X[i]=2*A[i-1]-X[i-1]
print(*X)