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

N, M, P = map(int, input().split())
E = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    E[i] = (a - 1, b - 1, P - c)
INF = float("inf")
d = [INF for _ in range(N)]
d[0] = 0
for i in range(2*N):
    for f, t, w in E:
        if d[t] > d[f] + w:
            d[t] = d[f] + w
            if i >= N:
                d[t] = -INF
    if i == N-1:
        dN = d[-1]
if dN != d[-1]:
    print(-1)
elif dN > 0:
    print(0)
else:
    print(-dN)


### FIXED CODE ###

N, M, P = map(int, input().split())
E = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    E[i] = (a - 1, b - 1, P - c)
INF = float("inf")
d = [INF for _ in range(N)]
d[0] = 0
for i in range(2*N):
    for f, t, w in E:
        if d[t] > d[f] + w:
            d[t] = d[f] + w
            if i >= N:
                d[t] = -INF
    if i == N-1:
        dN = d[-1]
if dN != d[-1]:
    print(-1)
elif dN > 0:
    print(0)
else:
    print(-dN)
### BUGGY CODE ###

from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

n,k = map(int,stdin.readline().rstrip().split())
a = list(map(int,stdin.readline().rstrip().split()))
a = [0]+a
bunki = 0
now = a[1]
lip = [1]
while True:
    bunki += 1
    if now in lip:
        break
    lip.append(now)
    now = a[now]

tenki = lip.index(now)

lis = lip[tenki:]

roop = bunki-tenki

if k < tenki: 
    print(lip[k])
    exit()
k -= tenki

print(lis[k%roop])

### FIXED CODE ###

from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

n,k = map(int,stdin.readline().rstrip().split())
a = list(map(int,stdin.readline().rstrip().split()))
a = [0]+a
bunki = 0
now = a[1]
lip = [1]
se = set()
while True:
    bunki += 1
    if now in se:
        break
    se.add(now)
    lip.append(now)
    now = a[now]

tenki = lip.index(now)
lis = lip[tenki:]
roop = bunki-tenki

if k < tenki: 
    print(lip[k])
    exit()
k -= tenki

print(lis[k%roop])
### BUGGY CODE ###

n=int(input())
h=list(map(int,input().split()))
max=0
now=0
for i in range(n-1):
    now=0
    for j in range(i+1,n):
        if h[j]<=h[j-1]:
            now+=1
            if j==n-1:
                if now>=max:
                    max=now
                break
        else:
            if now>=max:
                max=now
            break
print(max)

### FIXED CODE ###

def main():
    n = int(input())
    h = input().split()
    h = [int(n) for n in h]
    max = 0
    now = 0
    i = 0
    for i in range(n-1):
        if h[i] >= h[i+1]:
            now += 1
        else:
            if now >= max:
                max = now
            now=0
        if now >= max:
            max = now
    print(max)

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

import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

MOD = 10**9 + 7

n = ri()
ls = ril()
counter = collections.defaultdict(int)
for a in ls:
    i = 0
    while a > 0:
        if a % 2 == 1:
            counter[i] += 1
        a //= 2
        i += 1
res = 0
for k, v in counter.items():
    res += (n - v) * v * 2**k % MOD
    res %= MOD
print(res)

### FIXED CODE ###

import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

MOD = 10**9 + 7

n = ri()
ls = ril()
counter = collections.defaultdict(int)
for a in ls:
    i = 0
    while a > 0:
        if a % 2 == 1:
            counter[i] += 1
        a //= 2
        i += 1
res = 0
for k, v in counter.items():
    res += (n - v) * v * 2**k % MOD
    res %= MOD
print(res)
### BUGGY CODE ###

M=10**9+7
mod =M
import sys
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        c = 0
        while n % i == 0:
            n /= i
            c+=1
        if c!=0:
            table.append((i,c))
        i += 1
    if n > 1:
        table.append((int(n), 1))
    return table

from collections import defaultdict
N=input()
xs = map(int, input().split())
ys = []
d = defaultdict(int)
for x in xs:
    ps = prime_decomposition(x)
    psd = defaultdict(int)
    for p, c in ps:
        psd[p] = c
        d[p] = max(d[p], c)
    ys.append(psd)
r = 0
for ps in ys:
    t = 1
    for p in d:
        t = (t*power(p,d[p]-ps[p])%M)%M
    r = (r+t)%M
print(r)


### FIXED CODE ###

M=10**9+7
mod =M
import sys
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
NNN = (10**6)
inverse = [0, 1]
for i in range( 2, NNN + 1 ):
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        c = 0
        while n % i == 0:
            n /= i
            c+=1
        if c!=0:
            table.append((i,c))
        i += 1
    if n > 1:
        table.append((int(n), 1))
    return table

from collections import defaultdict
N=input()
xs = list(map(int, input().split()))
ys = []
d = defaultdict(int)
for x in xs:
    ps = prime_decomposition(x)
    psd = defaultdict(int)
    for p, c in ps:
        psd[p] = c
        d[p] = max(d[p], c)
    ys.append(psd)
g=1
for p in d:
    g=mul(g,p**(d[p])%M)%M
r=0
for x in xs:
    r = (r+mul(g,inverse[x]))%M
print(r%M)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from fractions import Fraction
import sys

N = int(input())

dict_F = {}
count_0 = 0

def insert(A,B,s): # A>=0, B>0, s=0or1
  if Fraction(A,B) not in dict_F.keys():
    dict_F[Fraction(A,B)] = [0,0]
  dict_F[Fraction(A,B)][s] += 1

def make_power2(N):
  result = 1
  list_result = [1]
  for _ in range(N):
    result = (2*result)%mod
    list_result.append(result)
  return list_result

for _ in range(N):
  A,B = map(int, sys.stdin.readline().split())
  if A==0 and B==0:
    count_0 += 1
  elif A>=0 and B>0:
    insert(A,B,0)
  elif A>0 and B<=0:
    insert(-B,A,1)
  elif A<=0 and B<0:
    insert(-A,-B,0)
  elif A<0 and B>=0:
    insert(B,-A,1)

mod = 1000000007
power2 = make_power2(N)
answer = 1

for A,B in dict_F.values():
  answer = (answer*(power2[A]+power2[B]-1))%mod
answer = (answer+count_0-1)%mod

print(answer)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from math import gcd

N, *AB = map(int, sys.stdin.buffer.read().split())

dict_F = {}
count_0 = 0

def insert(A,B,s): # A>=0, B>0, s=0or1
  if (A,B) not in dict_F.keys():
    dict_F[(A,B)] = [0,0]
  dict_F[(A,B)][s] += 1

def make_power2(N):
  result = 1
  list_result = [1]
  for _ in range(N):
    result = (2*result)%mod
    list_result.append(result)
  return list_result

for i in range(N):
  A,B = AB[2*i], AB[2*i+1]
  if A==0 and B==0:
    count_0 += 1
    continue
  g = gcd(A,B)
  A //= g
  B //= g
  if A>=0 and B>0:
    insert(A,B,0)
  elif A>0 and B<=0:
    insert(-B,A,1)
  elif A<=0 and B<0:
    insert(-A,-B,0)
  elif A<0 and B>=0:
    insert(B,-A,1)

mod = 1000000007
power2 = make_power2(N)
answer = 1

for A,B in dict_F.values():
  answer = (answer*(power2[A]+power2[B]-1))%mod
answer = (answer+count_0-1)%mod

print(answer)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,k = LI()
    a = LI()
    r = [0] * n
    for i in range(1,n):
        ai = a[i]
        t = r[i-1] + abs(a[i-1]-ai)
        j = i - 2
        mj = i - k
        if mj < 0:
            mj = 0
        while j >= mj:
            u = r[j] + abs(a[j]-a[i])
            if t > u:
                t = u
            j -= 1

        r[i] = t

    return r[-1]


print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,k = LI()
    a = LI()
    r = [0] * n
    for i in range(1,n):
        ai = a[i]
        t = r[i-1] + abs(a[i-1]-ai)
        mj = i - k
        if mj < 0:
            mj = 0
        for j in range(mj,i-1):
            u = r[j] + abs(a[j]-ai)
            if t > u:
                t = u

        r[i] = t

    return r[-1]


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

N , M = map(int,input().split())

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

A.sort()

conv = []

for i in range(M) :
    B , C = map(int,input().split())
    conv.append([B,C])

sec = lambda A : A[1]
conv.sort(key=sec,reverse=True)

change = 0

for c in conv :
    if c[1] < A[0] : # 変換後のほうが小さい
        break

    for k in range(c[0]) :
        if A[k] >= c[1] :
            break

        A[k] = c[1]
        change += 1

    if change >= N :
        break

    A.sort()



print(int(sum(A)))

### FIXED CODE ###

N , M = map(int,input().split())

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

A.sort()

conv = []

for i in range(M) :
    B , C = map(int,input().split())
    conv.append([B,C])

sec = lambda A : A[1]
conv.sort(key=sec,reverse=True)

change = []
add = 0

# 大きいものからN個とる
for c in conv :
    for i in range(c[0]) :
        change.append(c[1])
        add += 1

    if(add >= N) :
        break

for i in range(min(N,len(change))) :
    if A[i] >= change[i] :
        break
    A[i] = change[i]

print(int(sum(A)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
l = [] 
r = []
count = 0

N, M = map(int, input().split())
l = [0] * M
r = [0] * M
for i in range(0,M):
    l[i], r[i] = map(int, input().split())

#idカードの生成
    
for i in range(1,N+1):
    if max(l) <= i and i <= min(r):
        count += 1

print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
l = [] 
r = []
count = 0

N, M = map(int, input().split())
l = [0] * M
r = [0] * M
for i in range(0,M):
    l[i], r[i] = map(int, input().split())

#idカードの生成
    
ml = max(l)
mr = min(r)

for i in range(1,N+1):
    if  ml <= i and i <= mr:
        count += 1

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

n,m,k=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
a,b=[0],[0]
for i in range(n):
  a.append(a[i]+A[i])
for i in range(m):
  b.append(b[i]+B[i])
ans=0
book=0
for i in range(n+1):
  for j in range(m+1):
    if a[i]+b[j]<=k:
      book=i+j
      if book>ans:
        ans = book
    else:
      break
print(ans)

### FIXED CODE ###

n,m,k=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
a,b=[0],[0]
for i in range(n):
  a.append(a[i]+A[i])
for i in range(m):
  b.append(b[i]+B[i])
ans=0
for i in range(n+1):
  if a[i]>k:
    break
  for j in range(m,-1,-1):
    if a[i]+b[j]<=k:
      ans=max(ans,i+j)
      m=j
      break
print(ans)
### BUGGY CODE ###

A, W = map(int,input().split())
B, V = map(int,input().split())
T = int(input())
flag = "NO"
mid = T//2
i = 1
while True:
    i += 1
    a = A + W*mid
    b = B + V*mid
 
    if a == b:
        flag = "YES"
        break
    elif a > b and a + W < b + V:
        break
    elif a < b and a - W > b - V:
        break
    elif T//(2**i) == 0:
        if a > b:
            mid = mid - 1
            if mid < 1:
                mid = 1
        elif a < b:
            mid = mid + 1
            if mid > T:
                mid = T
    elif a > b:
        mid = mid - T//(2**i)
    elif a < b:
        mid = mid + T//(2**i)

print(flag)

### FIXED CODE ###

A, W = map(int,input().split())
B, V = map(int,input().split())
T = int(input())

a = A + W*T
b = B + V*T
c = A - W*T
d = B - V*T


if A < B:
    if a >= b:
        print("YES")
    else:
        print("NO")
else:
    if c <= d:
        print("YES")
    else:
        print("NO")
### BUGGY CODE ###

N, Q = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N - 1)]
PX = [list(map(int, input().split())) for _ in range(Q)]

graph = [[] for _ in range(N + 1)]
for A, B in AB:
  graph[A].append(B)
  graph[B].append(A)
#print("graph:", graph)
  
X = [0] * (N + 1)
for p, x in PX:
  X[p] += x
#print("X:", X)

stack = [1]
check = [0] * (N + 1)
check[1] = 1
cnt = [0] * (N + 1)
cnt[1] = X[1]

while stack:
  s = stack.pop()
  for g in graph[s]:
    if check[g] == 0:
      check[g] = 1
      cnt[g] = cnt[s] + X[g]
      stack.append(g)
print(*cnt[1::])

### FIXED CODE ###

import collections

N,Q=map(int,input().split())
M=[[] for i in range(N+1)]
P=[0 for i in range(N+1)]
for i in range(N-1):
  a,b=map(int,input().split())
  M[a].append(b)
  M[b].append(a)
#print("M:",M)

S=[0 for i in range(N+1)]
for i in range(Q):
  p,x=map(int,input().split())
  S[p]+=x
#print(S)
  
d=collections.deque([1])

while len(d):
  dd=d.popleft()
  if P[dd]==0:
    P[dd]=1
    for i in M[dd]:
      if P[i]==0:
        S[i]+=S[dd]
      d.append(i)
  #print(d,S)
print(*S[1:])
### BUGGY CODE ###

n = int(input())
d = list(map(int, input().split()))
d.sort()
k_count = 0
for i in range(len(d)):
    arc = len(list(filter(lambda x: x > d[i], d)))
    abc = len(list(filter(lambda x: x <= d[i], d)))
    if arc == abc:
        k_count += (d[i+1] - d[i])
print(k_count)

### FIXED CODE ###

n = int(input())
d = list(map(int, input().split()))
d.sort()
k_count = 0
i = n // 2 - 1
arc = len(list(filter(lambda x: x > d[i], d)))
abc = len(list(filter(lambda x: x <= d[i], d)))
if arc == abc:
    k_count += (d[i+1] - d[i])
print(k_count)
### BUGGY CODE ###

n, m = map(int, input().split())
*A, = map(int, input().split())
A.sort()

# Aの累積和を求めておく
S = [0]
x = 0
for a in A:
    x += a
    S.append(x)


def lower(x):
    # A[i]<xなるiの個数
    left = -1
    right = n
    while right-left > 1:
        mid = (left+right)//2
        if A[mid] < x:
            left = mid
        else:
            right = mid
    return right


def lower_pair(x):
    # A[i]+A[j]<xなる(i,j)の個数
    cnt = 0
    for a in A:
        cnt += lower(x-a)
    return cnt


# A[i]+A[j]のm番目に大きい値を求める
# lower_pair(x)<n**2-mなる最大のxを求めればよい
left = 2*min(A)
right = 2*max(A)
while right-left > 1:
    mid = (left+right)//2
    if lower_pair(mid) < n**2-m:
        left = mid
    else:
        right = mid
x = left

# A[i]+A[j]>=xとなる(i,j)の個数とA[i]+A[j]の総和を求める
k = n**2-lower_pair(x)
s = 0
for a in A:
    cnt = lower(x-a)
    s += (n-cnt)*a+S[n]-S[cnt]

print(s-(k-m)*x)


### FIXED CODE ###

n, m = map(int, input().split())
*A, = map(int, input().split())
A.sort()

# Aの累積和を求めておく
S = [0]
x = 0
for a in A:
    x += a
    S.append(x)


def lower(x):
    # A[i]<xなるiの個数
    left = -1
    right = n
    while right-left > 1:
        mid = (left+right)//2
        if A[mid] < x:
            left = mid
        else:
            right = mid
    return right


def lower_pair(x):
    # A[i]+A[j]<xなる(i,j)の個数
    cnt = 0
    for a in A:
        cnt += lower(x-a)
    return cnt


# A[i]+A[j]のm番目に大きい値を求める
# lower_pair(x)<n**2-mなる最大のxを求めればよい
left = 2*min(A)
right = 2*max(A)
while right-left > 1:
    mid = (left+right)//2
    if lower_pair(mid) < n**2-m:
        left = mid
    else:
        right = mid
x = left

# A[i]+A[j]>=xとなる(i,j)の個数とA[i]+A[j]の総和を求める
k = n**2-lower_pair(x)
s = 0
for a in A:
    cnt = lower(x-a)
    s += (n-cnt)*a+S[n]-S[cnt]

print(s-(k-m)*x)
### BUGGY CODE ###

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

dp = [0] * (S + 1)
ans = 0
for a in A:
    dp[0] += 1
    for s in range(S + 1)[::-1]:
        if a + s <= S:
            dp[a + s] = (dp[a + s] + dp[s]) % MOD
    ans += dp[S]

print(ans % MOD)


### FIXED CODE ###

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

dp = [0] * (S + 1)
ans = 0

for i, a in enumerate(A):
    for s in range(S + 1)[:: -1]:
        if s + a <= S:
            dp[s + a] += dp[s]
    if a <= S:
        dp[a] += (i + 1)
    ans += dp[S]

print(ans % MOD)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

def check(t):
    res = 0
    for ai in a:
        if ai:
            aj = t // ai
            if ai > 0:
                res += bisect_right(a, aj)
            else:
                if t % ai:
                    res += n - bisect_right(a, aj)
                else:
                    res += n - bisect_left(a, aj)
        else:
            if t >= 0:
                res += n
        if ai * ai <= t:
            res -= 1
    return res // 2

l = - 10 ** 18
r = 10 ** 18

while r - l > 1:
    mid = (l + r) // 2
    if check(mid) < k:
        l = mid
    else:
        r = mid

if check(l) == k:
    print(l)
else:
    print(r)

### FIXED CODE ###

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

a.sort()

def check(t):
    j = n - 1 if t > 0 else 0
    res = 0
    f = 1

    cond = lambda x, t, f:x <= t if f * t > 0 or (t == 0 and f == -1) else x > t
    shift = lambda x, t:x-1 if t > 0 else x+1
    count = lambda x, n, f:n-x if f == 1 else x

    for ai in a:
        if f == 1 and ai > 0:
            f = -1
            j = n - 1 if t > 0 else 0
        if ai:
            while j >= 0 and j < n and cond(ai * a[j], t, f):
                j = shift(j, t)
            if t > 0:
                res += count(j+1, n, f)
            else:
                res += count(j, n, f)
        else:
            if t >= 0:
                res += n
        if ai * ai <= t:
            res -= 1
    return res // 2
            

m = max(max(a)**2, min(a)**2)
l = -m
r = m

while r - l > 1:
    mid = (l + r) // 2
    if check(mid) < k:
        l = mid
    else:
        r = mid

if check(l) == k:
    print(l)
else:
    print(r)
### BUGGY CODE ###

h, w, d = map(int, input().split())
index = [(0,0) for x in range(h*w+1)]
for i in range(1,h+1):
    col = list(map(int, input().split()))
    for j in range(1,w+1):
        index[col[j-1]] = (i, j)

q = int(input())
for i in range(q):
    ans = 0
    l, r = map(int, input().split())
    while l != r:
        ans += abs(index[l+d][0] - index[l][0]) + abs(index[l+d][1]-index[l][1])
        l += d
    print(ans)



### FIXED CODE ###

h, w, d = map(int, input().split())
index = [(0,0) for x in range(h*w+1)]
for i in range(1,h+1):
    col = list(map(int, input().split()))
    for j in range(1,w+1):
        index[col[j-1]] = (i, j)

memo = [0 for x in range(h*w+1)]
l = 0
for l in range(1, h*w+1-d):
    memo[l+d] = memo[l] + abs(index[l+d][0] - index[l][0]) + abs(index[l+d][1]-index[l][1])

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(memo[r]-memo[l])
### BUGGY CODE ###

import numpy as np
from numba import njit

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

A_list = [0]+list(map(int, input().split()))
A_np=np.array(A_list)
#print(A_np)


def update(A_np):
  new_A_np=np.array([0]*(N+1))
  for i in range(1,N+1):
    tmp_np=np.array([0]*(N+1))
    #print(A_np)
    mi=i-A_np[i]
    ma=i+A_np[i]
    if mi<0:
      mi=0
    if ma>N:
      ma=N
    #print(mi,ma)
    tmp_np[mi:ma+1]=1
    #print(tmp_np)
    new_A_np+=tmp_np
  #print(new_A_np)
  A_np=new_A_np
  return(A_np)

for j in range(K):
  A_np=update(A_np)
  if sum(A_np[1:N+1])==N*N:
    break
    
for i in range(1,N+1):
  print(A_np[i],end=" ")


### FIXED CODE ###

import numpy as np
from numba import njit

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

A_list = np.array([0]+list(map(int, input().split())))

@njit
def update(A_list):

  for j in range(min(K,46)):
    new_A=np.zeros(N+2,dtype=np.int64)
    for i in range(1,N+1):
      #print(new_A)
      mi=i-A_list[i]
      ma=i+A_list[i]
      if mi<0:
        mi=0
      if ma>N:
        ma=N
      #new_A[mi:ma+1]+=1
      new_A[mi]+=1
      new_A[ma+1]-=1

    A_list=np.cumsum(new_A)
    #if sum(A_list[1:N+1])==N*N:
    #  return(A_list)    
    #  break
      
  return(A_list)

A_list=update(A_list)
for i in range(1,N+1):
  print(A_list[i],end=" ")
### BUGGY CODE ###

s=int(input())
d=dict(zip(list(range(2019)),[0]*2019))
i=0
while 10**(i-1)<=s:
  d[s%10**i%2019]+=1
  i+=1
ans=0
for _,i in d.items():
  ans+=i*(i-1)//2
print(ans)

### FIXED CODE ###

s=input()
n=len(s)
d=[0]*2019
d[0]=1
j=1
ans=0
now=0
for i in s[::-1]:
  now=(now+int(i)*j)%2019
  ans+=d[now]
  d[now]+=1
  j*=10
  j%=2019
print(ans)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc137/tasks/abc137_d
import sys
sys.setrecursionlimit(10 ** 6)

import collections

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conditions = {}
for i in range(n):
  inputs = [int(x) for x in input().split()]
  if inputs[0] in conditions.keys():
    conditions[inputs[0]].append(inputs[1])
  else:
    conditions[inputs[0]] = collections.deque([inputs[1]])

for day in conditions.keys():
  conditions[day] = sorted(conditions[day], reverse=True)

ans = 0
candidates = {}
cand_len = 0
for reversed_day in range(1, m + 1):
  if reversed_day in conditions.keys():
    candidates[reversed_day] = conditions[reversed_day]
    cand_len += 1

  if cand_len == 0:
    continue

  maxval, maxkey = 0, 0
  for key, cands in candidates.items():
    if cands[0] > maxval:
      maxval = cands[0]
      maxkey = key
  ans += candidates[maxkey].pop(0)
  if len(candidates[maxkey]) == 0:
    del candidates[maxkey]
    cand_len -= 1
print(ans)

### FIXED CODE ###


import collections
import heapq

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conditions = collections.deque([])
for i in range(n):
  conditions.append([int(x) for x in input().split()])

conditions = sorted(conditions)

cnt, ans = 0, 0
candidates = []
for reversed_day in range(1, m + 1):
  while cnt < len(conditions) and conditions[cnt][0] <= reversed_day:
    heapq.heappush(candidates, -conditions[cnt][1])
    cnt += 1

  if len(candidates) == 0:
    continue
  ans -= heapq.heappop(candidates)

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

a, b , n= input().split() 
a = int(a)
b = int(b)
n = int(n)
if b > n :
    print(a*n//b)
else:
    max = 0
    for i in range(1,n,1):
        r = (a*i // b) - a* (i//b)
        if r > max:
            max = r

    print(max)


### FIXED CODE ###

a, b , n= input().split() 
a = int(a)
b = int(b)
n = int(n)
p = min(b,n)
if p % b ==0:
    print(int(a*(p-1)/b))
else:
    print(int(a*p/b))
### BUGGY CODE ###

import itertools, functools, math


def prime_stream():
    stream = itertools.count(2)
    sieve = lambda x, y: x % y != 0

    while True:
        prime = next(stream)
        stream = filter(functools.partial(sieve, y=prime), stream)
        yield prime


N, P = map(int, input().split())

ans = 1
if P // N != 0:
    for p in prime_stream():
        if p > P:
            break
        e = 0
        while P % p == 0:
            P //= p
            e += 1  # 素数のカウント
        if e // N > 0:
            ans *= p ** (e // N)

print(ans)


### FIXED CODE ###

N, P = map(int, input().split())

if N == 1:
    ans = P
else:
    ans = 1
    p = 2
    while p * p <= P:
        e = 0
        while P % p == 0:
            P //= p
            e += 1  # 素数のカウント
        if e // N > 0:
            ans *= p ** (e // N)
        p += 1

print(ans)