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

S = list(input())
ln = len(S)
next_lr = [0] * ln
next_r = 0
next_l = 0


for i in range(ln):
    if S[i] == "R":
        if i < next_l:
            next_lr[i] = next_l - i
        else:
            for j in range(i+1,ln):
                if S[j] == "L":
                    next_l = j
                    next_lr[i] = j - i
                    break
    else:
        if i < next_r:
            next_lr[i] = next_r - i
        else:
            for j in reversed(range(0,i)):
                if S[j] == "R":
                    next_r = j
                    next_lr[i] = next_r - i
                    break

result = [0] * ln
for i in range(ln):
    nx = next_lr[i]
    if nx %2 == 0:
        result[i+nx] += 1
    elif nx > 0:
        result[i+nx-1] += 1
    else:
        result[i+nx+1] += 1

print(" ".join(map(str, result)))


### FIXED CODE ###

S = list(input())
ln = len(S)
next_lr = [0] * ln
next_r = 0
next_l = 0


for i in range(ln):
    if S[i] == "R":
        next_r = i
        if i < next_l:
            next_lr[i] = next_l - i
        else:
            for j in range(i+1,ln):
                if S[j] == "L":
                    next_l = j
                    next_lr[i] = j - i
                    break
    else:
        next_lr[i] = next_r - i


result = [0] * ln
for i in range(ln):
    nx = next_lr[i]
    if nx %2 == 0:
        result[i+nx] += 1
    elif nx > 0:
        result[i+nx-1] += 1
    else:
        result[i+nx+1] += 1

print(" ".join(map(str, result)))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
lr = []
for i in range(Q):
    lr.append(list(map(int, input().split())))

ACpos = []
Apos = -1
for i in range(N - 1):
    if("A" == S[i]):
        Apos = i
    if(("C" == S[i]) & (i - 1 == Apos)):
        ACpos.append(Apos + 1)
        Apos = -1
#print("ACpos = {}".format(ACpos))

for idx in lr:
    cnt = 0
    for pos in ACpos:
        if((idx[0] <= pos) & (pos < idx[1])):
            cnt += 1
#    print("cnt = {}, idx = {}".format(cnt, idx))
    print(str(cnt))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
lr = []
for i in range(Q):
    lr.append(list(map(int, input().split())))

ACnum = [0]
for i in range(N - 1):
    ACnum.append(ACnum[-1])
    if("AC" == S[i:i + 2]):
        ACnum[i + 1] += 1
#print("ACnum = {}".format(ACnum))

for l, r in lr:
    print(str(ACnum[r - 1] - ACnum[l - 1]))
### BUGGY CODE ###

n,q = map(int, input().split())
s = input()
li = []
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        li.append(i+1)
for i in range(q):
    l, r = map(int, input().split())
    ans = 0
    for num in li:
        if l <= num and num+1 <= r:
            ans += 1
    print(ans)

### FIXED CODE ###

n,q = map(int, input().split())
s = input()
li = [0]*(n+1)
for i in range(n):
    if s[i:i+2] == "AC":
        li[i+1] = li[i] + 1
    else:
        li[i+1] = li[i]

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

N, C = map(int, input().split())
S = []
for i in range(N):
    S.append(list(map(int, input().split())))
S.sort()
R = [[] for i in range(C)]
for i in range(N):
    c = S[i][2] - 1
    if R[c]:
        if R[c][-1][1] == S[i][0]:
            R[c][-1][1] = S[i][1]
            continue
    R[c].append(S[i][:])
    R[c][-1][0] -= 0.5
maxDup = 0
for r in R:
    for s in r:
        dup1 = 1
        dup2 = 1
        for rr in R:
            if rr == r:
                continue
            for ss in rr:
                if (s[0] >= ss[0] and s[0] < ss[1]):
                    dup1 += 1
                if (s[1] >= ss[0] and s[1] <= ss[1]):
                    dup2 += 1
        if maxDup < max(dup1, dup2):
            maxDup = max(dup1, dup2)
print(maxDup)


### FIXED CODE ###

N, C = map(int, input().split())
S = []
for i in range(N):
    S.append(list(map(int, input().split())))
S.sort()
R = [[] for i in range(C)]
for i in range(N):
    c = S[i][2] - 1
    if R[c]:
        if R[c][-1][1] == S[i][0]:
            R[c][-1][1] = S[i][1]
            continue
    R[c].append(S[i][:])
D = [0]*100001
for r in R:
    for s in r:
        for i in range(s[0], s[1]+1):
            D[i] += 1
print(max(D))
### BUGGY CODE ###

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

ans = A
for i in range(B-A):
    ans = ans ^ (A+i+1)
    
print(ans)

### FIXED CODE ###

A,B = map(int,input().split())
keta = 0
tmp = B
twos = []
base = 1
while tmp > 0:
    tmp /= 2
    keta += 1
    base *= 2
    twos.append(base)

def func(n):
    if n%2 == 0:
        tmp = (n-1)//2
        ans = tmp%2 ^ n
    else:
        tmp = (n-1)//2 
        ans = tmp%2
    return ans
    
print(func(B)^func(A-1))
### BUGGY CODE ###

member = int(input())
member_array = sorted(list(map(int, input().split())),reverse=True)
result = 0

for i in range(member):
    member_array.pop()
    member_array.pop(0)
    result += member_array.pop(0)

print(result)

### FIXED CODE ###

member = int(input())
member_array = sorted(list(map(int, input().split())),reverse=True)
result = 0
count = 1

for i in range(member):
    result += member_array[count]
    count += 2

print(result)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline

h, n = map(int, input().split())
a = map(int, read().split())
ab = zip(a, a)

INF = 10 ** 18
dp = [INF] * 10 ** 4 * 2
dp[0] = 0
for a, b in ab:
    for i in range(h):
        if dp[i + a] > dp[i] + b:
            dp[i + a] = dp[i] + b
print(min(dp[h:]))

### FIXED CODE ###

h, n = map(int, input().split())
ab = tuple(tuple(map(int, input().split())) for _ in range(n))

dp = [10 ** 20] * 10 ** 4 * 2
dp[0] = 0
for a, b in ab:
    for i in range(h):
        dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[h:]))
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
 
def main():
    n=int(input())
    A=list(map(int, input().split()))
    ans = 0
    mod = 10**9 + 7
    for i in range(60):
        q = sum(map(lambda x:((x >> i) & 0b1),A))
        ans += q*(n-q)*pow(2, i, mod)
    print(ans%mod)
 
if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
 
def main():
    n=int(input())
    A=list(map(int, input().split()))
    ans = 0
    mod = 10**9 + 7
    for i in range(60):
        q = sum(map(lambda x:((x >> i) & 0b1),A))
        ans += q*(n-q)*pow(2, i, mod)
        ans = ans % mod
    print(ans)
 
if __name__=='__main__':
    main()
### BUGGY CODE ###

n = int(input())
u = [-1] * n
u[0] = 0
a = []
for i in range(n-1):
    u1, u2, w = [int(j) for j in input().split()]
    u1, u2 = u1 - 1, u2 - 1
    a.append((u1, u2, w))
i=0
while a:
    j=a[i]
    if u[j[0]] != -1:
        u[j[1]] = (u[j[0]] + j[2]) % 2
        del a[i]
        i=0
    elif u[j[1]] != -1:
        u[j[0]] = (u[j[1]] + j[2]) % 2
        del a[i]
        i = 0
    else:
        i+=1

for i in u:
    print(i)
    


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)


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


n = int(input())
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b, c = [int(i) - 1 for i in input().split()]
    c += 1
    e[a].append([b, c])
    e[b].append([a, c])

c = [0] * n


def dfs(i=0, r=-1, co=0):
    c[i] = co
    for j, k in e[i]:
        if j != r:
            dfs(j, i, (co+k) % 2)


dfs()
print("\n".join(map(str, c)))
### BUGGY CODE ###

import math
n = int(input())
s = int(input())

def c(b):
    cur = n
    acc = 0
    while cur != 0:
        div, mod = divmod(cur, b)
        acc += mod
        cur = div
    return acc

def f():
    if n == s:
        return (n + 1)
    if n < s:
        return -1
    rt = math.ceil(math.sqrt(n))
    for b in range(2, rt + 1):
        if c(b) == s: return b
    for p in range(rt, 0, -1):
        q = s - p
        x = n - q
        b = x // p
        # if x % p == 0 and b > q and b > p and q >= 0:
        if c(b) == s:
            return b
    return -1
    
print(f())        

### FIXED CODE ###

import math
n = int(input())
s = int(input())

def c(b):
    cur = n
    acc = 0
    while cur != 0:
        div, mod = divmod(cur, b)
        acc += mod
        cur = div
    return acc

def g(b):
    if b > n: return n
    return sum(divmod(n,b))

def f():
    if n == s:
        return (n + 1)
    if n < s:
        return -1
    rt = math.ceil(math.sqrt(n))
    for b in range(2, rt + 1):
        if c(b) == s: return b
    for p in range(rt - 1, 0, -1):
        q = s - p
        x = n - q
        b = x // p
        if g(b) == s:
            return b
    return -1
    
print(f())
### BUGGY CODE ###

#pypyでreduceは速いのか?

from fractions import gcd
from functools import reduce
import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))
mod=10**9+7

lcm = reduce(lambda x,y: x*(y//gcd(x,y)), A)
ans=0
for i in range(N):
    ans+=lcm//A[i]
ans%=mod
print(ans)

### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline

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


for i in range(N):
    a=A[i]
    for j in range(2,a):
        temp=0
        while a%j==0:
            a=a//j
            temp+=1
        lcm[j]=max(lcm[j],temp)
        if a==1 or j*j>A[i]:
            break
    if a!=1:
        lcm[a]=max(lcm[a],1)
                
        
l=1
for d in lcm.items():
    l*=pow(d[0],d[1])
    

ans=0
mod=10**9+7

for i in range(N):
    ans+=l//A[i]
    
print(ans%mod)
### BUGGY CODE ###

from collections import deque

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]

q=deque()
ans=0

def bfs(i,j):
    global ans
    q.append((i,j))
    while q:
        y,x=q.popleft()
        field[y][x]=1
        if s[y][x]=='#':
            ans+=1
        for dy,dx in ((1,0),(0,1),(-1,0),(0,-1)):
            ny = y+dy
            nx = x+dx
            if 0<=ny<h and 0<=nx<w and s[y][x]!=s[ny][nx] and field[ny][nx]==float('inf'):
                field[ny][nx]=1
                q.append((ny,nx))

                         
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            field=[[float('inf') for i in range(w)] for j in range(h)]
            bfs(i,j)

print(ans)

### FIXED CODE ###

from collections import deque

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]

q=deque()
ans=0

def bfs(i,j):
    global ans
    white=0
    black=0
    q.append((i,j))
    while q:
        y,x=q.popleft()
        if s[y][x]=='#':
            black+=1
        if s[y][x]=='.':
            white+=1
        for dy,dx in ((1,0),(0,1),(-1,0),(0,-1)):
            ny = y+dy
            nx = x+dx
            if 0<=ny<h and 0<=nx<w and s[y][x]!=s[ny][nx] and field[ny][nx]==False:
                field[ny][nx]=True
                q.append((ny,nx))
    ans+=(black*white)

field=[[False]*w for j in range(h)]                         
for i in range(h):
    for j in range(w):
        if s[i][j]=='.' and field[i][j]==False:
            field[i][j]=True
            bfs(i,j)

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

from collections import defaultdict

N, K = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
dd = defaultdict(int)

ans = 0
for i in range(K, 0, -1):
    dd[i] = (K // i) ** N
    for temp in range(i * 2, K + 1, i):
        dd[i] -= dd[temp]
    ans += dd[i] * i
    ans %= mod
print(ans)


### FIXED CODE ###

from collections import defaultdict

N, K = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
dd = defaultdict(int)

ans = 0
for i in range(K, 0, -1):
    dd[i] = pow(K // i, N, mod)
    for temp in range(i * 2, K + 1, i):
        dd[i] -= dd[temp]
    ans += dd[i] * i
    ans %= mod
print(ans)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc164/tasks/abc164_d

from operator import mul
from functools import reduce
from collections import defaultdict

def combination(n, r):
    if not 0 <= r <= n: return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

S = input()
L = len(S)
res = 0

T = [0]

for i in range(1,L+1):
    """ 累積和 """
    T.append(int(S[L-i:]))

reminder = [0]*2019
for i in range(L+1):
    reminder[T[i]%2019] += 1

for c in reminder:
    res += combination(c,2)

print(res)

### FIXED CODE ###

# https://atcoder.jp/contests/abc164/tasks/abc164_d

from operator import mul
from functools import reduce
from collections import defaultdict

def combination(n, r):
    if not 0 <= r <= n: return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

S = input()

res = 0

T = [0]
x = 0
L = len(S)
for i, s in zip(range(L),reversed(S)):
    """ 累積和 """
    x = (int(s)*pow(10,i,2019) + x)%2019
    T.append(x)

reminder = [0]*2019
for i in range(L+1):
    reminder[T[i]%2019] += 1

for c in reminder:
    res += combination(c,2)

print(res)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

count = 0
a = []
while(1):
    try:
        count += 1
        a.append([int(i) for i in input().split(",")])
    except EOFError:
        break
dim = int(count/2)
b = [[0 for i in range(dim+1)] for j in range(dim+1)]
for i in range(dim):
    for j in range(i+1):
        b[i-j][j] = a[i][j]
for i in range(dim-1):
    for j in range(dim-i-1):
        b[dim-1-j][i+1+j] = a[i+dim][j]

dp_ = [[True if i < dim else 0 for i in range(dim+1)] if j < dim else [0 for i in range(dim+1)] for j in range(dim+1)]

def dp(i,j):
    if dp_[i][j]:
        dp_[i][j] = b[i][j] + max(dp(i+1,j),dp(i,j+1))
        return dp_[i][j]
    else:
        return dp_[i][j]

print(dp(0,0))


### FIXED CODE ###

from copy import copy
import sys
sys.setrecursionlimit(1000000)

count = 0
a = []
while(1):
    try:
        a.append([int(i) for i in input().split(",")])
        count += 1
    except EOFError:
        break
dim = int(count/2)+1
b = [[0 for i in range(dim+1)] for j in range(dim+1)]
for i in range(dim):
    for j in range(i+1):
        b[i-j][j] = a[i][j]
for i in range(dim-1):
    for j in range(dim-i-1):
        b[dim-1-j][i+1+j] = a[i+dim][j]

dp_ = [[True if i < dim else 0 for i in range(dim+1)] if j < dim else [0 for i in range(dim+1)] for j in range(dim+1)]

def dp(i,j):
    global dp_
    if dp_[i][j] is True:
        dp_[i][j] = b[i][j] + max(dp(i+1,j),dp(i,j+1))
        return dp_[i][j]
    else:
        return dp_[i][j]

print(dp(0,0))
### BUGGY CODE ###

from collections import Counter

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

now_cnt = len(list(set(A)))

if (now_cnt <= k):
    print(0)
    exit()

c = Counter(A)
c_sorted = sorted(c.items(), key=lambda x: x[1])
dec = now_cnt - k
cnt = 0
L = []

for (i, v) in c_sorted:
    L.append([i, v])

while True:
    if (dec != 0):
        L[0][1] -= 1
        L[-1][1] += 1
        cnt += 1
    else:
        print(cnt)
        exit()

    if (L[0][1] == 0):
        L.pop(0)
        dec -= 1

print(cnt)


### FIXED CODE ###

from collections import Counter, deque

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

now_cnt = len(list(set(A)))

if (now_cnt <= k):
    print(0)
    exit()

c = Counter(A)
c_sorted = sorted(c.items(), key=lambda x: x[1])
dec = now_cnt - k
cnt = 0
L = deque()

for (i, v) in c_sorted:
    L.append([i, v])

while True:
    if (dec != 0):
        L[0][1] -= 1
        L[-1][1] += 1
        cnt += 1
    else:
        print(cnt)
        exit()

    if (L[0][1] == 0):
        L.popleft()
        dec -= 1

print(cnt)
### BUGGY CODE ###

def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = {(i, j):0 for i in range(1, len(S)+1) for j in range(13)}
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[(1, i)] = 1
    else:
        DP_table[(1, int(digit))] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier *= 10
        multiplier %= 13
        if digit == '?':
            for j in range(10):
                devided = j * multiplier
                for k in range(13):
                    surplus = (devided + k) % 13
                    DP_table[(i + 1, surplus)] += DP_table[(i, k)] % MOD
                    DP_table[(i + 1, surplus)] %= MOD
        else:
            for k in range(13):
                surplus = (int(digit) * multiplier + k) % 13
                DP_table[(i + 1, surplus)] += DP_table[(i, k)] % MOD
                DP_table[(i + 1, surplus)] %= MOD
                
    print(DP_table[(len(S), 5)])

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = [[0 for i in range(13)] for j in range(len(S))]
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[0][i] = 1
    else:
        DP_table[0][int(digit)] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    DP_table[i][(j * multiplier + k) % 13] += DP_table[i-1][k]
        else:
            digit = int(digit)
            for k in range(13):
                DP_table[i][(digit * multiplier + k) % 13] += DP_table[i-1][k]
        
        for j in range(13):
            DP_table[i][j] %= MOD

    print(DP_table[len(S)-1][5])

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

import sys
sys.setrecursionlimit(10**7)

def cur(x):
    for i in neighbor[x]:
        ans[i]+=ans[x]
        neighbor[i].remove(x)
        cur(i)

n,q=map(int,input().split())
neighbor=[[]  for _ in range(n+1)]
parent=[-1]*(n+1)
ans=[0]*(n+1)
for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].append(b)
    neighbor[b].append(a)


for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x

cur(1)
print(" ".join(map(str,ans[1:])))


### FIXED CODE ###

n,q=map(int,input().split())
neighbor=[[]  for _ in range(n+1)]
ans=[0]*(n+1)

for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].append(b)
    neighbor[b].append(a)


for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x

visit=[True]*(n+1)
tmp=[1]
for x in tmp:
    visit[x]=False
    for y in neighbor[x]:
        if visit[y]:
            tmp.append(y)
            ans[y]+=ans[x]

print(*ans[1:])
### BUGGY CODE ###

import copy
import math

N,X = map(int,raw_input().split())
S = map(int,raw_input().split())
MOD = 10**9 + 7

S.sort()

dp = [[0 for i in range(X+1)] for j in range(N+1)]

for i in range(X+1):
  dp[1][i] = i % S[0]

for n in range(2,N+1):
  for x in range(X+1):
    #print n,x
    dp[n][x] =  dp[n-1][x] * (n-1) 
    dp[n][x] += dp[n-1][x%S[n-1]]
    dp[n][x] %= MOD

print dp[N][X]


### FIXED CODE ###

import copy
import math

N,X = map(int,raw_input().split())
S = map(int,raw_input().split())
MOD = 10**9 + 7

S.sort()

dp = [[0 for i in range(X+1)] for j in range(N+1)]

for i in range(X+1):
  dp[1][i] = i % S[0]

for n in range(2,N+1):
  for x in range(X+1):
    #print n,x
    dp[n][x] =  dp[n-1][x] * (n-1) 
    dp[n][x] += dp[n-1][x%S[n-1]]
    dp[n][x] %= MOD

print dp[N][X]
### BUGGY CODE ###


from collections import Counter
from itertools import product

n,m,q  = map(int,input().split())
rails=[tuple(map(int,input().split())) for i in range(m)]
qs=[tuple(map(int,input().split())) for i in range(q)]

xlist = [[0 for j in range(n)] for i in range(n)]
sumlist = [[0 for j in range(n+1)] for i in range(n)]
sumsumlist = [[0 for j in range(n+1)] for i in range(n+1)]
for (l,r),i in Counter(rails).items():
    xlist[l-1][r-1]=i


for (i,j) in product(range(n),range(n)):
    sumlist[i][j+1]=sum(xlist[i][0:j+1])

for (i,j) in product(range(n),range(n)):
    sumsumlist[i+1][j+1] = sum([sumlist[l][j+1] for l in range(0,i+1)])



for (p,q) in qs:
    ans = sumsumlist[q][q]- sumsumlist[q][p-1] -sumsumlist[p-1][q] + sumsumlist[p-1][p-1]
    print(ans)


### FIXED CODE ###

from collections import Counter
from itertools import product

n,m,q  = map(int,input().split())
rails=[tuple(map(int,input().split())) for i in range(m)]
qs=[tuple(map(int,input().split())) for i in range(q)]

xlist = [[0 for j in range(n)] for i in range(n)]
sumlist = [[0 for j in range(n+1)] for i in range(n)]
for (l,r),i in Counter(rails).items():
    xlist[l-1][r-1]=i


for (i,j) in product(range(n),range(n)):
    sumlist[i][j+1]=sum(xlist[i][0:j+1])


for (p,q) in qs:
    ans = 0
    for i in range(p-1,q):
        ans = ans+sumlist[i][q]-sumlist[i][p-1]
    print(ans)
### BUGGY CODE ###

import numpy as np

n, k = map(int, input().split())
A = np.array(list(map(int, input().split())))
A = np.append(A, 0)
for _ in range(k):
    l = np.zeros((n + 1,), int)
    for i, a in enumerate(A[:-1]):
        l[max(0, i - a)] += 1
        l[min(n, i + a + 1)] -= 1
    A = np.cumsum(l)
    if np.all(A[:-1] == n):
        break
print(*A[:-1])

### FIXED CODE ###

import numpy as np
from numba import jit


@jit("i8, i8, i8[:]")
def myfunc(n, k, A):
    for _ in range(k):
        l = np.zeros((n + 1,), dtype=np.int64)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = np.cumsum(l)
        if np.all(A[:-1] == n):
            break
    return A


def main():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype=np.int64)
    A = np.append(A, 0)
    print(*myfunc(n, k, A)[:-1])


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

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

l = len(S)
if P == 2:
    ans = 0
    for i in range(l):
        if int(S[i])%2 == 0:
            ans += i+1
elif P == 5:
    ans = 0
    for i in range(l):
        if int(S[i])%5 == 0:
            ans += i+1
else:
    data = [0]*P
    for i in range(l-1, -1, -1):
        data[int(S[i:l])%P] += 1
    ans = data[0]
    for item in data:
        if item > 1:
            ans += item*(item-1)//2

print(ans)

### FIXED CODE ###

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

l = len(S)
if P == 2:
    ans = 0
    for i in range(l):
        if S[i]%2 == 0:
            ans += i+1
elif P == 5:
    ans = 0
    for i in range(l):
        if S[i]%5 == 0:
            ans += i+1
else:
    data = [0]*P
    temp = 0
    ans = 0
    for i in range(l-1, -1, -1):
        temp += S[i]*pow(10, l-i-1, P)
        temp %= P
        ans += data[temp]
        data[temp] += 1
    ans += data[0]

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

import sys
input = sys.stdin.readline

s = input().split()[0]
q = int(input())

for _ in range(q):
    q_i = input().split()
    if len(q_i) == 1:
        s = s[::-1]
    else:
        _, f, c = q_i
        f = int(f)
        if f == 1:
            s = c + s
        else:
            s = s + c

print(s)

### FIXED CODE ###

import sys
input = sys.stdin.readline

s = input().split()[0]
q = int(input())

left, right = [], []
state = 1
for _ in range(q):
    q_i = input().split()
    if len(q_i) == 1:
        state = (state)%2 + 1
    else:
        _, f, c = q_i
        f = int(f)
        if (f+state)%2 == 0:
            left += [c]
        else:
            right += [c]
if state == 1:
    print(''.join(left[::-1]) + s + ''.join(right))
else:
    print(''.join(right[::-1]) + s[::-1] + ''.join(left))
### BUGGY CODE ###

num = int(input())
lists = []
for i in range(num):
    x = input()
    if x not in lists:
        lists.append(x)
print(len(lists))

### FIXED CODE ###

num = int(input())
count = num
lists = []
for i in range(num):
    lists.append(input())
print(len(set(lists)))
### BUGGY CODE ###

n, m = map(int, input().split())
a = map(int, input().split())
a = sorted(a)[::-1]
for i in range(m):
  a[0] = int(a[0] / 2)
  a = sorted(a)[::-1]
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):
  tmp = int(heapq.heappop(a) / 2)
  heapq.heappush(a, tmp)
print(-1 * sum(a))