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

import numpy as np
import heapq

INF=10**12
def daik(s,g,d,adj):
    used=np.array([])
    heap=[]
    table=np.array([INF for i in range(N)])
    table[s]=0
    heapq.heappush(heap,(table[s],s))
    used=np.append(used,s)
                
    while heap and not(g in used):
        q=heapq.heappop(heap)
        a=q[1]
        used=np.append(used,a)
        for i in adj[a]:
            if not(i in used):
                cost=d[a,i] 
                if cost!=INF:
                    table[i]=min(table[i],table[a]+cost)
                    heapq.heappush(heap,(table[i],i))
    return table[g]

N,M=map(int,input().split())
LRC=[]
for i in range(M):
    L,R,C=map(int,input().split())
    LRC.append([L-1,R-1,C])
LRC=np.array(LRC)
LRC=LRC[np.argsort(LRC[:,2])][::-1]

d=np.array([[INF for j in range(N)] for i in range(N)])
adj=[[] for i in range(N)]
for i in range(N-1):
    d[i+1,i]=0
    adj[i+1].append(i)
    adj[i].append(i+1)
for i in range(M):
    C=LRC[i,2]
    d[LRC[i,0],LRC[i,1]]=C
    d[LRC[i,1],LRC[i,0]]=C
    adj[LRC[i,0]].append(LRC[i,1])
    adj[LRC[i,1]].append(LRC[i,0])

ans=daik(0,N-1,d,adj)
if ans==INF:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import numpy as np
import heapq

INF=10**15
N,M=map(int,input().split())
adj=[[] for i in range(N)]
for i in range(M):
    L,R,C=map(int,input().split())
    L-=1
    R-=1
    adj[L].append((R,C))
    adj[R].append((L,C))
for i in range(N-1):
    adj[i+1].append((i,0))
    
s=0
g=N-1
heap=[]
table=np.array([INF for i in range(N)])
table[s]=0
heapq.heappush(heap,(table[s],s))
                
while heap:
    q=heapq.heappop(heap)
    a=q[1]
    if q[0]>table[a]: continue
    for ne in adj[a]:
        p=ne[0]
        co=ne[1]
        if table[p]>table[a]+co:
            table[p]=table[a]+co
            heapq.heappush(heap,(table[p],p))
ans=table[g]
if ans==INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
w = [[] for i in range(M)]
for i in range(N):
    a, b = map(int, input().split())
    try:
        w[a-1].append(b)
    except:
        pass
for x in w:
    x.sort()
ans = 0
for i in range(M):
    if i>=1:
        w[i] += w[i-1][:-1]
        w[i].sort()
    try:
        ans += w[i][-1]
    except:
        pass
print(ans)

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
w = [[] for i in range(M)]
for i in range(N):
    a, b = map(int, input().split())
    try:
        w[a-1].append(-b)
    except:
        pass
ans = 0
a = []
heapq.heapify(a)
for i in range(M):
    for x in w[i]:
        heapq.heappush(a, x)
    try:
        ans += -heapq.heappop(a)
    except:
        pass
print(ans)
### BUGGY CODE ###

import math
A, B = map(int, input().split())

def gcd(a, b):
	if b == 0: return(a)
	else : return gcd(b, a % b)
		
G = gcd(A, B)
ctr = 1
for i in range(2, G + 1):
    if G == 1: 
        break
    if G % i == 0: 
        ctr += 1
    while G % i == 0:
        G /= i
        
        
print(ctr)

### FIXED CODE ###

import math
A, B = map(int, input().split())

def gcd(a, b):
	if b == 0: return(a)
	else : return gcd(b, a % b)
		
G = gcd(A, B)
ctr = 1
for i in range(2, int(math.sqrt(G)) + 1):
    if G == 1: 
        break
    if G % i == 0: 
        ctr += 1
    while G % i == 0:
        G /= i
        
if G == 1:        
    print(ctr)
else:
    print(ctr + 1)
### BUGGY CODE ###

import sys

def input():
    return sys.stdin.readline().rstrip()

if __name__ == "__main__":
    n = int(input())
    sl = [''.join(sorted(input())) for i in range(n)]

    count = 0
    for i in range(n):
        for j in range(i+1, n):
            if sl[i] == sl[j]:
                count += 1

    print(count)


### FIXED CODE ###

import sys
import collections

def input():
    return sys.stdin.readline().rstrip()

if __name__ == "__main__":
    n = int(input())
    sl = [''.join(sorted(input())) for i in range(n)]
    c = collections.Counter(sl)

    dict = collections.defaultdict(int)
    for v in c.values():
        if v == 1:
            continue

        dict[v] += 1

    ans = 0
    for k, v in dict.items():
        ans += sum([i for i in range(k)]) * v

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

N , K = map(int,input().split())
D = list(map(int,input().split()))

maxValue = 0
actList = [0]*K

for i in range(4**K):
    act = i
    valList = []
    V = D.copy()

    for j in range(K):
        actList[j] = (act % 4)
        act = int(act / 4)

    for j in actList:
        if(j == 0): # 操作 A
            if(len(V) == 0):
                continue
            valList.append(V.pop(0))
        elif(j == 1): # B
            if(len(V) == 0):
                continue
            valList.append(V.pop())
        elif(j == 2): # C
            if(len(valList) == 0):
                continue
            V.insert(0,valList.pop(0))
        elif(j == 3): # D
            if(len(valList) == 0):
                continue
            V.append(valList.pop(0))
        valList.sort()

    val = sum(valList)
    if maxValue < val:
        maxValue = val

print(maxValue)



### FIXED CODE ###

N , K = map(int,input().split())
D = list(map(int,input().split()))

maxValue = 0

for i in range(min(N,K)+1):
    for j in range(min(N,K)-i+1):
        left = D[:i]
        right = D[N-j:]
        merge = (left + right + [0])
        merge.sort()

        index = 0

        for k in range(K-i-j):
            if (merge[index] < 0):
                index += 1
            else:
                break

        val = sum(merge[index:])
        if(maxValue < val):
            maxValue = val

print(maxValue)
### BUGGY CODE ###

K=int(input())
import math
t=0
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      a=math.gcd(i,j)
      b=math.gcd(a,k)
      t+=b
print(t)

### FIXED CODE ###

K=int(input())
import math

if K==1:
  print(1)
  exit()
elif K==2:
  print(9)
  exit()
else:
  t=0
  for i in range(1,K-1):
    for j in range(i+1,K):
      for k in range(j+1,K+1):
        a=math.gcd(i,j)
        b=math.gcd(a,k)
        t+=b
  tw=0
  for i in range(1,K):
    for j in range(i+1,K+1):
      c=math.gcd(i,j)
      tw+=c
  
  on=0
  for i in range(1,K+1):
    on+=i
  print(t*6+tw*6+on)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
    n = int(input())

    a = list()
    for i in range(n):
        a.append(int(input()))

    a_max = max(a)

    for i in range(n):
        if a[i] != a_max:
            print(a_max)
            continue

        tmp = a.copy()
        tmp.remove(a[i])
        print(max(tmp))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
    n = int(input())

    a = [None] * n
    for i in range(n):
        a[i] = int(input())

    a_sorted = sorted(a, reverse=True)
    a_max = max(a)

    for i in a:
        if i != a_max:
            print(a_max)
            continue

        index = a_sorted.index(i)
        if index == 0:
            print(a_sorted[index + 1])


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

S = input()
Q = int(input())
reverse_flag = False

def add_s(s, f, c):
  if f == '1':
    # 先頭
    s = ''.join((c, s))
  else:
    # 末尾
    s = ''.join((s, c))
  return s

for _ in range(Q):
  q = input()
  if q == '1':
    reverse_flag = not reverse_flag
    continue
  _, f, c = q.split()
  #print(reverse_flag, f, c)
  if reverse_flag:
    S = add_s(S, '1' if f == '2' else '2', c)
  else:
    S = add_s(S, f, c)
  #print('---', S)

if reverse_flag:
  S = S[::-1]
print(S)
    

### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())
reverse_flag = False
sento = deque([])
matubi = deque([])

def add_s(f, c):
  if f == '1':
    # 先頭
    sento.appendleft(c)
  else:
    # 末尾
    matubi.append(c)

for _ in range(Q):
  q = input()
  if q == '1':
    reverse_flag = not reverse_flag
    continue
  _, f, c = q.split()
  #print(reverse_flag, f, c)
  if reverse_flag:
    add_s('1' if f == '2' else '2', c)
  else:
    add_s(f, c)
  #print('---', S)

_s = ''.join(sento)
_m = ''.join(matubi)
ans = ''.join([_s, S, _m])
if reverse_flag:
  ans = ans[::-1]
print(ans)
### BUGGY CODE ###

# coding: utf-8
import sys
sysread = sys.stdin.readline
from collections import defaultdict
sys.setrecursionlimit(10**7)
def run():

    N,M,K = map(int,sysread().split())
    to = [[] for _ in range(N+1)]
    n_to = [0 for _ in range(N + 1)]
    for i in range(1,M+1):
        a,b = map(int, sysread().split())
        #a,b = AB[i]
        to[a].append(b)
        n_to[a] += 1
        to[b].append(a)
        n_to[b] += 1

    stack = defaultdict(lambda:0)
    visited = [False] * (N+1)
    belong = [None] * (N+1)


    def dfs(n):
        _stack = [n]
        visited[n] = True
        while _stack:
            node = _stack.pop()
            stack[n] += 1
            belong[node] = n
            for next in to[node]:
                if not visited[next]:
                    _stack.append(next)
                    visited[next] = True
        return None


    for i in range(1,N+1):
        if not visited[i]:
            dfs(i)

    block = [0 for _ in range(N+1)]
    for i in range(1, K+1):
        c,d = map(int, sysread().split())
        #c, d = CD[i]
        if belong[c] == belong[d]:
            block[c] += 1
            block[d] += 1

    candidates = [0] * (N+1)

    for tree in stack.keys():
        for k in range(1,N+1):
            tr = belong[k]
            candidates[k] = stack[tr] - 1 - n_to[k] - block[k]

    print(' '.join(map(str, candidates[1:])))

if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
sysread = sys.stdin.readline
from collections import defaultdict
sys.setrecursionlimit(10**7)
def run():

    N,M,K = map(int,sysread().split())
    to = [[] for _ in range(N+1)]
    n_to = [0 for _ in range(N + 1)]
    for i in range(1,M+1):
        a,b = map(int, sysread().split())
        #a,b = AB[i]
        to[a].append(b)
        n_to[a] += 1
        to[b].append(a)
        n_to[b] += 1

    stack = defaultdict(lambda:0)
    visited = [False] * (N+1)
    belong = [None] * (N+1)


    def dfs(n):
        _stack = [n]
        visited[n] = True
        while _stack:
            node = _stack.pop()
            stack[n] += 1
            belong[node] = n
            for next in to[node]:
                if not visited[next]:
                    _stack.append(next)
                    visited[next] = True
        return None


    for i in range(1,N+1):
        if not visited[i]:
            dfs(i)

    block = [0 for _ in range(N+1)]
    for i in range(1, K+1):
        c,d = map(int, sysread().split())
        #c, d = CD[i]
        if belong[c] == belong[d]:
            block[c] += 1
            block[d] += 1

    candidates = [0] * (N+1)

    for k in range(1,N+1):
        tr = belong[k]
        candidates[k] = stack[tr] - 1 - n_to[k] - block[k]

    print(' '.join(map(str, candidates[1:])))

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

"""
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
"""

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

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

# min
min_ = 0
for n in range(N-K+1):
    min_ += A[n]*cmb(N-1-n, K-1)

# max
max_ = 0
for n in reversed( range(K-1, N) ):
    max_ += A[n]*cmb(n, K-1)

mod = 10**9+7
print( (max_-min_)%mod )


### FIXED CODE ###

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

mod = 10**9+7 #出力の制限
N_ = 10**5+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N_ + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

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

# min
min_ = 0
for n in range(N-K+1):
    min_ += A[n]*cmb(N-1-n, K-1, mod)

# max
max_ = 0
for n in reversed( range(K-1, N) ):
    max_ += A[n]*cmb(n, K-1, mod)

#mod = 10**9+7
print( (max_-min_)%mod )
### BUGGY CODE ###

a,b=map(int,input().split())
c=1
for i in range(a,b+1):
    c*=i

if c>0:
    print('Positive')
elif c==0:
    print('Zero')
else:
    print('Negative')


### FIXED CODE ###

a,b=map(int,input().split())
if a<=0<=b:
    print('Zero')
elif a<0 and b<0:
    n=abs(a-b)+1
    if n%2==0:
        print('Positive')
    else:
        print('Negative')
else:
    print('Positive')
### BUGGY CODE ###

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

A.sort(reverse=True)
cnt = 0
for _ in range(N):
    cnt += A[1]
    del A[0:2]
    del A[-1]
    
print(cnt)

### FIXED CODE ###

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

A.sort(reverse=True)
i = 1
n = 1
cnt = 0
while 2*i <= 2*N:
    cnt += A[n]
    i += 1
    n += 2
    
print(cnt)
### BUGGY CODE ###

x, y, z, k = map(int, input().split())

a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

e = []

for va in a:
    for vb in b:
        e.append(va+vb)

e.sort(reverse=True)

e = e[:k]

d = []
for vc in c:
    for ve in e:
        d.append(vc+ve)

d.sort(reverse=True)
d = d[:k]

for vd in d:
    print(vd)

### FIXED CODE ###

import heapq

x, y, z, k = map(int, input().split())

a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

e = []

for va in a:
    for vb in b:
        e.append(va+vb)

e.sort(reverse=True)
e = e[:k]

d = []
for ve in e:
    for vc in c:
        heapq.heappush(d, -(ve+vc))

for i in range(k):
    print(-heapq.heappop(d))
### BUGGY CODE ###

x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

eats = sorted(p, reverse=True)[:x] + sorted(q, reverse=True)[:y]
while r and max(r) >= min(eats):
    eats[eats.index(min(eats))] = max(r)
    r.remove(max(r))

print(sum(eats))

### FIXED CODE ###

x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

eats = sorted(p, reverse=True)[:x] + sorted(q, reverse=True)[:y] + r
eats.sort(reverse=True)
print(sum(eats[:x+y]))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,m,q=map(int,input().split())
num=[[0]*(n+1) for _ in range(n+1)]
for i in range(m):
	l,r=map(int,input().split())
	num[l][r]+=1
for i in range(n):
	for j in range(n):
		num[i+1][j+1]+=num[i+1][j]
for i in range(q):
	p,q=map(int,input().split())
	ans=0
	for i in range(p,q+1):
		ans+=num[i][q]-num[i][p-1]
	print(ans)




### FIXED CODE ###

import sys
input=sys.stdin.readline
n,m,q=map(int,input().split())
num=[[0]*(n+1) for _ in range(n+1)]
for i in range(m):
	l,r=map(int,input().split())
	num[l][r]+=1
for i in range(n):
	for j in range(n):
		num[i+1][j+1]+=num[i+1][j]
for i in range(q):
	p,q=map(int,input().split())
	ans=0
	for i in range(p,q+1):
		ans+=num[i][q]-num[i][p-1]
	print(ans)
### BUGGY CODE ###

S = list(input())
T = list(input())
MAX_LEN = 3007
dp = [[0] * MAX_LEN for _ in range(MAX_LEN)]

for i in range(len(S)):
    for j in range(len(T)):
        ii = i + 1
        jj = j + 1
        if S[i] == T[j]:
            dp[ii][jj] = dp[ii - 1][jj - 1] + 1
        else:

            dp[ii][jj] = max(dp[ii - 1][jj],
                             dp[ii][jj - 1]
                             )

i = len(S)
j = len(T)
from collections import deque

ans = deque(maxlen=dp[i][j])
while i > 0 and j > 0:
    if dp[i][j] == dp[i][j - 1]:
        j -= 1
    elif dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        ans.appendleft(S[i - 1])
        i -= 1
        j -= 1
print(*ans, sep='')


### FIXED CODE ###

s = input()
t = input()

dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
# 最長の文字数を求める
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1], dp[i + 1][j])

# print(dp[-1][-1]) # 最長文字数
i, j = len(s), len(t)

ans = []
while i > 0 and j > 0:
    if s[i - 1] == t[j - 1] and dp[i][j] == dp[i - 1][j - 1] + 1:
        ans.append(s[i - 1])
        i -= 1
        j -= 1
    else:
        if dp[i - 1][j] == dp[i][j]:
            i -= 1
        else:
            j -= 1
print(*reversed(ans), sep='')
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC113 C

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,m = LI()
lst = [[] for _ in range(n)]
py = [LI() for _ in range(m)]
for i in range(m):
    p,y = py[i]
    lst[p-1].append(y)

ans = []
for i in lst:
    i.sort()
for i in range(m):
    p,y = py[i]
    s1 = '00000' + str(p)
    s2 = '00000' + str(lst[p-1].index(y)+1)
    s = s1[-6:] + s2[-6:]
    ans.append(s)
for i in ans:
    print(i)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC113 C

from operator import itemgetter
n,m = map(int,input().split())
py = [list(map(int,input().split())) for _ in range(m)]
for i in range(m):
    py[i].append(i)
py.sort(key = itemgetter(1))
py.sort(key = itemgetter(0))

x = py[0][0]
c = 0
for i in range(m):
    if x != py[i][0]:
        c = 1
        x = py[i][0]
    else:
        c += 1
    py[i].append(c)
py.sort(key = itemgetter(2))
for i in range(m):
    front = '00000'+str(py[i][0])
    back = '00000'+str(py[i][3])
    print(front[-6:]+back[-6:])
### BUGGY CODE ###

r1, c1, r2, c2 = map(int, input().split())
L = 10 ** 9 + 7

# 互除法
def get_euclidian (A, B):
  if B == 1:
    return (1)
  else:
    return (int((1 - A * get_euclidian (B, A % B)) / B))

# 階乗計算
F = [1]
for i in range(1, r2 + c2 + 3):
  F.append(F[i - 1] * i)

# 組み合わせ計算
def get_combi (n, r):

  NmodL = F[n] % L
  RmodL = F[r] % L
  SmodL = F[n-r] % L
  Euc = (get_euclidian(L, RmodL * SmodL) + L) % L
  return ((NmodL * Euc) % L)

combi1 = get_combi(r2 + c2 + 2, r2 + 1)
combi2 = get_combi(r2 + c1 + 1, c1)
combi3 = get_combi(r1 + c2 + 1, r1)
combi4 = get_combi(r1 + c1, r1)

print (int(combi1 - combi2 - combi3 + combi4))

### FIXED CODE ###

r1, c1, r2, c2 = map(int, input().split())
L = 10 ** 9 + 7

# 互除法
def get_euclidian (A, B):
  if B == 1:
    return (1)
  else:
    return (int((1 - A * get_euclidian (B, A % B)) / B))

# 階乗計算
F = [1]
for i in range(1, r2 + c2 + 3):
  F.append((F[i - 1] * i) % L)

# 組み合わせ計算
def get_combi (n, r):

  Euc = get_euclidian(L, (F[r] * F[n - r]) % L)
  return ((F[n] * Euc) % L)

combi1 = get_combi(r2 + c2 + 2, r2 + 1)
combi2 = get_combi(r2 + c1 + 1, c1)
combi3 = get_combi(r1 + c2 + 1, r1)
combi4 = get_combi(r1 + c1, r1)

print ((int(combi1 - combi2 - combi3 + combi4) + L) % L)
### BUGGY CODE ###

A,B,K=map(int,input().split())
for i in range(A,B+1):
  if i<=A+K-1 or i>=B-K+1:print(i)
  else:A+=0

### FIXED CODE ###

a,b,k=map(int, input().split())
r=range(a,b+1)
for i in sorted(set(r[:k])|set(r[-k:])):print(i)
### BUGGY CODE ###

N=int(input())
X=input()
f={}
for i in range(N):
    x=''
    for j in range(N):
        if i == j:
            x+='1'
        else:
            x+='0'
    y=int(X,2) ^ int(x,2)
    if y not in f:
        ans = 0
        while y!=0:
            y = y % bin(y).count('1')
            ans += 1
        print(ans)
        f[y]=ans
    else: print(f[y])

### FIXED CODE ###

N=int(input())
X=input()
popcount=X.count('1')
bi1=[]
bi0=[]
Xnum1 = 0
Xnum0 = 0
if popcount != 1:
    for i in range(N):
        if i==0: bi1.append(1)
        else: bi1.append(bi1[i-1]*2%(popcount-1))
        Xnum1 = (Xnum1 + int(X[N-i-1])*bi1[i])%(popcount-1)
for i in range(N):
    if i==0: bi0.append(1)
    else: bi0.append(bi0[i-1]*2%(popcount+1))
    Xnum0 = (Xnum0 + int(X[N-i-1])*bi0[i])%(popcount+1)
for i in range(N):
    if popcount==1 and X[i]=='1':
        print(0)
        continue
    if X[i]=='1':
        Xi = (Xnum1 - bi1[N-i-1])%(popcount-1)
    else:
        Xi = (Xnum0 + bi0[N-i-1])%(popcount+1)
    ans = 1
    while Xi!=0:
        Xi = Xi % bin(Xi).count('1')
        ans += 1
    print(ans)
### BUGGY CODE ###

lists=[]
setlists=[]
uselists=[]
allsums=0

n=int(input())
for s in range(n):
    something=sorted(str(input()))
    lists.append(something)
    if something not in setlists:
        setlists.append(something)


for i in setlists:
    whatis=lists.count(i)
    uselists.append(whatis)

for x in uselists:
    allsums+=int(x*(x-1)/2)
print(allsums)

### FIXED CODE ###

n=int(input())
dicts={}
nums=0
for x in range(n):
    s=str(input())
    sorting=sorted(s)
    sorting="".join(sorting)
    if sorting not in dicts.keys():
        dicts[sorting]=1
    else:
        dicts[sorting]+=1
for x in  dicts.values():
    nums+=int(x*(x-1)/2)
print(nums)
### BUGGY CODE ###

H, W = [int(i) for i in input().split(" ")]
S = []
for i in range(H):
  S.append(input())

import numpy as np
a = np.zeros([H,W],dtype=int)
b = np.zeros([H,W],dtype=int)
c = np.zeros([H,W],dtype=int)
d = np.zeros([H,W],dtype=int)

for h in range(H):
  for w in range(W):
    if S[h][w]=="#":
      a[h,w]=0
    elif w == 0:
      a[h,w]=1
    else: 
      a[h,w] = a[h,w-1] + 1

for h in range(H):
  for w in range(W):
    w = W-w-1
    if S[h][w]=="#":
      b[h,w]=0
    elif w == W-1:
      b[h,w]=1
    else: 
      b[h,w] = b[h,w+1] + 1
      
for w in range(W):
  for h in range(H):
    if S[h][w]=="#":
      c[h,w]=0
    elif h == 0:
      c[h,w]=1
    else: 
      c[h,w] = c[h-1,w] + 1
      
for w in range(W):
  for h in range(H):
    h = H-h-1
    
    if S[h][w]=="#":
      d[h,w]=0
    elif h == H-1:
      d[h,w]=1
    else: 
      d[h,w] = d[h+1,w] + 1
      
print((a+b+c+d).max()-3)

### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
S = []
for h in range(H):
  S.append(list(map(lambda s:0 if s=='#' else 1, input())))
S = np.array(S)
 
l,r,u,d = [np.zeros([H,W], dtype=int) for _ in range(4)]

for w in range(W):
  l[:,w] = (l[:,w-1]+1)*S[:,w]
  r[:,-w-1] = (r[:,-w]+1)*S[:,-w-1]

for h in range(H):
  u[h] = (u[h-1]+1)*S[h]
  d[-h-1] = (d[-h]+1)*S[-h-1]
  
ans = np.max((l+r+u+d-3)*S)

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

from itertools import accumulate

def mi():
    return map(int, input().split())

def BIT_query(idx, BIT):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

def main():
    N, K = mi()
    A = list(mi())

    for _ in range(K):
        l = [0]*N
        for i in range(N):
            left = max(i-A[i], 0)
            right = min(i+A[i]+1, N)
            l[left] += 1
            if right < N:
                l[right] -= 1
        A = list(accumulate(l))
    print(' '.join(list(map(str, A))))

if __name__ == '__main__':
    main()

### FIXED CODE ###

from itertools import accumulate

def mi():
    return map(int, input().split())

def main():
    N, K = mi()
    A = list(mi())

    for _ in range(K):
        l = [0]*N
        for i in range(N):
            left = max(i-A[i], 0)
            right = min(i+A[i]+1, N)
            l[left] += 1
            if right < N:
                l[right] -= 1
        if A != list(accumulate(l)):
            A = list(accumulate(l))
        else:
            break
    print(' '.join(list(map(str, A))))

if __name__ == '__main__':
    main()