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

import numpy as np

N = int(input())
m = [ int(i) for i in input().strip().split(" ")]

k_tmp = float(sum(m))/len(m)

k1 = int(np.ceil(k_tmp))
k2 = int(np.floor(k_tmp))

res1 = sum([(x-k1) * (x-k1) for x in m])
res2 = sum([(x-k2) * (x-k2) for x in m])
res = 0
if res1 > res2:
    res = res2
else:
    res = res1
print(res)

### FIXED CODE ###

import math

N = int(input())
m = [ int(i) for i in input().strip().split(" ")]

k_tmp = float(sum(m))/len(m)

k1 = int(math.ceil(k_tmp))
k2 = int(math.floor(k_tmp))

res1 = sum([(x-k1) * (x-k1) for x in m])
res2 = sum([(x-k2) * (x-k2) for x in m])
res = 0
if res1 > res2:
    res = res2
else:
    res = res1
print(res)
### BUGGY CODE ###

from collections import deque

def f1(x,y,xa,ya):
    if reach[xa][ya] > reach[x][y]:
         if c[xa][ya] == ".":
            reach[xa][ya] = reach[x][y]
            r.append([xa,ya])
            q.append([xa,ya])

def f2(x,y,xa,ya):
    if 0 <= xa <= h+1 and 0 <= ya <= w+1:
    
        if reach[xa][ya] > reach[x][y] + 1:
            if c[xa][ya] == ".":
                reach[xa][ya] = reach[x][y] + 1
                q.append([xa,ya])

h,w = map(int,input().split())
cx, cy = map(int,input().split())
dx, dy = map(int,input().split())

c = [0]*(h+2)
for i in range(1,h+1):
    c[i] = [0] + list(input()) + [0]
c[0]  = [0]*(w+2)
c[-1] = [0]*(w+2)

reach = [[float("Inf") for j in range(w+2)] for i in range(h+2)]
q = deque([])

reach[cx][cy] = 0
q.append([cx,cy])

ans = 0

while q:

    
    
    x,y = q.popleft()
    
    r = deque()
    r.append([x,y])
    while r:
        xx,yy = r.popleft()
        
        f1(xx,yy,xx-1,yy)
        f1(xx,yy,xx+1,yy)
        f1(xx,yy,xx,yy-1)
        f1(xx,yy,xx,yy+1)
    
    for i in range(-2,3):
        for j in range(-2,3):
            f2(x,y,x+i,y+j)

if reach[dx][dy] == float("Inf"):
    print(-1)
else:
    print(reach[dx][dy])


### FIXED CODE ###

from collections import deque
import time


def f1(x,y,xa,ya):
    if reach[xa][ya] == -1 or reach[xa][ya] > reach[x][y]:
         if c[xa][ya] == ".":
            reach[xa][ya] = reach[x][y]
            r.append([xa,ya])
            q.append([xa,ya])

            
            
def f2(x,y,xa,ya):
    if 0 <= xa <= h and 0 <= ya <= w:
    
        if reach[xa][ya] == -1 or reach[xa][ya] > reach[x][y] + 1:
            if c[xa][ya] == ".":
                reach[xa][ya] = reach[x][y] + 1
                q.append([xa,ya])

h,w = map(int,input().split())
cx, cy = map(int,input().split())
dx, dy = map(int,input().split())

t0 = time.time()

c = ["#"]*(h+2)
for i in range(1,h+1):
    c[i] = ["#"] + list(input()) + ["#"]
c[0]  = [0]*(w+2)
c[-1] = [0]*(w+2)

reach = [[-1 for j in range(w+2)] for i in range(h+2)]
q = deque([])

reach[cx][cy] = 0
q.append([cx,cy])

ans = 0

while q:
    
    if time.time() - t0 >= 1.5:
        break
    
    
    x,y = q.popleft()
    
    r = deque()
    r.append([x,y])
    while r:
        xx,yy = r.popleft()
        
        f1(xx,yy,xx-1,yy)
        f1(xx,yy,xx+1,yy)
        f1(xx,yy,xx,yy-1)
        f1(xx,yy,xx,yy+1)
    
    for i in range(-2,3):
        for j in range(-2,3):
            f2(x,y,x+i,y+j)


print(reach[dx][dy])
### BUGGY CODE ###

# coding: utf-8

N, M = (int(x) for x in input().split())

adj_list = [[] for i in range(N)]
for i in range(M):
	x, y, z = (int(x) for x in input().split())
	adj_list[x - 1].append(y - 1)
	adj_list[y - 1].append(x - 1)

searched = [False] * N
count = 0
for i in range(N):
	if searched[i] == True:
		continue

	count += 1
	stack = [i]
	while len(stack) > 0:
		node = stack.pop()
		searched[node] = True
		for n in adj_list[node]:
			if searched[n] == False:
				stack.append(n)

print(count)

### FIXED CODE ###

# coding: utf-8

N, M = (int(x) for x in input().split())

adj_list = [[] for i in range(N)]
for i in range(M):
	x, y, z = (int(x) for x in input().split())
	adj_list[x - 1].append(y - 1)
	adj_list[y - 1].append(x - 1)

searched = [False] * N
count = 0
for i in range(N):
	if searched[i] == True:
		continue

	count += 1
	stack = [i]
	searched[i] = True
	while len(stack) > 0:
		node = stack.pop()	
		for n in adj_list[node]:
			if searched[n] == False:
				stack.append(n)
				searched[n] = True

print(count)
### BUGGY CODE ###

import numpy as np
n = int(input())
A = [int(i) for i in input().split()]
ans = 1

for i in range(n):
    ans *= A[i]
    
if ans >pow(10,18):
    print(-1)
else:
    print(ans)
    

### FIXED CODE ###

n = int(input())
A = [int(i) for i in input().split()]
the = pow(10,18)
ans = 1

if 0 in A:
    print(0)
else:
    for i in range(n):
        ans *= A[i]
        if ans >the:
            print(-1)
            break
        else:
            continue
    if ans <= the:
        print(ans)
### BUGGY CODE ###

N, K = [int(i) for i in input().split()]
array = [int(i) for i in input().split()]

exv = [(1 + array[i]) / 2 for i in range(K)]
max_num = sum(exv)

for i in range(K, N):
    del exv[0]
    exv.append((1 + array[i]) / 2 )
    sum_exv = sum(exv)
    if sum_exv > max_num:
        max_num = sum_exv
print(max_num)

### FIXED CODE ###

import numpy as np

N, K = [int(i) for i in input().split()]
numbers = [int(i) for i in input().split()]

ary = np.array([(1 + n) / 2 for n in numbers])

cumsum = ary.cumsum()

max_exv = cumsum[K-1]
for i in range(N - K):
    if cumsum[i+K] - cumsum[i] > max_exv:
        max_exv = cumsum[i+K] - cumsum[i]
    
print(max_exv)
### BUGGY CODE ###

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

for aa in a:
    b.append(aa)
    b = b[::-1]

print(' '.join(map(str,b)))

### FIXED CODE ###

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

x,y = [],[]
for i in range(1,n+1):
    if i % 2 == 0:
        x.append(a[i-1])
    else:
        y.append(a[i-1])
if n % 2 == 0:
    print(" ".join(map(str,x[::-1])), " ".join(map(str,y)))
else:
    print(" ".join(map(str,y[::-1])), " ".join(map(str,x)))
### BUGGY CODE ###

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

for i in range(N - 1):
  head = H[i]
  remains = H[i + 1:]
  if head - min(remains) >= 2:
    print("No")
    break
else:
  print("Yes")

### FIXED CODE ###

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

head = 0

for i in range(N):
  if H[i] >= head:
    head = H[i]
  if head - H[i] >= 2:
    print("No")
    break
else:print("Yes")
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
gf = uf.all_group_members()
ans = 0
for i in gf.values():
    #print(i)
    ans = max(ans, len(i))
print(ans)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n, m = map(int, input().split())
if m == 0:
    print(1)
    exit()
uf = UnionFind(n)
ans = 0
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
    ans = max(ans, uf.size(a-1))
print(ans)
### BUGGY CODE ###

#E
from math import gcd
N=int(input())
A=list(map(int,input().split()))
GCD=A[0]
for i in range(1,N):
    GCD=gcd(GCD,A[i])
    
def Primefact(n):
    Dic={}
    for i in range(2,int(pow(n,0.5))+1):
        if n%i==0:
            Dic[i]=0
            while True:
                n/=i
                Dic[i]+=1
                if n%i!=0:
                    break
        if n==1:
            break
    if n!=1:
        Dic[int(n)]=1
    return Dic

if GCD==1:
    L=[False for i in range(10**6+1)]
    flag=False
    for i in range(N):
        Li=Primefact(A[i])
        for k,v in Li.items():
            if L[k]:
                flag=True
                break
            else:
                L[k]=True
    if flag:
        ans="setwise coprime"
    else:
        ans="pairwise coprime"
else:
    ans="not coprime"
print(ans)

### FIXED CODE ###

#E
from math import gcd
N=int(input())
A=list(map(int,input().split()))
GCD=A[0]
for i in range(1,N):
    GCD=gcd(GCD,A[i])
    
def Fast_PFact(n):
    List=[0 for i in range(n+1)]
    List[1]=1
    for i in range(2,n+1):
        if List[i]==0:
            cnt=1
            while i*cnt<=n:
                List[i*cnt]=i
                cnt+=1
    return List

if GCD==1:
    P=Fast_PFact(10**6)
    L=[False for i in range(10**6+1)]
    flag=False
    for i in range(N):
        a=A[i]
        while a>1:
            if L[P[a]]:
                flag=True
                break
                
            else:
                L[P[a]]=True
                divisor=P[a]
                while divisor==P[a]:
                    a=int(a/divisor)        
    if flag:
        ans="setwise coprime"
    else:
        ans="pairwise coprime"
else:
    ans="not coprime"
print(ans)
### BUGGY CODE ###

import sys,heapq
input = sys.stdin.readline

N,M = list(map(int,input().split()))
A = sorted(list(map(int,input().split())),reverse = 1)
rep = []
for _ in range(M):
    b,c = list(map(int,input().split()))
    tmp = [-c]*b
    rep = rep+tmp
rep=sorted(rep,reverse=1)[:N]
heapq.heapify(rep)

for i in range(N):
    if A[i] < -1 * rep[0]:
        heapq.heappush(rep,-1*A[i])
        A[i] = -1 * heapq.heappop(rep)
print(sum(A))


### FIXED CODE ###

import sys
input = sys.stdin.readline

def sol():
    N,M = list(map(int,input().split()))
    A = list(map(int,input().split()))
    tmp = sorted([list(map(int,input().split())) for _ in range(M)],key = lambda x:-x[1])

    t = []
    for a,b in tmp:
        t+=[b]*a
        
        if len(t) >=N:
            break

    A += t
    A.sort(reverse = 1)
    print(sum(A[:N]))

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

N = int(input())
List = list(map(int, input().split()))
num = 0

for i in range(N):
  if min(List[:i+1]) == List[i]:
    num += 1

print(num)

### FIXED CODE ###

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

import sys

N, X, Y = map(int, input().split())

d = [[sys.maxsize for _ in range(N)] for _ in range(N)]

for i in range(N):
  d[i][i] = 0
  if i == N-1:
    pass
  else:
    d[i][i+1] = 1
    d[i+1][i] = 1

d[X-1][Y-1] = 1
d[Y-1][X-1] = 1

for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j] = min(d[i][j], d[i][k] + d[k][j])

answer = [0 for _ in range(N-1)]

for h in range(N):
  for i in range(h+1, N):
    if h != i:
      answer[d[h][i]-1] += 1

for k in range(N-1):
  print(answer[k])

### FIXED CODE ###

import sys

N, X, Y = map(int, input().split())
X -= 1
Y -= 1

d = [[sys.maxsize for _ in range(N)] for _ in range(N)]

for i in range(N):
  for j in range(N):
    d[i][j] = min(abs(j-i), abs(X-i) + 1 + abs(j-Y), abs(Y-i) + 1 + abs(j-X))

answer = [0 for _ in range(N-1)]

for h in range(N):
  for i in range(h+1, N):
    if h != i:
      answer[d[h][i]-1] += 1

for k in range(N-1):
  print(answer[k])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
A = []
for i in range(n):
    rs = list(map(int, input().split()))
    rs = [r-1 for r in rs]
    A.append(rs)

cnts = [0] * n
days = 1
while True:
    tekis = []
    # print("Day",days, cnts)
    fin = 0
    for cnt,a in zip(cnts, A):
        if cnt == n-1: 
            tekis.append(-1)
            fin += 1
        else: 
            tekis.append(a[cnt])
    if fin == n: 
        print(days-1)
        exit()
    # 敵の敵が自分だったらマッチング成立
    flg = False
    matched = [False] * n
    for i,teki in enumerate(tekis):
        if matched[teki] or teki==-1:continue
        if tekis[teki] == i:
            cnts[i] += 1
            matched[i] = True
            cnts[teki] += 1
            matched[teki] = True
            flg = True
            # print("{}vs{}".format(i,teki))
    # マッチングが一つも成立しない
    if days > 50000:
        print(-1)
    if not flg:
        print(-1)
        exit()
    days += 1


### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict, deque
n = int(input())
X = 10000
INF = 1 << 50
edges = defaultdict(list)
edges_r = defaultdict(list)
def topological_sort(G):

    cnt_in = defaultdict(int)
    for k in G.keys():
        for v in G[k]:
            cnt_in[v] += 1
    # print(cnt_in)
    res = []
    # 入次数==0
    q = deque([i for i in list(G.keys()) if cnt_in[i]==0])
    while len(q) > 0:
        v = q.popleft()
        res.append(v)
        for next_v in G[v]:
            # 入次数を下げていく
            cnt_in[next_v] -= 1
            # 入次数が0に残ったところを次に追加
            if cnt_in[next_v] == 0:
                q.append(next_v)
    # トポソ不可能！
    if len(G) != len(res):
        print(-1)
        exit()
    return res

for i in range(n):
    r = list(map(int, input().split()))
    # 初期
    mn = min(i, r[0]-1)
    mx = max(i, r[0]-1)
    prev = mn * n + mx
    for e in r[1:]:
        e -= 1
        mn = min(i,e)
        mx = max(i,e)
        now = mn*n+mx
        edges[prev].append(now)
        edges_r[now].append(prev)
        prev = now
vs = topological_sort(edges)

# トポソの順番で経路長を入れていく
used = [0] * n**2
# for V in vs:
#     if used[V]: continue
#     used[V] = 1
#     q = deque([V])
#     while len(q) > 0:
#         v = q.popleft()
#         for u in edges[v]: 
#             if used[u] <= used[v]:
#                 q.append(u)
#                 used[u] = max(used[u], used[v] + 1)

for V in vs:
    if used[V]:continue
    used[V] = 1
    mx = 1
    for b in edges_r[V]:
        mx = max(mx, used[b]+1)
    used[V] = mx
# print(used)
print(max(used))
### BUGGY CODE ###

N = int(input())
counter =-1 
number = 0
for i in range(N):
    k = i
    now_counter = 0
    while(k % 2 == 0):
        now_counter += 1
        k /= 2
    if(now_counter > counter):
        number = i
print(number)


### FIXED CODE ###

N = int(input())
counter =-1 
number = 0
for i in range(N):
    k = i+1
    now_counter = 0
    while(k % 2 == 0):
        now_counter += 1
        k /= 2
    if(now_counter > counter):
        number = i+1
        counter = now_counter
print(number)
### BUGGY CODE ###

n = int(input())

ans =  0

for i in range(1, n):
  for j in range(1, (n - 1) // i + 1):
    if i * j <= n - 1:
      ans += 1
    
print(ans)

### FIXED CODE ###

n = int(input())

ans =  0

for i in range(1, n):
  ans += (n - 1) // i 
    
print(ans)
### BUGGY CODE ###

import sys
from collections import deque

N = int(input())
A = [deque([int(i) for i in input().split()]) for i in range(N)]

ans=0
empty = [deque() for n in range(N)]

while True:
    change=0
    stamina=[1]*N
    for g in range(N):
        if A[g]!=deque() and stamina[g]==1 and stamina[A[g][0]-1]==1:
            if g+1 == A[A[g][0]-1][0]:
                _pop = A[g].popleft()
                A[_pop-1].popleft()
                stamina[g]=0
                stamina[_pop-1]=0
                change=1
    ans+=1
    if change==0:
        break
    if A==empty:
        print(ans)
        sys.exit()

print(-1)

### FIXED CODE ###

import sys
from collections import deque

N = int(input())
A = [deque([int(i) for i in input().split()]) for i in range(N)]

ans=0
empty = [deque() for i in range(N)]
pre_fight = set([i for i in range(N)])
record = set()

while True:
    for g in pre_fight:
        if A[g]!=deque():
            if g+1 == A[A[g][0]-1][0]:
                record.add(g)
                record.add(A[g][0]-1)
    if record==set():
        break
    else:
        for i in record:
            A[i].popleft()
    ans+=1
    pre_fight = record
    record = set()
    if A==empty:
        print(ans)
        sys.exit()

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

def p_e():
    h, w = map(int, input().split())
    t = [list(map(int, input().split())) for _ in range(h)]
    m = 0
    for i in range(h):
        *b, = map(int, input().split())
        for j, e in enumerate(b):
            t[i][j] = abs(t[i][j] - e)
            if m < abs(t[i][j] - e):
                m = abs(t[i][j] - e)

    # dp[i][j][k]: (i,j)でkになるかどうかbool値
    bool_width = 6400
    dp = [[[False] * bool_width for _ in range(w)] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if i == j == 0:
                dp[i][j][t[i][j]] = True
                continue
            for k in range(bool_width):
                if i > 0:
                    if abs(k + t[i][j]) < bool_width:
                        dp[i][j][k] |= dp[i - 1][j][abs(k + t[i][j])]
                    if abs(k - t[i][j]) < bool_width:
                        dp[i][j][k] |= dp[i - 1][j][abs(k - t[i][j])]
                if j > 0:
                    if abs(k + t[i][j]) < bool_width:
                        dp[i][j][k] |= dp[i][j - 1][abs(k + t[i][j])]
                    if abs(k - t[i][j]) < bool_width:
                        dp[i][j][k] |= dp[i][j - 1][abs(k - t[i][j])]
    for i, e in enumerate(dp[-1][-1]):
        if e:
            print(i)
            break
            
p_e()

### FIXED CODE ###

def p_e():
    from itertools import product
    h, w = map(int, input().split())
    t1 = [list(map(int, input().split())) for _ in range(h)]
    t2 = [list(map(int, input().split())) for _ in range(h)]

    # pythonでbitsetを用いる->boolのDPで2進数の1をTrue, 0をFalseとして扱う
    # 右にxシフト = その値にx足した値    (10001)<<4 -> (100010000)
    m = 160 * 80
    dp = [[0] * w for _ in range(h)]
    dp[0][0] = 1 << m
    for i, j in product(range(h), range(w)):
        v = abs(t1[i][j] - t2[i][j])
        if i > 0:
            dp[i][j] |= dp[i - 1][j]
        if j > 0:
            dp[i][j] |= dp[i][j - 1]
        dp[i][j] = (dp[i][j] << v) | (dp[i][j] >> v)

    ans = m
    for i in range(m * 2):
        if dp[h - 1][w - 1] & (1 << i) > 0:
            ans = min(ans, abs(m - i))
    print(ans)
    
p_e()
### BUGGY CODE ###

### https://atcoder.jp/contests/dp/tasks/dp_d
N,W = map(int,input().split())
Goods_List=[]
for i in range(N):
    Goods_List.append(list(map(int,input().split())))

dp={0:0}
for i in range(N):
    Current_Weight = Goods_List[i][0]
    Current_Value  = Goods_List[i][1]
    if (i == 0) & (Current_Weight <= W) :
        dp[Current_Weight] = Current_Value
    elif i > 0:
        Last_Search_List = list(dp.keys())
        Current_Search_List = list(map(lambda x:x+Current_Weight,Last_Search_List))
        for j in range(len(Current_Search_List)):
            Last_Search_Weight = Last_Search_List[j]
            Current_Search_Weight = Current_Search_List[j]
            if Current_Search_Weight in dp:
                dp[Current_Search_Weight] = max(dp[Current_Search_Weight],
                                                dp[Last_Search_Weight] + Current_Value)
            elif Current_Search_Weight <= W :
                dp[Current_Search_Weight] = dp[Last_Search_Weight] + Current_Value

print(max(dp.values()))

### FIXED CODE ###

#https://atcoder.jp/contests/dp/tasks/dp_e
import copy
N,W = map(int,input().split())
Goods_List=[]
for i in range(N):
    Goods_List.append(list(map(int,input().split())))
 
Sum_Value = sum(map(lambda x:x[1],Goods_List))
dp = [[0] * (Sum_Value + 1) for i in range(N)]

for i in range(N):
    if i == 0:
        dp[i][Goods_List[i][1]] = Goods_List[i][0]
    else:
        dp[i] = copy.copy(dp[i-1])
        Valid_List = [k for k, x in enumerate(dp[i]) if x != 0]
        Valid_List.append(0)
        for j in Valid_List:
            if dp[i][j + Goods_List[i][1]] == 0:
                dp[i][j + Goods_List[i][1]] = dp[i-1][j] + Goods_List[i][0]
            else:
                dp[i][j + Goods_List[i][1]] = min(dp[i-1][j] + Goods_List[i][0],dp[i][j + Goods_List[i][1]])
        

for k in range(len(dp[-1])-1,0,-1):
    if (dp[-1][k] != 0) & (dp[-1][k] <= W):
        print(k)
        break
### BUGGY CODE ###

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

count = 0

for i in range(len(s)):
    for j in range(i + 1, len(s)):
        if s[i] != s[j]:
            for k in range(j + 1, len(s)):
                if ((k - j) != (j - i)) and (s[i] != s[k]) and (s[j] != s[k]):
                    count += 1

print(count)



### FIXED CODE ###

import math

k = int(input())
n = input()

r = n.count("R")
g = n.count("G")
b = n.count("B")

ans = r*g*b

for i in range(k):
    
    for j in range(i + 1, math.ceil((k + i)/2)):
        
        if (n[i] != n[j]) and (n[2*j - i] != n[i]) and (n[j] != n[2*j - i]):
            ans -= 1

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

from collections import deque
n=int(input())
tree=[[] for _ in range(n+1)]
for i in range(1,n):
  a,b=map(int,input().split())
  tree[a].append([b,i])
  tree[b].append([a,i])
queue=deque([[1,1]])
ans=[-1]*(n+1)

while queue:
  v,i=queue.popleft()
  color=1
  for nv,j in tree[v]:
    if ans[i]==color:
      color+=1
    if not ans[nv]==-1:
      continue
    queue.append([nv,color])
    ans[j]=color
    color+=1
print(max(ans))
for i in range(1,n):
  print(ans[i])

### FIXED CODE ###

from collections import deque
n=int(input())
tree=[[] for _ in range(n+1)]
for i in range(1,n):
  a,b=map(int,input().split())
  tree[a].append([b,i])
  tree[b].append([a,i])
queue=deque([[1,0]])
ans=[0]*(n+1)
ans[1]=1
visited=[0]*(n+1)

while queue:
  v,c=queue.popleft()
  color=1
  for nv,i in tree[v]:
    if c==color:
      color+=1
    if visited[i]==1:
      continue
    visited[i]=1
    queue.append([nv,color])
    ans[i]=color
    color+=1
print(max(ans))
for i in range(1,n):
  print(ans[i])
### BUGGY CODE ###

import numpy as np

n, k = map(int, input().split())
a = np.array(input().split(), dtype=np.int64)

for j in range(k):
    b = np.zeros(n+1, dtype=np.int64)
    for i in range(n):
        b[max(i-a[i], 0)] += 1
        b[min(i+a[i]+1, n)] -= 1
    a = np.cumsum(b)[:-1]
print(*a)


### FIXED CODE ###

import sys
import numpy as np
from numba import njit

readline = sys.stdin.readline

@njit('i8,i8,i8[::1]',cache=True)
def loop(n,k,a):
    for j in range(k):
        b = np.zeros(n+1, dtype=np.int64)
        for i in range(n):
            b[max(i-a[i], 0)] += 1
            b[min(i+a[i]+1, n)] -= 1
        a = np.cumsum(b)[:-1]
        if np.all(a==n):
            return(a)
            break
    else:
        return(a)


n, k = map(int, readline().split())
a = np.array(readline().split(), dtype=np.int64)

ans = loop(n,k,a)
print(*ans)