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

import numpy as np
import collections

alpha2num = lambda c:ord(c) - ord('a')

N = int(input())
D = np.zeros([26,N])
SUM = 0

for n in range(N):
  s = input()
  c = collections.Counter(s)
  for _c in c.keys():
    i = alpha2num(_c)
    D[i, n] = c[_c]

for n in range(N):
  d = D[:,n]
  d = d.reshape(len(d),1)
  diff = D - np.dot(d,np.ones([1,N]))
  count = sum(np.square(diff))
  k = np.count_nonzero(count == 0)
  SUM = SUM + k
  
print('%d' % ((SUM-N)/2))
  

### FIXED CODE ###

N = int(input())
D = {}
SUM = 0

for n in range(N):
  s = input()
  l = sorted(s)
  l = ''.join(l)
  
  if l in D:
    SUM = SUM + D[l]
    D[l] = D[l] + 1
  else:
    D[l] = 1
  
print(SUM)
### BUGGY CODE ###

from collections import deque
from itertools import product


def read():
    H, W = list(map(int, input().split()))
    S = ''
    S += ('#' * (W+2))
    for h in range(H):
        buf = input()
        S += '#' + buf + '#'
    S += ('#' * (W+2))
    return H, W, S


def bfs(yx, H, W, S):
    dirs = [1, W+2, -1, -W-2]
    visited = [False for i in range((H+2) * (W+2))]
    q = deque()
    q.appendleft((yx, 0))
    max_depth = 0
    while len(q) > 0:
        yx, depth = q.pop()
        visited[yx] = True
        max_depth = max(max_depth, depth)
        for dyx in dirs:
            nyx = yx + dyx
            if S[nyx] == '.' and not visited[nyx]:
                q.appendleft((nyx, depth+1))
    return max_depth


def solve(H, W, S):
    dist_max = 0
    for yx in range((H+2) * (W+2)):
        if S[yx] == '.':
            d = bfs(yx, H, W, S)
            dist_max = max(d, dist_max)
    return dist_max


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


### FIXED CODE ###

from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


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

s=input()
s=s[::-1]

n=len(s)
modlist=[[0 for i in range(13)]for _ in range(n+1)]

#13で割ったあまりの判定方法
if s[0]!="?":
    modlist[0][int(s[0])]=1
elif s[0]=="?":
    for  i in range(10):
        modlist[0][i]=1
for i in range(1,n):
    if s[i]!="?":
        add=(int(s[i])*(10**(i)))%13
        for  j in range(13):
            modlist[i][j]+=modlist[i-1][(j-add)%13]
            modlist[i][j]%(10**9+7)
            

    else:
        for nums in range(10):
                add=nums*(10**i)%13
                for  j in range(13):
                    modlist[i][j]+=modlist[i-1][(j-add)%13]
                    modlist[i][j]=modlist[i][j]%(10**9+7)

print(modlist[-2][5])                
            


### FIXED CODE ###

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m
def main():
    s=list(input())
    mod=10**9+7
    K=modinv(10,13)
    U=[[0 for i in range(10) ]for k in range(13)]
    for i in range(13):
        for j in range(10):
            U[i][j]=((i-j)*K)%13

    dp=[[0 for k in range(13)] for i in range(len(s))]
    #dp[i][j]=初めのindex=i番目まで見たときに、あまりがjになるような方法の総数
    num=s[0]
    if s[0]=="?":
        for i in range(10):
            dp[0][i]=1
    else:
        number=int(s[0])
        dp[0][number]=1

    for i in range(1,len(s)):
        for k in range(13):
            if s[i]=="?":
                for j in range(10):
                    dp[i][k]+=dp[i-1][U[k][j]]%mod
            else:
                number=int(s[i])
                dp[i][k]=dp[i-1][U[k][number]]%mod
    print(dp[len(s)-1][5]%mod)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import math
import sys

def part_sum(a,A):
  N=len(a)
  dp=[[0 for i in range(A+1)] for j in range(N+1)]
  dp[0][0]=1

  for i in range(N):
    for j in range(A+1):
      if a[i]<=j: 
        dp[i+1][j]=dp[i][j-a[i]] or dp[i][j]
      else: 
        dp[i+1][j]=dp[i][j]
  return dp[N][A]

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

s=sum(a)
s_factors=[]

l=int(math.sqrt(s))

for i in range(1,l+1):
    if s%i==0:
        s_factors.append(i)
        s_factors.append(s//i)

s_factors.sort()

for f in s_factors[::-1]:
    b=[a[i]%f for i in range(n)]
    c=[f-a[i]%f for i in range(n)]
    
    b.sort()
    c.sort()
    c=c[::-1]

    for i in range(n):
        if sum(b[:i+1])==sum(c[i+1:]):
            if sum(b[:i+1])<=k:
                print(f)
                sys.exit()

### FIXED CODE ###

import math
import sys

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

s=sum(a)
s_factors=[]

l=int(math.sqrt(s))

for i in range(1,l+1):
    if s%i==0:
        s_factors.append(i)
        s_factors.append(s//i)

s_factors.sort()

for f in s_factors[::-1]:
    b=[a[i]%f for i in range(n)]
    c=[f-a[i]%f for i in range(n)]
    
    b.sort()
    c.sort()
    c=c[::-1]

    sb=[0 for i in range(n)]
    sc=[0 for i in range(n)]
    
    sb[0]=b[0]
    sc[0]=c[0]

    for i in range(1,n):
        sb[i]=sb[i-1]+b[i]

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

    for i in range(n):
        if sb[i]==sc[n-1]-sc[i]:
            if sb[i]<=k:
                print(f)
                sys.exit()
### BUGGY CODE ###

import math
import numpy as np

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
  
def set_list(es):
  return len(list(set(es))) == 1
  
n = int(input())
n_list = [int(i) for i in input().split()] 

np_list = np.array(n_list)
min1_idx = np.argmin(np_list)
min1 = min(np_list)
np_list[min1_idx] = 10000000001
min2_idx = np.argmin(np_list)
min2 = min(np_list)

div_list = make_divisors(min1) + make_divisors(min2)
div_set = set(div_list)

for s in reversed(sorted(list(div_set))):
  if set_list(n_list):
    print(n_list[0])
    break  
  count = 0
  j = 0
  for x in n_list:
    if n_list[j] % s == 0:
      #print(s)
      #print(n_list[j] % s)
      count += 1
    j += 1
  if count >= n - 1:
    print(s)
    break
  
      

      
  






### FIXED CODE ###

import math
import numpy as np

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
  
def set_list(es):
  return len(list(set(es))) == 1
  
n = int(input())
n_list = [int(i) for i in input().split()] 

if set_list(n_list):
    print(n_list[0])
else:
  min1 = min(n_list)
  n_list.remove(min1)
  min2 = min(n_list)
  n_list.append(min1)

  div_list = make_divisors(min1) + make_divisors(min2)
  div_set = set(div_list)
  div_list = sorted(list(div_set))

  k = 0
  length = len(div_set)
  while k < length: 
    s = div_list[length - k - 1]
    count = 0
    j = 0
    for x in n_list:
      if n_list[j] % s == 0:
        count += 1
      j += 1
    if count >= n - 1:
      print(s)
      break
      
    k += 1
### BUGGY CODE ###

r,g,b,n = map(int,input().split())
count = 0
rr = n // r
for i in range(rr+1):
  for j in range((n-i*r)//g+1):
    if n >= i*r + j*g and (n - (i*r + j*g)) %  b == 0:
        count += 1
print(count)


### FIXED CODE ###

r,g,b,n = map(int,input().split())
count = 0
rr = n // r
for i in range(rr+1):
  for j in range((n-i*r)//g+1):
    tmp = n - (i*r + j*g)
    if tmp >= 0 and tmp %  b == 0:
        count += 1
print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, W = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(N)]

INFTY = -1
MAX_V = 10**5
dp = [[INFTY]*(MAX_V+1) for _ in range(N)]
dp[0][S[0][1]] = S[0][0]

for i in range(1, N):
    w, v = S[i]
    for j in range(v):
        dp[i][j] = dp[i-1][j]

    if dp[i-1][v] == -1:
        dp[i][v] = w
    else:
        dp[i][v] = min(dp[i-1][v], w)

    for j in range(v+1, MAX_V+1):
        if dp[i-1][j] == -1 and dp[i-1][j-v] == -1:
            continue
        elif dp[i-1][j] == -1:
            if dp[i-1][j-v]+w > W:
                continue
            else:
                dp[i][j] = dp[i-1][j-v]+w
        elif dp[i-1][j-v] == -1:
            dp[i][j] = dp[i-1][j]
        else:
            if dp[i-1][j-v]+w > W:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-v]+w)

for i in range(MAX_V, 0, -1):
    if dp[N-1][i] != -1:
        print(i)
        break


### FIXED CODE ###

import sys
input = sys.stdin.readline

N, W = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(N)]

INFTY = -1
MAX_V = 10**5
dp = [[INFTY]*(MAX_V+1) for _ in range(N)]
dp[0][S[0][1]] = S[0][0]

for i in range(1, N):
    w, v = S[i]
    for j in range(v):
        dp[i][j] = dp[i-1][j]

    if dp[i-1][v] == -1:
        dp[i][v] = w
    else:
        dp[i][v] = min(dp[i-1][v], w)

    for j in range(v+1, MAX_V+1):
        if dp[i-1][j] == -1 and dp[i-1][j-v] == -1:
            continue
        elif dp[i-1][j] == -1:
            if dp[i-1][j-v]+w > W:
                continue
            else:
                dp[i][j] = dp[i-1][j-v]+w
        elif dp[i-1][j-v] == -1:
            dp[i][j] = dp[i-1][j]
        else:
            if dp[i-1][j-v]+w > W:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-v]+w)

for i in range(MAX_V, 0, -1):
    if dp[N-1][i] != -1:
        print(i)
        break
### BUGGY CODE ###

import numpy as np
n = int(input())
a = list(map(int,input().split()))
dp = np.full((2, n//2 + 1), -10**18, dtype=np.int64)
"""
dp[i][j] := iは偶奇, jは何個決めるか
"""
dp[0][0] = 0
dp[1][0] = 0
for i in range(n):
	k = i % 2
	dp[k][1:] = np.maximum(dp[1-k][1:], dp[k][:-1]+a[i])

print(max(dp[0][n//2], dp[1][n//2]))

### FIXED CODE ###

import numpy as np
n = int(input())
a = list(map(int,input().split()))
dp = np.full((2, n//2 + 1), -10**18, dtype=np.int64)
"""
dp[i][j] := iは偶奇, jは何個決めるか
"""
dp[0][0] = 0
dp[1][0] = 0
for i in range(n):
	k = i % 2
	for j in [2, 1, 0]:
		if i//2+j <= n//2:
			if i//2-1+j >= 0:
				dp[k][i//2+j] = np.maximum(dp[1-k][i//2+j], dp[k][i//2-1+j]+a[i])

print(max(dp[0][n//2], dp[1][n//2]))
### BUGGY CODE ###

S = input()

ans = 0
_MOD = {0:1}

for i in range(len(S)):
    j = int(S[i:]) % 2019
    if j in _MOD:
        _MOD[j] = _MOD[j] + 1
    else:
        _MOD[j] = 1
        
for i in _MOD:
    m= _MOD[i]
#    ans += (_MOD[i] * (_MOD[i] - 1)) // 2
    ans += (m * (m - 1)) // 2

print(ans)

### FIXED CODE ###

S = input()[::-1]


_MOD = {0: 1}
amari = 0
a = 1
ans = 0

for i in S:
    amari = (amari + int(i) * a) % 2019
    a = (a * 10) % 2019  #表示桁 1あたりの余
    if amari in _MOD:
        _MOD[amari] = _MOD[amari] + 1
    else:
        _MOD[amari] = 1
    
for amari in _MOD:
    m = _MOD[amari]
    ans += (m * (m - 1)) // 2

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

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    l = 29
    val = 0
    from bisect import bisect_left as bl, bisect_right as br

    for k in range(l):
        # i桁目を求める
        tmp = pow(2, k+1)
        bb = [item%(tmp) for item in b]
        bb.sort()
        ans = 0
        for item in a:
            aa = item%tmp
            if aa<=tmp//2:
                ans += (br(bb, tmp-1-aa) - bl(bb, tmp//2-aa))%2
            else:
                ans += (br(bb, tmp-1-aa) + (n - bl(bb, tmp//2*3-aa)))%2
        if ans%2:
            val += pow(2, k)
    print(val)
main()

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = 29
val = 0

def lcount(a,b,x):
    """ソート済a,bに対して, a[i]+b[j]<=xなるi,jの個数
    """
    la = len(a)
    lb = len(b)
    j = -1
    ans = 0
    for i in range(la-1, -1, -1):
        while j+1<lb and a[i]+b[j+1]<=x:
            j += 1
        ans += (j+1)
    return ans
for k in range(l):
    # i桁目を求める
    tmp = pow(2, k+1)
    bb = [item%(tmp) for item in b]
    aa = [item%(tmp) for item in a]
    aa.sort()
    bb.sort()
    ans = n**2 - lcount(aa,bb,tmp//2*3-1) + lcount(aa,bb,tmp-1) - lcount(aa,bb,tmp//2-1)
    if ans%2:
        val += pow(2, k)
print(val)
### BUGGY CODE ###

import math


def f(a: float, b: float, theta: float) -> float:
    # 求める角度をθとすると三角形の底辺はb*tan(π/2-θ)となる
    # つまり以下の条件を満たす最大のθを求めればよい
    # b*tan(π/2-θ) * b * 1/2 >= x / a
    if theta > (90.0 - 0.0000000001):
        return 0.0
    t = b * math.tan(math.radians(90.0 - theta))
    if t <= a:
        return b * t / 2
    else:
        top = b - (a * math.tan(math.radians(theta)))
        return (b + top) * a / 2


def water_bottle(a: int, b: int, x: int) -> float:
    ok = 90.0
    ng = 0.0
    water = x / a
    for _ in range(100000):
        mid = (ok + ng) / 2.0
        if f(a, b, mid) < water:
            ok = mid
        else:
            ng = mid
    return ok


if __name__ == '__main__':
    abx = list(map(int, input().split()))
    result = water_bottle(abx[0], abx[1], abx[2])
    print(result)

### FIXED CODE ###

import math


def f(a: float, b: float, theta: float) -> float:
    # 求める角度をθとすると三角形の底辺はb*tan(π/2-θ)となる
    # つまり以下の条件を満たす最大のθを求めればよい
    # b*tan(π/2-θ) * b * 1/2 >= x / a
    if theta > (90.0 - 0.0000000001):
        return 0.0
    t = b * math.tan(math.radians(90.0 - theta))
    if t <= a:
        return b * t / 2
    else:
        top = b - (a * math.tan(math.radians(theta)))
        return (b + top) * a / 2


def water_bottle(a: int, b: int, x: int) -> float:
    ok = 90.0
    ng = 0.0
    water = x / a
    for _ in range(10000):
        mid = (ok + ng) / 2.0
        if f(a, b, mid) < water:
            ok = mid
        else:
            ng = mid
    return ok


if __name__ == '__main__':
    abx = list(map(int, input().split()))
    result = water_bottle(abx[0], abx[1], abx[2])
    print(result)
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    tot = 0
    while A:
        A.pop()
        tot += A.pop()
        A.pop(0)
    return tot
 
if __name__ == '__main__':
    print(main())

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    tot = 0
    for i in range(N):
        tot += A[3*N-2-2*i]
    return tot
if __name__ == '__main__':
    print(main())
### BUGGY CODE ###

N = int(input())

A = []
for i in range(N):
    A.append(int(input()))
    
for i in range(N):
    tmp = A[i]
    A[i] = 0
    print(max(A))
    A[i] = tmp

### FIXED CODE ###

N = int(input())

A = []
for i in range(N):
    A.append(int(input()))

M = sorted(A)

for i in range(N):
    if A[i] == M[-1]:
        print(M[-2])
    else:
        print(M[-1])
### BUGGY CODE ###

N,M = map(int,input().split())
former_set = set()
for i in range(M):
  a,b =  map(int, input().split())
  if i != 0: 
    tmp_set = { i for i in range(a,b+1)}
    former_set = tmp_set & former_set
  else:
    former_set = { i for i in range(a,b+1)}
print(len(former_set))

### FIXED CODE ###

N,M = map(int,input().split())
a = list()
b = list()
for i in range(M):
  tmp_a,tmp_b =  map(int, input().split())
  a.append(tmp_a)
  b.append(tmp_b)
print(min(b)-max(a)+1 if min(b)-max(a) >= 0 else 0)
### BUGGY CODE ###

N, Q =map(int,input().split())
S =input()
for _ in range(Q):
  l,r = map(int,input().split())
  print(S[l-1:r].count("AC"))
  

### FIXED CODE ###

import sys
imput =sys.stdin.readline
N, Q =map(int,input().split())
S =[i for i in input()]
q = [[int(i) for i in input().split()] for _ in range(Q)]
num = 0
for i in range(N-1):
    if S[i]+S[i+1]=="AC":
        num += 1
    S[i] = num
S[-1] = num
S.append(0)
for lr in q:
  print(S[lr[1]-2] -S[lr[0]-2])
### BUGGY CODE ###

def main():
    n, k = (int(x)for x in input().split())
    if n <= k:
        print(0)
        return
    hl = [int(x)for x in input().split()]
    hl = sorted(hl, reverse=1)
    for x in range(1, k+1):
        hl = hl[1:]
    print(sum(hl))


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, k = (int(x) for x in input().split())
    if n <= k:
        print(0)
        return
    hl = [int(x) for x in input().split()]
    hl = sorted(hl, reverse=1)[k:]
    print(sum(hl))


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

from itertools import permutations

n,m,r = map(int,input().split())
R = list(map(int,input().split()))
inf = 10**9

edges=[[inf for i in range(n+1)] for i in range(n+1)]

for i in range(m):
  a,b,c = map(int,input().split())
  edges[a][b] = c
  edges[b][a] = c


for k in range(1,n+1):
  for i in range(1,n):
    for j in range(i,n+1):
      edges[i][j] = min(edges[i][k]+edges[k][j], edges[i][j])
      edges[j][i] = edges[i][j]

# print(edges)

ans = inf
for i in permutations(R):
  tmp = 0
  for j in range(r-1):
    tmp += edges[i[j]][i[j+1]]
  ans = min(tmp, ans)

print(ans)

### FIXED CODE ###

from itertools import permutations

n,m,r = map(int,input().split())
R = list(map(int,input().split()))
inf = 10**9

edges=[[inf for i in range(n+1)] for i in range(n+1)]

for i in range(m):
  a,b,c = map(int,input().split())
  edges[a][b] = c
  edges[b][a] = c


for k in range(1,n+1):
  for i in range(1,n):
    for j in range(i,n+1):
      if edges[i][j] > edges[i][k] + edges[k][j]:
        edges[i][j] = edges[i][k]+edges[k][j]
        edges[j][i] = edges[i][j]


ans = inf
for i in permutations(R):
  tmp = 0
  for j in range(r-1):
    tmp += edges[i[j]][i[j+1]]
  ans = min(tmp, ans)

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

from bisect import bisect
from time import time

st_time = time()
N = int(input())
src = list(map(int,input().split()))

cums = [0]
for a in src:
    cums.append(cums[-1] + a)

ans = cums[-1] * 999
c = bisect(cums, cums[-1]//2)
d = 1
while time() - st_time < 1.94:
    if abs(d) >= N: break
    if 2 <= c <= N-2:
        b1 = bisect(cums[:c], cums[c]//2)
        b2 = bisect(cums[c:], (cums[c]+cums[-1])//2) + c
        pq_cands = []
        for i in (b1,b1-1):
            if not 0 < i < c: continue
            p = cums[i]
            q = cums[c] - cums[i]
            pq_cands.append((p,q))
        rs_cands = []
        for i in (b2,b2-1):
            if not c < i < N: continue
            r = cums[i] - cums[c]
            s = cums[-1] - cums[i]
            rs_cands.append((r,s))
        for p,q in pq_cands:
            for r,s in rs_cands:
                mn = min(p,q,r,s)
                mx = max(p,q,r,s)
                ans = min(ans, mx-mn)
    c += d
    d = (abs(d)+1) * [1,-1][d%2]
print(ans)

### FIXED CODE ###

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

cums = [0]
for a in src:
    cums.append(cums[-1] + a)

ps = [None] * (N+1)
qs = [None] * (N+1)
rs = [None] * (N+1)
ss = [None] * (N+1)

l = 1
for r in range(2,N-1):
    p1 = cums[l]
    q1 = cums[r] - cums[l]
    d1 = abs(p1-q1)
    while l < r:
        p2 = cums[l+1]
        q2 = cums[r] - cums[l+1]
        d2 = abs(p2-q2)
        if d2 > d1: break
        l += 1
        p1,q1,d1 = p2,q2,d2
    ps[r] = p1
    qs[r] = q1

r = N-1
for l in range(N-2,1,-1):
    r1 = cums[r] - cums[l]
    s1 = cums[N] - cums[r]
    d1 = abs(r1-s1)
    while l < r:
        r2 = cums[r-1] - cums[l]
        s2 = cums[N] - cums[r-1]
        d2 = abs(r2-s2)
        if d2 > d1: break
        r -= 1
        r1,s1,d1 = r2,s2,d2
    rs[l] = r1
    ss[l] = s1

ans = cums[-1] * 999
for p,q,r,s in zip(ps,qs,rs,ss):
    if p is None: continue
    tmp = max(p,q,r,s) - min(p,q,r,s)
    ans = min(ans, tmp)
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
s=0
for i in range(0,N):
    for j in range(i+1,N):
        if A[i]==A[j]:
            s=s+1
if s==0:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

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

if len(A)==len(set(A)):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,K = map(int,input().split())
A = list(map(int,input().split()))
if N == 1:
    print(1)
else:
    if True:
        old = A
        for _ in range(K):
            li = [0]*N
            for i in range(N):
                MIN = max(0,i-old[i])
                MAX = min(N-1,i+old[i])
                li[MIN] += 1
                if MAX != N-1:
                    li[MAX+1] -= 1
            old = accumulate(li)
            old = list(old)
            if min(old) == N:
                break
        print(*old)


### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,K = map(int,input().split())
A = list(map(int,input().split()))
if N == 1:
    print(1)
else:
    
    old = A
    for _ in range(K):
        li = [0]*N
        for i in range(N):
            MIN = max(0,i-old[i])
            MAX = min(N-1,i+old[i])
            li[MIN] += 1
            if MAX != N-1:
                li[MAX+1] -= 1
        s = 0
        for i in range(N):
            s += li[i]
            old[i] = s
        if min(old) == N:
            break
    print(*old)