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

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

n, m = map(int, input().split())
data = []
row = []
col = []
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    data.append(1)
    row.append(a)
    col.append(b)
    data.append(1)
    row.append(b)
    col.append(a)
graph = csr_matrix((data, (row, col)), shape=(n, n))
_, p = dijkstra(graph, return_predecessors=True, unweighted=True, indices=0, limit=n)
for item in p[1:]:
    if(item < 0):
        print("No")
        exit()
print("Yes")
for item in p[1:]:
    print(item + 1)


### FIXED CODE ###

from collections import deque

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
prev = [-1] * n
visited = [False] * n
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

def bfs(v):
    q = deque()
    visited[v] = True
    q.append(v)
    while q:
        v = q.popleft()
        for child in edges[v]:
            if not visited[child]:
                visited[child] = True
                prev[child] = v
                q.append(child)

bfs(0)
print("Yes")
for i in range(1, n):
    print(prev[i] + 1)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
M = N//2
if N % 2 == 1 and A.count(0) == 1 and all(A.count(i*2+2)==2 for i in range(M)):
    print((2 ** M) % (10**9+7))
elif N % 2 == 0 and all(A.count(i*2+1)==2 for i in range(M)):
    print((2 ** M) % (10**9+7))
else:
    print(0)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
M = N//2
c = Counter(A)
if N % 2 == 1 and A.count(0) == 1 and all(c[i*2+2] == 2 for i in range(M)):
    print((2 ** M) % (10**9+7))
elif N % 2 == 0 and all(c[i*2+1]==2 for i in range(M)):
    print((2 ** M) % (10**9+7))
else:
    print(0)
### BUGGY CODE ###

from heapq import heappush, heappop
import collections
import math
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
inf = float("inf")


def main():
    N = int(input())
    E = {}
    for i in range(0, N+1):
        E[i] = []
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        E[a].append(b)
        E[b].append(a)

    dp = [[0 for i in range(2)] for j in range(100100)]

    def dfs(c, p):
        dp[c][0], dp[c][1] = 1, 1
        for to in E[c]:
            if to != p:
                dfs(to, c)
                dp[c][0] *= dp[to][0] + dp[to][1]
                dp[c][1] *= dp[to][0]

    dfs(0, -1)

    ans = (dp[0][0] + dp[0][1]) % MOD
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from heapq import heappush, heappop
import collections
import math
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
inf = float("inf")


def main():
    N = int(input())
    E = {}
    for i in range(0, N+1):
        E[i] = []
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        E[a].append(b)
        E[b].append(a)

    dp = [[0 for i in range(2)] for j in range(100100)]

    def dfs(c, p):
        dp[c][0], dp[c][1] = 1, 1
        for to in E[c]:
            if to != p:
                dfs(to, c)
                dp[c][0] *= dp[to][0] + dp[to][1]
                dp[c][1] *= dp[to][0]

    dfs(0, -1)

    ans = (dp[0][0] + dp[0][1]) % MOD
    print(ans)


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

s=input()
w=["dream","dreamer","erase","eraser"]
while True:
    if len(s)==0:
        print("YES")
        exit()
    if len(s)<=4:
        print("NO")
        exit()
    
    if s[0:5]==w[0]:
        if len(s)>=7:
            if s[5:7]=="er": #dremaerかeraserかerase
                if s[7]=="a": #erはeraseかeraserのer
                    s=s[5:]
                else:
                    s=s[7:]
        else:
            s=s[5:]

    elif s[0:5]==w[2]:
        if s[5]=="r": 
            s=s[6:]
        else:
            s=s[5:]
    else:
        print("NO")
        exit()

    if len(s)==0:
        print("YES")
        exit()
    #print(s)

### FIXED CODE ###

s=input()
w=["dream","dreamer","erase","eraser",""]
while True:
    

    if s[0:5]==w[0]:
        if s[5:7]=="er": #dremaerかeraserかerase
            if s[7]=="a": #erはeraseかeraserのer
                s=s[5:]
            else:
                s=s[7:]
        else:
            s=s[5:]

    elif s[0:5]==w[2]:
        if s[5]=="r": 
            s=s[6:]
        else:
            s=s[5:]
    else:
        print("NO")
        exit()

    if len(s)<=7:
        if s in w:
            print("YES")
            exit()
        else:
            print("NO")
            exit()
    
    #print(s)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

H,W = map(int, input().split())

a = set()
i = 0
for h in range(H):
    s = list(input().strip())
    for c in s:
        if c == "#":
            a.add(i)
        i += 1
#print(a)

m = 0
for i in range(H*W):
    ni = H+W-2
    for j in a:
        ni = min(ni, abs(j//W-i//W) + abs(j%W -i%W))
#        print(ni, abs(j-i)//W, abs(j%W -i%W))
    m = max(m, ni)
print(m)


### FIXED CODE ###

import sys
input=sys.stdin.readline
H,W = map(int, input().split())

b = [[True]*(W+2)]
for _ in range(H):
    b.append([True] + [x == '#' for x in input().strip()] + [True])
b.append([True]*(W+2))

check = []
for i in range(1,H+1):
    for j in range(1,W+1):
        if b[i][j]:
            check.append((i,j))
t = 0
while check:
    tmp = []
    for i,j in check:
        if not b[i-1][j]:
            b[i-1][j] = True
            tmp.append((i-1,j))
        if not b[i][j-1]:
            b[i][j-1] = True
            tmp.append((i,j-1))
        if not b[i][j+1]:
            b[i][j+1] = True
            tmp.append((i,j+1))
        if not b[i+1][j]:
            b[i+1][j] = True
            tmp.append((i+1,j))
    check = tmp
    t += 1

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

n = int(input())
l = list(map(int, input().split()))

l.sort()
ans = 0

for i in range(n):
    if i + 1 == n:
        break
    for j in range(i+1, n):
        for k in range(j+1, n):
            if l[i] + l[j] <= l[k]:
                break
            ans += 1
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int, input().split()))

l.sort()
ans_set = set()
ans = 0

for i in range(n):
    if i + 1 == n:
        break
    for j in range(i+1, n):
        ans += max(bisect.bisect_left(l, l[i]+l[j]) - j-1, 0)

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

N = int(input())
import heapq as h
A = list(map(int, input().split()))


# use 0 based index
sum_red, sum_blue = [], []

head = A[:N]
tail = [-x for x in A[-N:]]
h.heapify(head)
h.heapify(tail)
sum_red.append(sum(head))
sum_blue.append(-sum(tail))
for k in range(N, 2*N):
    h.heappushpop(head, A[k])
    sum_red.append(sum(head))
    h.heappushpop(tail, -A[-k-1])
    sum_blue.append(-sum(tail))


# 逆順に突っ込んでるので反転
sum_blue = sum_blue[::-1]

diff = [r-b for r, b in zip(sum_red, sum_blue)]
print(max(diff))


### FIXED CODE ###

N = int(input())
import heapq as h
A = list(map(int, input().split()))


# use 0 based index
sum_red, sum_blue = [], []

head = A[:N]
tail = [-x for x in A[-N:]]
h.heapify(head)
h.heapify(tail)
sum_red.append(sum(head))
sum_blue.append(-sum(tail))
# keypoint: いちいちsumすると線形時間かかるのでsum_hoge[-1]でアクセスする
for k in range(N, 2*N):
    num_sub = h.heappushpop(head, A[k])
    sum_red.append(sum_red[-1]-num_sub+A[k])
    num_sub = -h.heappushpop(tail, -A[-k-1])
    sum_blue.append(sum_blue[-1]-num_sub+A[-k-1])


print(max([r-b for r, b in zip(sum_red, sum_blue[::-1])]))
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
sums = []
for i in range(N - K + 1):
  sums.append(sum(P[i:i + K]))
print((max(sums) + K) / 2)


### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
E = list(map(lambda x: (int(x) + 1) / 2, input().split()))

res = np.cumsum(E)

ans = res[K - 1]
for i in range(K, N):
    if ans < res[i] - res[i - K]:
        ans = res[i] - res[i - K]
print(ans)
### BUGGY CODE ###

import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
INF = 1000000000000

n = I()
a = LI()

a.sort()
f = [False]*n

if(n > 1):
    for i in range(1,n):
        if(a[i-1] == a[i]):
            f[i-1] = True
        for j in range(0,i):
            if(a[i] % a[j] == 0):
                f[i] = True
                break

count = 0
for i in range(n):
    if(not f[i]):
        count += 1

print(count)

### FIXED CODE ###

import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
INF = 1000000000000

n = I()
a = LI()

a.sort()
m = a[n-1]
flg = [False]*(m+1)

count = 0
for x in range(n):
    v = a[x]
    if(not flg[v]):
        i = v
        while(i <= m):
            flg[i] = True
            i += v
        if(x == n-1 or v != a[x+1]):
            count += 1

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

import sys

n = int(input())
nums = list(map(int,input().split()))

number = 1
count = 0

if 1 not in nums:
    print(-1)
    sys.exit()

while len(nums) > 0:
    try:
        idx = nums.index(number)
    except ValueError:
        count += len(nums)
        break
    count += idx
    nums = nums[idx+1:]
    number += 1

print(count)


### FIXED CODE ###

import sys

n = int(input())
nums = list(map(int,input().split()))

number = 1
count = 0

if 1 not in nums:
    print(-1)
    sys.exit()

for num in nums:
    if num == number:
        number += 1
    else:
        count += 1
print(count)
### BUGGY CODE ###

def solve_145e():
    from collections import namedtuple
    from operator import attrgetter
    import sys
    input = sys.stdin.readline

    Food = namedtuple('Food', 'time_to_eat deliciousness')

    N, T = map(int, input().split())
    foods = []
    for _ in range(N):
        row = map(int, input().split())
        foods.append(Food(*row))
    foods.sort(key=attrgetter('time_to_eat'))
    # 同じ料理の組を食べるなら時間のかかるものを後回しにしても結果は悪くならない

    dp = [-1] * T
    dp[0] = 0
    # dp[time]:=timeに食べ終わる注文の仕方で得られる最大満足度

    ma = 0  # 回答候補
    ca = 0  # フィニッシュ前候補
    for food in foods:
        # これでフィニッシュの場合
        ma = max(ma, ca + food.deliciousness)

        # まだ食べる場合
        for time in reversed(range(T - food.time_to_eat)):
            if ~dp[time]:
                when_eat = dp[time] + food.deliciousness
                if dp[time + food.time_to_eat] < when_eat:
                    dp[time + food.time_to_eat] = when_eat
                    ca = max(ca, when_eat)

    print(ma)
    return


if __name__ == '__main__':
    solve_145e()


### FIXED CODE ###

def solve():
    from collections import namedtuple
    import sys

    input = sys.stdin.readline
    Dish = namedtuple('Dish', 'idx cost pt')

    n, t = map(int, input().split())
    dishes = []
    for idx in range(1, n + 1):
        cost, pt = map(int, input().split())
        dishes.append(Dish(idx=idx, cost=cost, pt=pt))

    dp_ht = [[0] * t for _ in range(n + 2)]  # head->tail
    dp_th = [[0] * t for _ in range(n + 2)]  # tail->head
    # dp[注文可能な範囲の端][完食にかかる総時間]:= 美味しさの最大値

    for dish in dishes:
        for cost_ in range(t):
            if cost_ >= dish.cost:
                dp_ht[dish.idx][cost_] = max(dp_ht[dish.idx - 1][cost_],
                                             dp_ht[dish.idx - 1][cost_ - dish.cost] + dish.pt)
            else:
                dp_ht[dish.idx][cost_] = dp_ht[dish.idx - 1][cost_]

    for dish in reversed(dishes):
        for cost_ in range(t):
            if cost_ >= dish.cost:
                dp_th[dish.idx][cost_] = max(dp_th[dish.idx + 1][cost_],
                                             dp_th[dish.idx + 1][cost_ - dish.cost] + dish.pt)
            else:
                dp_th[dish.idx][cost_] = dp_th[dish.idx + 1][cost_]

    ret = 0
    for last_dish in dishes:
        for cost_ in range(t):
            ret = max(ret, dp_ht[last_dish.idx - 1][cost_] + dp_th[last_dish.idx + 1][t - 1 - cost_] + last_dish.pt)
    return ret


print(solve())
### BUGGY CODE ###

import sys
from collections import deque

n = int(input())
x = eval('0b' + input())

memo = {0: 0}

# def slove(x):
#     cnt = 0
#     tmp = []
#     while x:
#         if x in memo:
#             return cnt + memo[x]
#         else:

#         x = x % popcount(x)
#         cnt += 1
#     return cnt

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []

for i in range(n):
    y = 0
    if x & (1 << i):
        y = x & ~(1 << i)
    else:
        y= x | (1 << i)
    ans.append(solve(y))

for ansi in reversed(ans):
    print(ansi)


    

        


### FIXED CODE ###

from collections import deque

n = int(input())
x = input()

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []
px = x.count("1")

memo1 = [1 % (px - 1)] if px > 1 else []
memo2 = [1 % (px + 1)]
x1 = 0
x2 = 0

for i in range(n):
    if px > 1:
        memo1.append(memo1[-1] * 2 % (px-1))
    memo2.append(memo2[-1] * 2 % (px+1))

for i in range(n):
    if x[-i-1] == '1':
        if px > 1:
            x1 += memo1[i]
            x1 %= (px-1)
        x2 += memo2[i]
        x1 %= (px+1)

for i in range(n):
    if x[-i-1] == "1":
        if px > 1:
            ans.append(solve((x1-memo1[i])%(px-1)) + 1)
        else:
            ans.append(0)
    else:
        ans.append(solve((x2+memo2[i])%(px+1)) + 1)


for ansi in reversed(ans):
    print(ansi)
### BUGGY CODE ###

n, m = map(int, input().split())
way = [[] for i in range(n + 1)]
ans = [-1 for i in range(n + 1)]
reached = [0 for i in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    way[a].append(b)
    way[b].append(a)
queue = [1]
while len(queue) > 0:
    go = queue.pop(0)
    reached[go] = 1
    for i in range(len(way[go])):
        if (reached[way[go][i]] == 0) and (way[go][i] not in queue):
            queue.append(way[go][i])
            ans[way[go][i]] = go
print('Yes')
for i in range(2, n + 1):
    print(ans[i])

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
way = [[] for i in range(n + 1)]
ans = [-1 for i in range(n + 1)]
reached = [0 for i in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    way[a].append(b)
    way[b].append(a)
D = deque([1])
while D:
    go = D.popleft()
    for i in way[go]:
        if reached[i] == 0:
            D.append(i)
            reached[i] = 1
            ans[i] = go
print('Yes')
for i in range(2, n + 1):
    print(ans[i])
### BUGGY CODE ###

# coding: utf-8
# Your code here!
kai = int(input())
a = 0
b = 0
cou = 0
kaz = []

for i in range(kai):
    a,b = map(int,input().split(" "))
    kaz.append(a)
    kaz.append(b)

for j in range(kai):
    while True:
        if kaz[(kai-j)*2 -2] % kaz [(kai-j)*2 -1] == 0:
            break
        else:
            cou += 1
            for k in range(kai):
                kaz[k*2] += 1
    
print(cou)

### FIXED CODE ###

n = int(input())
p = []
for i in range(n):
    a , b = map(int,input().split())
    p.append([a,b])
ans = 0
for i in reversed(range(n)):
    if (p[i][0] + ans) % p[i][1] != 0:
        ans += p[i][1] - ((p[i][0] + ans)%p[i][1])
print(ans)
### BUGGY CODE ###

from bisect import bisect_right

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

ans = 0
for x in A:
    y_low = bisect_right(B, x)
    for y in B[y_low:]:
        z_low = bisect_right(C, y)
        ans += N - z_low
print(ans)


### FIXED CODE ###

from bisect import bisect_left
from bisect import bisect_right


N = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))

ans = 0
y_low = {}
i = 0
for y in B:
    x = bisect_left(A, y)
    z = bisect_right(C, y)
    ans += x * (N-z)
print(ans)
### BUGGY CODE ###

      
def binary_search(A,n):
    # sequence A, item n
    l=len(A)
    if l==0:
        return False
    elif A[l/2] > n:
        return binary_search(A[:l/2],n)
    elif A[l/2] == n:
        return True
    elif A[l/2]<n:
        return binary_search(A[(l/2)+1:],n)

n = int(raw_input())
S = sorted(list(set(map(int,raw_input().split()))))
q = int(raw_input())
T = map(int,raw_input().split())

C = 0
for k in range(len(T)):
    if binary_search(S,T[k]):
        C += 1
print C

### FIXED CODE ###

# coding: utf-8
# Here your code !
n = int(raw_input())
S = map(int,raw_input().split())
q = int(raw_input())
T = map(int,raw_input().split())
C = 0

def binary_search(A,n):
    """no recursion version"""
    l = len(A)
    left = l/2
    right = l-1
    while A[left] != n:
        if left == right and A[left] != n:
            #print left,right,"if"
            return False
        elif A[left] > n: # n????????????????????´???
            right = left
            left = left/2
            #print left,right,"elif1"
        elif A[left] < n: # n????????????????????´???
            right = right
            left = (left + right-1)/2 + 1
            #print left,right,"elif2"
    else:
        return True

for item in T:
    if binary_search(S,item):
        C += 1
print C
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def inpl():
    return list(map(int, input().split()))


def GetBase(t=0):
    ret = []
    last = -C * 2 - 1
    for i, s in enumerate(S[t:]):
        if s == 'x':
            continue
        elif last + C >= i + t:
            continue

        ret.append(i + t)
        last = i + t
    return ret


def GetDepend(base_ans):
    ruiseki = []
    a = 0
    for s in S:
        if s == 'o':
            a += 1
            ruiseki.append(a)
        else:
            ruiseki.append(a)

    ret = {a: False for a in base_ans}
    for a in ret:
        if ruiseki[a] == ruiseki[min(N - 1, a + C)]:
            ret[a] = True
    return ret


def solve():
    base_ans = GetBase()
    if len(base_ans) > K:
        return []

    depend_dict = GetDepend(base_ans)
    for i, b in enumerate(base_ans):
        if depend_dict[b] is True:
            continue
        S[b] = 'x'
        tmp = GetBase(b)
        if len(tmp) + i < K:
            depend_dict[b] = True
        else:
            for s in set(tmp) - set(base_ans[i:]):
                depend_dict[s] = True

        S[b] = 'o'

    return [a + 1 for a in base_ans if depend_dict[a] is True]


N, K, C = inpl()
S = list(input().strip())

ans = solve()

for a in ans:
    print(a)


### FIXED CODE ###

import sys
input = sys.stdin.readline


def inpl():
    return list(map(int, input().split()))


def GetBase(t=0):
    ret = []
    last = -C * 2 - 1
    for i, s in enumerate(S[t:]):
        if s == 'x':
            continue
        elif last + C >= i + t:
            continue

        ret.append(i + t)
        last = i + t
    return ret


def GetReverse():
    ret = []
    last = -C * 2 - 1
    for i, s in enumerate(S[::-1]):
        if s == 'x':
            continue
        elif last + C >= i:
            continue

        ret.append(len(S) - 1 - i)
        last = i
    return reversed(ret)


def GetDepend(base_ans):
    ruiseki = []
    a = 0
    for s in S:
        if s == 'o':
            a += 1
            ruiseki.append(a)
        else:
            ruiseki.append(a)

    ret = {a: False for a in base_ans}
    for a in ret:
        if ruiseki[a] == ruiseki[min(N - 1, a + C)]:
            ret[a] = True
    return ret


def solve():
    base_ans = GetBase()
    if len(base_ans) > K:
        return []

    reverse_ans = GetReverse()

    return sorted(list(set(base_ans) & set(reverse_ans)))


N, K, C = inpl()
S = list(input().strip())

ans = solve()

for a in ans:
    print(a + 1)
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    P = [(v + 1) / 2 for v in map(int, input().split())]

    ans = 0
    for i in range(N - K + 1):
        ans = max(ans, sum(P[i : i + K]))

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    P = [(v + 1) / 2 for v in map(int, input().split())]

    ans = tmp = sum(P[0:K])
    for i in range(N - K):
        tmp = tmp - P[i] + P[i + K]
        ans = max(ans, tmp)

    print(ans)


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

import fractions
import math
n = int(input())
lis = list(map(int,input().split()))
lis.sort()
nu = []
for i in range(1,math.floor(math.sqrt(lis[0]))+1):
    if lis[0] % i == 0:
        nu.append(lis[0]//i)
        nu.append(i)
nu.sort(reverse = True)
for num in nu:
    key = 1
    for i in range(n):
        if lis[i] % num != 0:
            key = 0
            break
    if key == 1:
        for i in range(n):
            lis[i] = lis[i] // num
        break
nn = 1
for i in range(n):
    nn = (nn * lis[i]) // fractions.gcd(nn,lis[i])
ans = 0
for i in range(n):
    ans += nn//lis[i]
    ans %= 10 ** 9 + 7
print(ans)

### FIXED CODE ###

from fractions import gcd
from functools import reduce

mod = 10 ** 9 + 7

def lcm(a,b):
    return a * b//gcd(a,b)

n = int(input())
lis = list(map(int,input().split()))
now = reduce(lcm,lis)

print(sum(list(map(lambda x:now//x,lis)))%mod)
### BUGGY CODE ###

import numpy as np
from numba import njit


@njit('i8[:](i8,i8,i8[:])')
def solve(N, K, A):
    for _ in range(K):
        B = np.zeros(N + 1, dtype=np.int64)
        for i in range(N):
            B[max(0, i - A[i])] += 1
            B[min(N, i + A[i] + 1)] -= 1
        if np.all(B == N):
            return B
        A = np.cumsum(B)[:-1]
    return A


N, K = map(int, input().split())
A = np.array(input().split(), dtype=int)
print(' '.join(map(str, solve(N, K, A))))


### FIXED CODE ###

import numpy as np
from numba import njit


@njit
def solve(N, K, A):
    for _ in range(K):
        B = np.zeros(N + 1, dtype=np.int64)
        for i in range(N):
            a = A[i]
            B[max(0, i - a)] += 1
            B[min(N, i + a + 1)] -= 1
        A = np.cumsum(B)[:-1]
        if np.all(A == N):
            return A
    return A


N, K = map(int, input().split())
A = np.array(input().split(), dtype=int)
print(' '.join(map(str, solve(N, K, A))))
### BUGGY CODE ###

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

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = list(map(lambda x: int(x) * (-1), input().split()))
heapq.heapify(a)

for i in range(m):
    x = heapq.heappop(a)
    heapq.heappush(a, -1 * ((-x) // 2))
print(-sum(a))
### BUGGY CODE ###

e,a = map(int,input().split())
cnt = 0
while True:
    if e ==0 and a ==0:
        break
    else:
        for i in range(1,a+1):
            for j in range(1,a+1):
                if i<j:
                    continue
                else:
                    X = a - (i + j)
                    if X > 0:
                        cnt +=1
print(cnt)


### FIXED CODE ###

while True:
    e,a = map(int,input().split())
    if e ==0 and a ==0:
        break
    cnt = 0
    for i in range(1,e+1):
        for j in range(1,e+1):
            if j<=i:
                continue
            X = a - (i + j)
            if X > j and X <=e:
                cnt +=1
    print(cnt)