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

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

dp = [2 * 10 ** 9 for _ in range(n)]
dp[0] = 0
for i in range(1, n):
    hi = h[i]
    for j in range(1, min(k, i) + 1):
        dp[i] = min(dp[i], dp[i - j] + abs(hi - h[i - j]))
print(dp[-1])


### FIXED CODE ###

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

dp = [0 for _ in range(n)]
for i in range(1, n):
    hi = h[i]
    x = 2 * 10 ** 9
    for j in range(1, min(k, i) + 1):
        x = min(x, dp[i - j] + abs(hi - h[i - j]))
    dp[i] = x
print(dp[-1])
### BUGGY CODE ###

N = int(input())
s = [0] * N
time = [1] * N
j = 0
for i in range(N):
  inp = str(input())
  if inp in s:
    x = s.index(inp)
    time[x] += 1
  else:
    s[j] = inp
    j += 1
    
ans = max(time)
#print(s, time)
ans_list = []
for i in range(N):
  if time[i] == ans:
    if s[i] != 0:
      ans_list.append(s[i])
      
ans_list = sorted(ans_list)
for i in range(len(ans_list)):
  print(ans_list[i])

### FIXED CODE ###

import collections
N = int(input())
s = [0] * N
for i in range(N):
  s[i] = str(input())
  
#print(s)
t = collections.Counter(s)
u = list(t.items())
#print(u)
x = max(list(t.values()))
ans = []
#print(x)
#print(u)
for i in range(len(u)):
  #print(u[i][1], x)
  if u[i][1] == x:
    ans.append(u[i][0])
    
    
ans = sorted(ans)

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

import collections
def main():

    N = int(input())
    S = input()
    d = collections.defaultdict(dict)
    ans = 0
    for l in range(1, N//2+1):
        for i in range(N-l+1):
            t = S[i:i+l]
            if t not in d[l]:
                d[l][t] = [i, i+l-1]
            else:
                if i > d[l][t][1]:
                    ans = l
                    break
    return ans

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

### FIXED CODE ###

def main():

    N = int(input())
    S = input()
    dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
    ans = 0

    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if S[i-1] == S[j-1] and dp[i-1][j-1] < (j-i):
                dp[i][j] = dp[i-1][j-1] + 1
                ans = max(ans, dp[i][j])
            else:
                dp[i][j] == 0
    return ans

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

s = input()
q = int(input())

for i in range(q):
    a = list(input().split())
    if a[0] == '1':
        s = s[::-1]
    if a[0] == '2':
        if a[1] == '1':
            s = a[2] + s
        else:
            s += a[2]
print(s)

### FIXED CODE ###

s = str(input())
q = int(input())
inv = False
head = ''
tail = ''

for i in range(q):
    a = input()
    if a == '1':
        inv = not inv
        continue
    a = a.split()
    if (a[1] == '1')^inv:
        head = a[2] + head
    else:
        tail += a[2]
s = head + s + tail
if inv:
    print(s[::-1])
else:
    print(s)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

input = sys.stdin.readline


def main():
    s = input().rstrip()
    n = len(s)
    cs = [0] * (n + 1)
    for i, x in enumerate(s):
        cs[i + 1] = cs[i] + int(x)
    ans = 0
    for i in range(n):
        for j in range(i + 3, n + 1):
            if (cs[j] - cs[i]) % 3 != 0:
                continue
            if int(s[i:j]) % 2019 == 0:
                ans += 1
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
s = input()[::-1]
n = len(s)
cs = [0] * (n + 1)
ten = 1
for i in range(n):
    cs[i + 1] = int(s[i]) * ten % 2019
    ten = ten * 10 % 2019
for i in range(n):
    cs[i + 1] = (cs[i + 1] + cs[i]) % 2019
cnt = [0] * 2019
for i, x in enumerate(cs):
    cnt[x] += 1
ans = sum(x * (x - 1) // 2 for x in cnt)
print(ans)
### BUGGY CODE ###

import math
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
f = [int(x) for x in input().split()]
a.sort()
f.sort(reverse=True)
lx = 0
rx = a[-1] * f[0]
for i in range(1000):
    if lx == rx:
        break
    cx = (lx + rx) // 2
    kk = 0
    for j in range(n):
        ta = a[j]
        y = (ta*f[j] - cx + f[j] -1) // f[j]
        kk += max(0, y)
    if kk <= k:
        rx = cx
    else:
        lx = cx
print(rx)

### FIXED CODE ###

n, k = map(int, input().split())
# a = [int(x) for x in input().split()]
# f = [int(x) for x in input().split()]
a = list(map(int, input().split()))
f = list(map(int, input().split()))
a.sort()
f.sort(reverse=True)
lx = -1
rx = a[-1] * f[0]
while rx-lx>1 :
    cx = (lx + rx) // 2
    kk = 0
    for j in range(n):
        kk += max(0, a[j] - cx//f[j])
    if kk <= k:
        rx = cx
    else:
        lx = cx
print(rx)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(m):
    a[n-1] = a[n-1] // 2
    a.sort()
print(sum(a))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
if n == 1:
    for i in range(m):
        a[0] = a[0] // 2
    print(sum(a))
    exit()

a.sort()
i = 0
while i < m:
    a[n-1] = a[n-1] // 2
    i+=1
    num = len([1 for x in a[:n-1] if x > a[n-1]])
    hoge = min(m-i, num)
    for j in range(hoge):
        a[n-2-j] = a[n-2-j] // 2
    i += hoge
    a.sort()

print(sum(a))
### BUGGY CODE ###

n,m=[int(x) for x in input().rstrip().split()]
a=[int(x) for x in input().rstrip().split()]
a.sort(reverse=True)
d=[]
for i in range(m):
  b,c=[int(x) for x in input().rstrip().split()]
  d.extend([c]*b)
d.sort(reverse=True)
a+=d
a.sort(reverse=True)
print(sum(a[:n]))


### FIXED CODE ###

n,m=[int(x) for x in input().rstrip().split()]
a=[int(x) for x in input().rstrip().split()]
a.sort(reverse=True)
d=[]
bc=[]
for i in range(m):
  b,c=[int(x) for x in input().rstrip().split()]
  bc.append([b,c])

cnt=0
bc.sort(key=lambda x:x[1],reverse=True)
for b,c in bc:

  d.extend([c]*b)
  cnt+=b
  if n<cnt:
    break
  
d.sort(reverse=True)
a+=d
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

import math
N = int(input())
cnt_list = [0] * N
for i in range(1, N + 1):
    for j in range(i, N + 1, i):
        cnt_list[j - 1] += 1
ans = 0
for h in range(1, N + 1):
    ans += h * cnt_list[h -1]
print(ans)

### FIXED CODE ###

import math
N = int(input())
cnt_list = [0] * N
for i in range(1, N + 1):
    for j in range(i, N + 1, i):
        cnt_list[j - 1] += 1
ans = 0
for h in range(1, N + 1):
    ans += h * cnt_list[h -1]
print(ans)
### BUGGY CODE ###

N,M = list(map(int,input().split()))
S = list(map(int,input().split()))
S = [0] + S
T = list(map(int,input().split()))
T = [0] + T
DP = [[0] * (N+1)  for _ in range(M+1)]
for n in range(N+1):
    DP[0][n] = 1
for m in range(M+1):
    DP[m][0] = 1
# s = 0
# for i in range(N+1):
#     for j in range(M+1):
#         if S[i] == T[j]:
#             for i2 in range(i):
#                 for j2 in range(j):
#                     dp[i][j] += dp[i2][j2]
#             s += dp[i][j]
# print(s)
mod = 10**9 + 7
for n in range(1,N+1):
    for m in range(1,M+1):
        num = DP[m-1][n-1] if S[n] == T[m] else 0
        DP[m][n] = (DP[m-1][n] + DP[m][n-1] + num - DP[m-1][n-1]) % mod
print(DP[M][N])

### FIXED CODE ###

N,M = list(map(int,input().split()))
S = list(map(int,input().split()))
S = [0] + S
T = list(map(int,input().split()))
T = [0] + T
dp = [[0] * (N+1)  for _ in range(M+1)]
DP = [[0] * (N+1)  for _ in range(M+1)]
dp[0][0] = 1
for n in range(N+1):
    DP[0][n] = 1
for m in range(M+1):
    DP[m][0] = 1
# s = 0
# for i in range(N+1):
#     for j in range(M+1):
#         if S[i] == T[j]:
#             for i2 in range(i):
#                 for j2 in range(j):
#                     dp[i][j] += dp[i2][j2]
#             s += dp[i][j]
# print(s)
for n in range(1,N+1):
    for m in range(1,M+1):
        if S[n] == T[m]:
            dp[m][n] = DP[m-1][n-1]
        DP[m][n] = (DP[m-1][n] + DP[m][n-1] + dp[m][n] - DP[m-1][n-1]) % (10**9+7)
print(DP[M][N])
### BUGGY CODE ###

s = list(str(input()) )
b = {}
b[0] = 1
c_ = 0
for num,i in enumerate(reversed(s)):
  c = c_+int(i)*10**num
  if c%2019 in b: 
    b[c%2019] += 1
  else:
    b[c%2019] = 1
  c_ = c
ans = 0
for i in b.values():
  ans += i*(i-1)//2
print(ans)

### FIXED CODE ###

s = input()
MOD = 2019
a =[0]*MOD
a[0] = 1
c_ = 0
ans = 0
t = 1
for i in reversed(s):
  c = (c_+int(i)*t)%MOD
  a[c] += 1
  t *= 10
  t %= MOD
  c_ = c
for i in a:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

def factorial(n):
  ans = 1
  for i in range(n):
    ans *= i+1
    ans %= mod
  return ans


mod = 998244353
n = int(input())
s = input()
ans = 1
r,g,b = 0,0,0
rg,rb,gb = 0,0,0
for i in s:
  if i == "R":
    if gb > 0:
      ans *= gb
      gb -= 1
    elif g > 0:
      ans *= g
      g -= 1
      rg += 1
    elif b > 0:
      ans *= b
      b -= 1
      rb += 1
    else:
      r += 1
  elif i == "G":
    if rb > 0:
      ans *= rb
      rb -= 1
    elif r > 0:
      ans *= r
      r -= 1
      rg += 1
    elif b > 0:
      ans *= b
      b -= 1
      gb += 1
    else:
      g += 1
  elif i == "B":
    if rg > 0:
      ans *= rg
      rg -= 1
    elif r > 0:
      ans *= r
      r -= 1
      rb += 1
    elif g > 0:
      ans *= g
      g -= 1
      gb += 1
    else:
      b += 1
print((factorial(n) * ans) % mod)

### FIXED CODE ###

def factorial(n):
  ans = 1
  for i in range(n):
    ans *= i+1
    ans %= mod
  return ans


mod = 998244353
n = int(input())
s = input()
ans = 1
r,g,b = 0,0,0
rg,rb,gb = 0,0,0
for i in s:
  if i == "R":
    if gb > 0:
      ans *= gb
      gb -= 1
    elif g > 0:
      ans *= g
      g -= 1
      rg += 1
    elif b > 0:
      ans *= b
      b -= 1
      rb += 1
    else:
      r += 1
  elif i == "G":
    if rb > 0:
      ans *= rb
      rb -= 1
    elif r > 0:
      ans *= r
      r -= 1
      rg += 1
    elif b > 0:
      ans *= b
      b -= 1
      gb += 1
    else:
      g += 1
  elif i == "B":
    if rg > 0:
      ans *= rg
      rg -= 1
    elif r > 0:
      ans *= r
      r -= 1
      rb += 1
    elif g > 0:
      ans *= g
      g -= 1
      gb += 1
    else:
      b += 1
  ans %= mod
print((factorial(n) * ans) % mod)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

# dp[i][j][k] = 寿司が3つの皿がi個、2つの皿がj個、1つの皿がk個からの操作回数の期待値
# dp[0][0][0] = 0で正しいので、ここから順に埋めていけばよい。

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

cnt = [0] * 4

for a in A:
  cnt[a] += 1

dp = [[[0 for k in range(N + 2)] for j in range(N + 2)] for i in range(N + 2)]

for i in range(N + 1):
  for j in range(N + 1):
    for k in range(N + 1):
      nonzero = i + j + k
      if nonzero == 0:
        continue
      dp[i][j][k] = N / nonzero
      if i - 1 >= 0:
        dp[i][j][k] += dp[i - 1][j + 1][k] * i / nonzero
      if j - 1 >= 0:
        dp[i][j][k] += dp[i][j - 1][k + 1] * j / nonzero
      if k - 1 >= 0:
        dp[i][j][k] += dp[i][j][k - 1] * k / nonzero

print(dp[cnt[3]][cnt[2]][cnt[1]])


### FIXED CODE ###

import sys
readline = sys.stdin.readline

# dp[i][j][k] = 寿司が3つの皿がi個、2つの皿がj個、1つの皿がk個からの操作回数の期待値
# dp[0][0][0] = 0で正しいので、ここから順に埋めていけばよい。

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

cnt = [0] * 4

for a in A:
  cnt[a] += 1

dp = [[[0 for k in range(N + 2)] for j in range(N + 2)] for i in range(N + 2)]

for i in range(N + 1):
  for j in range(N + 1):
    for k in range(N + 1):
      nonzero = i + j + k
      if nonzero == 0:
        continue
      dp[i][j][k] = N / nonzero
      if i - 1 >= 0:
        dp[i][j][k] += dp[i - 1][j + 1][k] * i / nonzero
      if j - 1 >= 0:
        dp[i][j][k] += dp[i][j - 1][k + 1] * j / nonzero
      if k - 1 >= 0:
        dp[i][j][k] += dp[i][j][k - 1] * k / nonzero

print(dp[cnt[3]][cnt[2]][cnt[1]])
### BUGGY CODE ###

# D
import numpy as np
N, X, Y = map(int, input().split())

X = X - 1
Y = Y - 1

x = np.zeros((N,N))
for i in range(N):
    x[i,i:] = np.array(range(N-i))
y = np.zeros((N,N))
for i in range(0, N):
    for j in range(i+1, N):
        y[i, j] = abs(i-X) + abs(j-Y) + 1

ans = np.minimum(x, y)

for i in range(1,N):
    print(np.sum(ans==i))

### FIXED CODE ###

# D
import numpy as np
N, X, Y = map(int, input().split())

D = [0]*N
for i in range(1, N+1):
    for j in range(i+1, N+1):
        d = min(j-i, abs(j-Y) + abs(i-X) + 1) 
        D[d] += 1
for i in range(1, N):
    print(D[i])
### BUGGY CODE ###

import copy
n,m = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(m)]
bridge = [0 for _ in range(n)]
bridge_m = [[] for _ in range(n)]
for i in range(m):
    for j in range(ab[i][0],ab[i][1]):
        bridge[j] +=1
        bridge_m[j].append(i)
cnt =0
max_ = max(bridge)
while(max_!=0):
    argmax = bridge.index(max_)
    delete = copy.deepcopy(bridge_m[argmax])
    for i in delete:
        for j in range(ab[i][0],ab[i][1]):
            bridge[j] -=1
            bridge_m[j].remove(i)
    cnt +=1
    max_ =max(bridge)
print(cnt)

### FIXED CODE ###

n,m = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(m)]
ab.sort(key=lambda x:x[1])
last=-1
cnt=0
for i in range(len(ab)):
    if(ab[i][0]<=last):pass
    else:
        last=ab[i][1]-1
        cnt+=1
print(cnt)
### BUGGY CODE ###

import itertools
N = int(input())
A = list(map(int,input().split()))
a = set(A)
max = 0
comb = list(itertools.combinations(A,4))
for i in range(len(comb)):
    item = list(set(comb[i]))
    if len(item) == 2:
        if max < item[0]*item[1]:
            max = item[0]*item[1]

print(max)





### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int,input().split()))
c = Counter(A)
sticks = []
for i in c:
    s = c[i]
    if s >= 4:
        sticks.append(i)
    if s >= 2:
        sticks.append(i)
if len(sticks) < 2:
    print(0)
else:
    sticks.sort(reverse=True)
    print(sticks[0]*sticks[1])
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
ans = P.index(1)

for i in range(1,ans):
  if i > N - P[i]:
    ans -= 1
    continue
  for j in range(i):
    if P[i]>P[j]: 
      ans -= 1
      break
  
print(ans+1)

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
ans = 1
small = P[0]
for i in range(1,N):
  if P[i] <= small: 
    ans += 1
    small = P[i]
print(ans)
### BUGGY CODE ###



import sys
sys.setrecursionlimit(1000000)

def dfs1(u, pu):
    dp[u] = 1
    for v in tree[u]:
        if v != pu:
            dfs1(v, u)
            dp[u] *= (dp[v] + 1)
            dp[u] %= MOD

def dfs2(u, pu, pval):
    resp[u] = (dp[u] * pval) % MOD

    chlds = [v for v in tree[u] if v != pu]
    cumulr = [1] * len(chlds)
    for i in range(len(chlds) - 2, -1, -1):
        cumulr[i] = cumulr[i + 1] * (1 + dp[chlds[i + 1]]) % MOD

    pref = pval
    for i in range(len(chlds)):
        v = chlds[i]
        vval = (1 + pref * cumulr[i]) % MOD

        dfs2(v, u, vval)

        pref *= (dp[v] + 1)
        pref %= MOD


n, MOD = map(int, raw_input().split())
tree = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(lambda u: int(u) - 1, raw_input().split())
    tree[u].append(v)
    tree[v].append(u)

dp = [0] * n
resp = [0] * n
dfs1(0, -1)
dfs2(0, -1, 1)
for i in range(n):
    print(resp[i])


### FIXED CODE ###



n, MOD = map(int, raw_input().split())
tree = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(lambda u: int(u) - 1, raw_input().split())
    tree[u].append(v)
    tree[v].append(u)


cola = [(0, -1)]
qind = 0
while qind < len(cola):
    u, pu = cola[qind]
    qind += 1
    for v in tree[u]:
        if v != pu:
            cola.append((v, u))

dp = [1] * n
for i in range(n - 1, -1, -1):
    u, pu = cola[i]
    for v in tree[u]:
        if v != pu:
            dp[u] *= (dp[v] + 1)
            dp[u] %= MOD

resp = [0] * n
pval = [1] * n
for j in range(n):
    u, pu = cola[j]
    resp[u] = (dp[u] * pval[u]) % MOD

    chlds = [v for v in tree[u] if v != pu]
    cumulr = [1] * len(chlds)
    for i in range(len(chlds) - 2, -1, -1):
        cumulr[i] = cumulr[i + 1] * (1 + dp[chlds[i + 1]]) % MOD

    pref = pval[u]
    for i in range(len(chlds)):
        v = chlds[i]
        pval[v] = (1 + pref * cumulr[i]) % MOD
        pref *= (dp[v] + 1)
        pref %= MOD

for i in range(n):
    print(resp[i])
### BUGGY CODE ###

from collections import deque

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

cango = [[]for i in range(n)]
cannotgo=[[]for i in range(n)]
for i in range(m):
    a,b = (map(int,input().split()))
    a,b = a-1,b-1
    cango[a].append(b)
    cango[b].append(a)

for i in range(k):
    c,d =(map(int,input().split()))
    c,d = c-1,d-1
    cannotgo[c].append(d)
    cannotgo[d].append(c)
# print(a)
# cango = [[]for i in range(n)]
# for i in a:
#     cango[i[0]-1].append(i[1]-1)
#     cango[i[1]-1].append(i[0]-1)
# print(cango)

# cannotgo=[[]for i in range(n)]
# for i in c:
#     cannotgo[i[0]-1].append(i[1]-1)
#     cannotgo[i[1]-1].append(i[0]-1)
# # print(cannotgo)
alre = [False]*n
parent = [-1]*n
gro = {}

# print(gro)
for i in range(n):
    if alre[i]==True:
        continue
    gro[i]=set([i])
    stack = [i]
    while stack:
        x = stack.pop()
        alre[x]=True
        parent[x]=i
        for to in cango[x]:
            if alre[to]:
                continue
            # print(to)
            gro[i].add(to)
            stack.append(to)
# print(gro)
# print(parent)
ans = [0]*n
# print(ans)
for iam in range(n):
    group = gro[parent[iam]]
    tmp_ans = len(group)-len(cango[iam])-1
    for block in cannotgo[iam]:
        if block in group:
            tmp_ans -=1
    ans[iam]=tmp_ans
print(*ans, sep=' ')


### FIXED CODE ###

from collections import deque

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

cango = [[]for i in range(n)]
cannotgo=[[]for i in range(n)]
for i in range(m):
    a,b = (map(int,input().split()))
    a,b = a-1,b-1
    cango[a].append(b)
    cango[b].append(a)

for i in range(k):
    c,d =(map(int,input().split()))
    c,d = c-1,d-1
    cannotgo[c].append(d)
    cannotgo[d].append(c)
# print(a)
# cango = [[]for i in range(n)]
# for i in a:
#     cango[i[0]-1].append(i[1]-1)
#     cango[i[1]-1].append(i[0]-1)
# print(cango)

# cannotgo=[[]for i in range(n)]
# for i in c:
#     cannotgo[i[0]-1].append(i[1]-1)
#     cannotgo[i[1]-1].append(i[0]-1)
# # print(cannotgo)
alre = [False]*n
parent = [-1]*n
gro = {}
y = deque()
# print(gro)
for i in range(n):
    # if alre[i]==True:
    #     continue
    # gro[i]=set([i])
    y.append(i)
    leader = i
    cnt = 0 
    while len(y)>0:
        x = y.popleft()
        if parent[x]!=-1:
            continue
            # print(to)
        parent[x]=leader
        y.extend(cango[x])
        cnt +=1
    if cnt!=0:
        gro[leader]=cnt
# print(gro)
# print(parent)
ans = [0]*n
# print(ans)
for iam in range(n):
    # group = gro[parent[iam]]
    tmp_ans = gro[parent[iam]]
    tmp_ans -=1
    tmp_ans -= len(cango[iam])
    for block in cannotgo[iam]:
        if parent[block]==parent[iam] :
            tmp_ans -=1
    ans[iam]=tmp_ans
print(*ans, sep=' ')
### BUGGY CODE ###

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

sen = y//1000
for gosen in range(sen//5+1):
    for man in range((sen-gosen*5)//10+1):
        if y == man*10000+gosen*5000+(sen-gosen*5-man*10)*1000 and n == man+gosen+sen-gosen*5-man*10:
            print(man,gosen,sen-gosen*5-man*10)
            exit()

print(-1,-1,-1)

### FIXED CODE ###

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

for sen in range(n+1):
    for gosen in range(n+1-sen):
        man = n-sen-gosen
        if 1000*sen + 5000*gosen + 10000*man == y:
            print(man,gosen,sen)
            exit()

print(-1,-1,-1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

    for _ in range(min(30,K)):
        B = [0] * (N + 1)
        for i,a in enumerate(A):
            B[max(i - a,0)] += 1
            B[min(i + a + 1,N)] -= 1
        for i in range(N):
            B[i + 1] += B[i]
        A = B
    print(' '.join(map(str,A[:-1])))            
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

    for _ in range(min(100,K)):
        B = [0] * (N + 1)
        for i,a in enumerate(A):
            B[max(i - a,0)] += 1
            B[min(i + a + 1,N)] -= 1
        for i in range(N):
            B[i + 1] += B[i]
        A = B
    print(' '.join(map(str,A[:-1])))            
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N,W=map(int,input().split())
dp=[[0]*(W+1) for _ in range(N+1)]
for i in range(1,N+1):
  w,v=map(int,input().split())
  for j in range(1,W+1):
    if j>=w:
      dp[i][j]=max(dp[i-1][j-w]+v,dp[i-1][j])
    else:
      dp[i][j]=dp[i-1][j]
print(dp[N][W])

### FIXED CODE ###

N,W=map(int,input().split())
dp=[[0]*(W+1) for _ in range(N+1)]
for i in range(1,N+1):
  w,v=map(int,input().split())
  for j in range(1,W+1):
    if j>=w:
      dp[i][j]=max(dp[i-1][j-w]+v,dp[i-1][j])
    else:
      dp[i][j]=dp[i-1][j]
print(dp[N][W])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
n = int(input())
v = 10**5+2
e = [[] for i in range(2*v)]
for i in range(n):
    x,y = map(int,input().split())
    y += v
    e[x].append(y)
    e[y].append(x)
visit = [0]*(2*v)
def dfs(x):
    if not visit[x]:
        visit[x] = 1
        count[x//v] += 1
        for nex in e[x]:
            dfs(nex)
ans = 0
for i in range(v):
    if not visit[i]:
        count = [0]*2
        dfs(i)
        ans += count[0]*count[1]
print(ans-n)
    


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n = int(input())
v = 10**5+2
e = [[] for i in range(2*v)]
for i in range(n):
    x,y = map(int,input().split())
    y += v
    e[x].append(y)
    e[y].append(x)
visit = [0]*(2*v)
def dfs(x):
    if not visit[x]:
        visit[x] = 1
        count[x//v] += 1
        for nex in e[x]:
            dfs(nex)
ans = 0
for i in range(v):
    if not visit[i]:
        count = [0]*2
        dfs(i)
        ans += count[0]*count[1]
print(ans-n)
### BUGGY CODE ###

import fractions
def main():
  _=input()
  a=tuple(map(int,input().split()))
  aset=set(a)
  a1=a[0]
  fgcd=fractions.gcd
  for i in aset:
    if a1%i:
        a1=(i*a1)//fgcd(i,a1)
  x=[a1//i for i in a]
  print(sum(x)%(10**9+7))
  
if __name__ == '__main__':
    main()

### FIXED CODE ###

import fractions
from functools import reduce
def main():
  _=input()
  a=tuple(map(int,input().split()))
  fgcd=fractions.gcd
  def lcm_base(x, y):
    return (x * y) // fgcd(x, y)
  def lcm(numbers):
    return reduce(lcm_base, numbers, 1)
  q=lcm(a)
  x=[q//i for i in a]
  print(sum(x)%(10**9+7))
  
if __name__ == '__main__':
    main()
### BUGGY CODE ###

# Q2
H, W = map(int, input().split())
a = [[c for c in input()] for _h in range(H)]

compressed = False
while not compressed:
    compressed = False
    for h in range(H):
        if '#' not in a[h]:
            for w in range(W):
                a[h][w] = ''
                compressed = True
    for w in range(W):
        if '#' not in [p[w] for p in a]:
            for h in range(H):
                a[h][w] = ''
                compressed = True

for h in range(H):
    line = ''.join(a[h])
    if line:
        print(''.join(a[h]))

### FIXED CODE ###

# Q2
H, W = map(int, input().split())
a = [[c for c in input()] for _h in range(H)]


for h in range(H):
    if '#' not in a[h]:
        for w in range(W):
            a[h][w] = ''
for w in range(W):
    if '#' not in [p[w] for p in a]:
        for h in range(H):
            a[h][w] = ''

for h in range(H):
    line = ''.join(a[h])
    if line:
        print(''.join(a[h]))