Harryxun/stf_run huggingface dataset:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline
input = sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

import numpy as np

def main():
	n,s=MI()
	A=LI()

	li=[0]*(s+10)
	li=np.array(li)
	li[0]=1
	#print(li)

	for i in A:
		tmp=li.copy()
		li*=2
		li[i:]+=tmp[:s+10-i]
		li%=998244353
		#print(li)
	print(li[s])



if __name__ == "__main__":
	main()


### FIXED CODE ###

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

import numpy as np

def main():
	n,s=MI()
	A=LI()

	li=[0]*(3010)
	li=np.array(li)
	li[0]=1
	#print(li)

	for i in A:
		tmp=li.copy()
		li*=2
		li[i:]+=tmp[:3010-i]
		li%=998244353
		#print(li)
	print(li[s])



if __name__ == "__main__":
	main()
n = int(input())
a = list(map(int, input().split()))

count = 0
sum_a = a[0]
for i in range(n - 1):
    sum_a2 = sum_a + a[i + 1]
    if sum_a * sum_a2 >= 0:
        count += abs(sum_a2) + 1
        sum_a2 = - abs(sum_a) // sum_a
    sum_a = sum_a2
print(count)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [a[0]]
for i in range(n - 1):
    b.append(b[-1] + a[i + 1])
f = [True, False]
ans = float("inf")
for i in f:
    flag = i
    count = 0
    num = 0
    for j in range(n):
        if flag == True:
            if b[j] + num <= 0:
                count += 1 - b[j] - num
                num += 1 - b[j] - num
            flag = False
        else:
            if b[j] + num >= 0:
                count += b[j] + num + 1
                num -= b[j] + num + 1
            flag = True
    ans = min(ans, count)
print(ans)
a,b,n = map(int, input().split())

t=0
xx=1
l=[-1]*(b+1)
p=1
d=b//a
if d==0:
   d=1
if n>=b and b>1:
   while t == 0 and xx <= n:
      c=a*xx%b
      if l[c]==-1:
         l[c]=xx
      else:
         t=1
      xx+=d
   while t>-1:

      if l[p]>-1:
         t=-2
         x=l[p]
      p+=1
else:
   x=n
print(a*x//b-a*(x//b))


### FIXED CODE ###


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


if n>=b-1:
    x=b-1
else:
    x=n
print(a*x//b-a*(x//b))
n, k =map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
roop = []
seen = [0 for  _ in range(n)]
count = 0
for i in range(n):
    if seen[i]>0:
        continue
    else:
        count+=1
        seen[i] = count
        roop.append([c[i]])
        t = i
        while i!=p[t]-1:
            seen[p[t]-1]=count
            roop[-1].append(c[p[t]-1])
            t = p[t]-1
#print(seen)
#print(roop)
ans = max(c)

for i in roop:
    #print(ans)
    
    s = sum(i)
    ii = i+i
    #print(ii)
    if len(i)>=k:
        for j in range(1, k+1):
            temp = sum(ii[:j])
            for l in range(len(i)):
                if l!=0:
                    temp+=ii[l+j-1]
                    temp-=ii[l-1]
                    #temp = sum(ii[l:l+j])
                #print(i, j, l, temp)
                ans  = max(ans, temp)
    else:
        for j in range(1, len(i)+1):
            temp=  sum(ii[:j])
            for l in range(len(i)):
                if l != 0:
                    temp+=ii[l+j-1]
                    temp-=ii[l-1]
                #print(temp)
                if s>0:
                    temp1 = temp+s*((k-j)//len(i))
                
                #print(i, j, l, temp)
                ans  = max(ans, temp)
                ans  = max(ans, temp1)
            
print(ans)

        


### FIXED CODE ###

n, k =map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
roop = []
seen = [0 for  _ in range(n)]
count = 0
for i in range(n):
    if seen[i]>0:
        continue
    else:
        count+=1
        seen[i] = count
        roop.append([c[i]])
        t = i
        while i!=p[t]-1:
            seen[p[t]-1]=count
            roop[-1].append(c[p[t]-1])
            t = p[t]-1
#print(seen)
#print(roop)
ans = max(c)

for i in roop:
    #print(ans)
    
    s = sum(i)
    ii = i+i
    #print(ii)
    if len(i)>=k:
        for j in range(1, k+1):
            temp = sum(ii[:j])
            for l in range(len(i)):
                if l!=0:
                    temp+=ii[l+j-1]
                    temp-=ii[l-1]
                    #temp = sum(ii[l:l+j])
                #print(i, j, l, temp)
                ans  = max(ans, temp)
    else:
        for j in range(1, len(i)+1):
            temp=  sum(ii[:j])
            for l in range(len(i)):
                if l != 0:
                    temp+=ii[l+j-1]
                    temp-=ii[l-1]
                #print(temp)
                if s>0:
                    temp1 = temp+s*((k-j)//len(i))
                else:
                    temp1 = temp
                
                #print(i, j, l, temp)
                ans  = max(ans, temp)
                ans  = max(ans, temp1)
            
print(ans)
import bisect
n=int(input())
a=[int(input()) for i in range(n)]
inf=10**6
tmp=[inf]*n
ans=0
for i in range(n-1,-1,-1):
  j= bisect.bisect_right(tmp,a[i])
  tmp[j]=a[i]
for i in range(n):
  if tmp[i]!=inf:
    ans+=1
print(ans)

### FIXED CODE ###

import bisect
n=int(input())
a=[int(input()) for i in range(n)]
inf=10**9+1
tmp=[inf]*n
ans=0
for i in range(n-1,-1,-1):
  j= bisect.bisect_right(tmp,a[i])
  tmp[j]=a[i]
for i in range(n):
  if tmp[i]!=inf:
    ans+=1
print(ans)
import numpy as np
N,M=[int(i) for i in input().split(" ")]
 
G=np.zeros((N,N),dtype=np.int)
for i in range(N+M-1):
    A,B=[int(j)-1 for j in input().split(" ")]
    G[A][B]=1
for i in range(M):
    x=np.sum(G,axis=0).argmax()
    y=np.sum(G,axis=1).argmax()
    G[y][x]-=1
 
for l in G.T:
    if np.sum(l)==0:
        print("0")
    else:
        print(l.argmax()+1)

### FIXED CODE ###

N,A,B=[int(i) for i in input().split(" ")]
maximum=min(A,B)
minimum=max(A+B-N,0)
print(maximum,minimum)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;
    long long ans = 0, sum =0;
    int mod = 1000000000+7;
    cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; i++) {
        cin >> a.at(i);
        sum += a.at(i);
        sum %= mod;
    }
    for (int i = 0; i < N; i++) {
        sum -= a.at(i);
        if(sum<0) sum += mod;
        ans += sum * a.at(i);
        ans %= mod;
    }
    cout << ans << endl;
}


### FIXED CODE ###

def main():
    n = int(input())
    a = []
    sum = 0             #longの気持ち
    ans = 0             #long long の気持ち
    mod = 1_000_000_000 + 7
    x = list(map(int, input().split()))
    for i in range(n):
        sum += x[i]           
        a.append(x[i])
    
    for i in range(n):
        sum -= a[i]
        ans += sum * a[i]
        ans %= mod
    print(ans)

if __name__ == "__main__":
    main()
N = int(input())
T, A = map(int, input().split())
H_list = list(map(int, input().split()))

pre = A
'''
3
21 -11
81234 52141 94124
'''
for i, h in enumerate(H_list):
    if i == 0:
        ans = i
        pre = T - h * 0.006
        continue
    kion = T - h * 0.006
    if abs(A - kion) < abs(A - pre):
        #print(kion)
        #print(pre)
        #print(abs(A - kion),'kion')
        #print(abs(A - pre),'pre')
        ans = i
print(ans + 1)

### FIXED CODE ###

X, Y = map(int,input().split())
print(X + Y//2)
n, a, b = int(input().split())
if a*n > b:
  print(a*n)
else:
  print(b)


### FIXED CODE ###

n, a, b = map(int, input().split())
if a*n < b:
  print(a*n)
else:
  print(b)
N=int(input())
 
A=list(map(int,input().split()))
#B=[]
#C=[]
D=[0]*1000000
E=[0]*1000000
 
ans=0
 
for i in range(N):
  #B.append(A[i]+i+1)
  #C.append(-A[i]+i+1)
  D[2*A[i]+i]+=1
  E[i]+=1
 
for i in range(1000000):
  #ans+=C.count(i)
  ans+=D[i]*E[i]
 
print(ans)

### FIXED CODE ###

N=int(input())
 
A=list(map(int,input().split()))
#B=[]
#C=[]
D=[0]*1000000
E=[0]*1000000
 
ans=0
 
for i in range(N):
  if A[i]<500000:
  #B.append(A[i]+i+1)
  #C.append(-A[i]+i+1)
  #if -A[i]+i>=0:
  	D[A[i]+i]+=1
  	E[-A[i]+i]+=1
   #print(E[-A[i]+i],-A[i]+i)

for i in range(1000000):
  #ans+=C.count(i)
  ans+=D[i]*E[i]
 
print(ans)
s = list(input())
if s[3] == '7':
  ans = s[:3] + '8' + s[4:]
else:
  ans = s
print(ans)

### FIXED CODE ###

s = input()
if s[3] == '7':
  ans = s[:3] + '8' + s[4:]
else:
  ans = s
print(ans)
#!/usr/bin/env python3
import sys
from collections import defaultdict

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, a: "List[int]"):
    A = defaultdict(lambda : 0)
    for x in a:
        A[x] += 1
    if len(A) == 1 and 0 in A:
        print(YES)
        return
    if N % 3 != 0:
        print(NO)
        return
    if len(A) == 2 and A[0] == N // 3:
        print(YES)
        return
    if len(A) > 3:
        print(NO)
        return
    L = list(A.keys())
    if L[0] ^ L[1] != L[2]:
        print(NO)
        return
    if A[L[0]] != A[L[1]] or A[L[0]] != A[L[2]]:
        print(NO)
        return
    print(YES)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import defaultdict

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, a: "List[int]"):
    A = defaultdict(lambda : 0)
    for x in a:
        A[x] += 1
    if len(A) == 1 and 0 in A:
        print(YES)
        return
    if N % 3 != 0:
        print(NO)
        return
    if len(A) == 2 and A[0] == N // 3:
        print(YES)
        return
    if len(A) != 3:
        print(NO)
        return
    L = list(A.keys())
    if L[0] ^ L[1] != L[2]:
        print(NO)
        return
    if A[L[0]] != A[L[1]] or A[L[0]] != A[L[2]]:
        print(NO)
        return
    print(YES)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()
N = int(input())
S = {}

for i in range(N):
    arg = input()
    if (arg in S):
        S[arg] = S[arg] + 1
    else:
        S[arg] = 1
# valSorted = sorted(S.items(), key=lambda x:(-x[1], x[0]))
breakKey = None
for key, value in valSorted:
    if breakKey is None:
        breakKey = value
    if breakKey != value:
        break
    print(str(key))

### FIXED CODE ###

N = int(input())
S = {}

for i in range(N):
    arg = input()
    if (arg in S):
        S[arg] = S[arg] + 1
    else:
        S[arg] = 1
valSorted = sorted(S.items(), key=lambda x:(-x[1], x[0]))
breakKey = -1
for key, value in valSorted:
    if breakKey == -1:
        breakKey = value
    if breakKey != value:
        break
    print(str(key))
import math

def prime_factorization(n):
    s = math.floor(math.sqrt(n)) # 平方根を小数点切り捨て
    ans = [] # [素数, 指数]のリスト

    # 2からsまでの素因数を求める
    for i in [2] + list(range(3, s + 1, 2)):
        if n < i:
            break
        if n % i == 0:
            r = 0 # 指数カウンタクリア
            while n % i == 0:
                r += 1
                n //= i
            ans.append([i, r])

    # 残った素数を追加
    if n > s:
        ans.append([n, 1])

    return(ans)


A, B = [int(a) for a in input().split()]

# d = gcd(A, B) = p_1^(e_1) + p_2^(e_2) + ... + p_k^(e_k)
# と素因数分解できる場合、答えは k + 1
d = math.gcd(A, B)
pf = prime_factorization(d)
print(len(pf) + 1)


### FIXED CODE ###

### Pythonのバージョンが3.4.3なのでmath.gcd(*, *)がエラーとなるらしい。
import fractions
import math

def prime_factorization(n):
    s = math.floor(math.sqrt(n)) # 平方根を小数点切り捨て
    ans = [] # [素数, 指数]のリスト

    # 2からsまでの素因数を求める
    for i in [2] + list(range(3, s + 1, 2)):
        if n < i:
            break
        if n % i == 0:
            r = 0 # 指数カウンタクリア
            while n % i == 0:
                r += 1
                n //= i
            ans.append([i, r])

    # 残った素数を追加
    if n > s:
        ans.append([n, 1])

    return(ans)


A, B = [int(a) for a in input().split()]

# d = gcd(A, B) = p_1^(e_1) + p_2^(e_2) + ... + p_k^(e_k)
# と素因数分解できる場合、答えは k + 1
d = fractions.gcd(A, B)
pf = prime_factorization(d)
print(len(pf) + 1)
import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
a.sort()
bc.sort(key=lambda x:x[1],reverse=True)
s=0
for i in range(m):
  if a[s]<bc[i][1]:
    t=bisect.bisect_left(a,bc[i][1],s,n)
    for j in range(s,min(t,s+bc[i][0])):
      a[j]=bc[i][1]
    s=min(t,s+bc[i][0])
    if s>=n:
      break
  else:
    break
print(sum(ans))


### FIXED CODE ###

import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
a.sort()
bc.sort(key=lambda x:x[1],reverse=True)
s=0
for i in range(m):
  if a[s]<bc[i][1]:
    t=bisect.bisect_left(a,bc[i][1],s,n)
    for j in range(s,min(t,s+bc[i][0])):
      a[j]=bc[i][1]
    s=min(t,s+bc[i][0])
    if s>=n:
      break
  else:
    break
print(sum(a))
n,k = map(int,input().split( ))
h = list(map(int, input().split( )))
dp =[abs(h[i]-h[0]) for i in range(k)]
for i in range(2,k):
    tmp =[]
    for j in range(i+1):
        #tmp =[]
        #print(*dp)
        #print(dp[j])
        #print(*h)
        #print(h[i],h[j],i,j)
        tmp.append(dp[j]+abs(h[i]-h[j]))#こっちはdp[j],h[j]
    dp[i]= min(tmp)
for i in range(k,n):
    tmp =[]
    for j in range(1,k+1):#+1
        tmp.append(dp[i-j]+abs(h[i]-h[i-j]))#こっちはdp[i-j],h[i-j]
    dp.append(min(tmp))
print(*dp)
print(dp[n-1])


### FIXED CODE ###

import sys
n,k = map(int,input().split( ))
if k>n:
    flag =1
else:
    flag =0
    
k = min(k,n)
h = list(map(int, input().split( )))
dp =[abs(h[i]-h[0]) for i in range(k)]
for i in range(2,k):
    tmp =[]
    for j in range(i+1):
        #tmp =[]
        #print(*dp)
        #print(dp[j])
        #print(*h)
        #print(h[i],h[j],i,j)
        tmp.append(dp[j]+abs(h[i]-h[j]))#こっちはdp[j],h[j]
    dp[i]= min(tmp)
if flag:
    print(dp[-1])
    sys.exit()
for i in range(k,n):
    tmp =[]
    for j in range(1,k+1):#+1
        tmp.append(dp[i-j]+abs(h[i]-h[i-j]))#こっちはdp[i-j],h[i-j]
    dp.append(min(tmp))
#print(*dp)
print(dp[n-1])
#16:07
n = int(input())
raw = []
for _ in range(n):
  raw.append(list(map(lambda x: int(x)-1, input().split())))
cnt = [0 for _ in range(n)]
tmp = [0 for _ in range(n)]
now = [i for i in range(n)]
ans = 0
while now:
  ans += 1
  last = now
  now = []
  for x in last:
    tmp[x] = 0
  for x in last:
    try:
      y = raw[x][cnt[x]]
      if tmp[x] == tmp[y] == 0 and x == raw[y][cnt[y]]:
        cnt[x] += 1
        cnt[y] += 1
        tmp[x] = 1
        tmp[y] = 1
        now.append(x)
        now.append(y)
    except:
      pass
  #print(now)
if cnt == [n-1 for _ in range(n)]:
  print(ans-1)
else:
  print(-1)

### FIXED CODE ###

a = input()
b = input()
ans = 0
for i in range(3):
  if a[i] == b[i]:
    ans += 1
print(ans)
N,M = map(int,input().split())
A = list(map(int,[input() for i in range(M)]))

dp = {i:0 for i in A}

dp[0]=1 # 0段目

safe_stairs = list(range(1,N+1))
[safe_stairs.remove(a) for a in A]
  
for i in safe_stairs:  
  dp[i]=dp[i-1]+dp[i-2]
print(dp[N]%1000000007)  

### FIXED CODE ###

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
dp=[0]*(n+1)
dp[0]=1

af = [0]*(n+1)
for ai in a:
  af[ai]+=1

if 1 in a:
  dp[1]=0
else:
  dp[1]=1

  
for i in range(2,n+1):
  dp[i]=dp[i-2]+dp[i-1]
  if af[i]==1:    
    dp[i]=0

print(dp[-1]%1000000007)
s = input()
K = int(input())
LIST = []
for i in range(len(s)-1):
    j=i+1
    while j<=len(s):
        if s[i:j] not in LIST:
            LIST.append(s[i:j])
            LIST.sort()
            LIST[0:K]
        j+=1

print(LIST[K-1])

### FIXED CODE ###

a,b,c,d = map(int, input().split())
if abs(a-c)<=d or (abs(a-b)<=d and abs(b-c)<=d):
    print("Yes")
else:
    print("No")
from numpy import argmax, argmin
N = int(input())
V = list(map(int, input().split()))
V1 = []
V2 = []
for i in range(N):
    if i%2==0:
        V1.append(V[i])
    else:
        V2.append(V[i])

Cnt = [0]*10001
for v in V1:
    Cnt[v] += 1
a1 = N//2-max(Cnt)
arg1 = argmax(Cnt)
Cnt[arg1] = 0
a11 = N//2-max(Cnt)


Cnt = [0]*10001
for v in V2:
    Cnt[v] += 1
a2 = N//2-max(Cnt)
arg2 = argmax(Cnt)
Cnt[arg2] = 0
a22 = N//2-max(Cnt)
#print(arg1, arg2, a1, a11, a2, a22)
if arg1==arg2:
    print(min(a1+a22, a2+a11))
else:
    print(a1+a2)


### FIXED CODE ###

from numpy import argmax, argmin
N = int(input())
V = list(map(int, input().split()))
V1 = []
V2 = []
for i in range(N):
    if i%2==0:
        V1.append(V[i])
    else:
        V2.append(V[i])

Cnt = [0]*100001
for v in V1:
    Cnt[v] += 1
a1 = N//2-max(Cnt)
arg1 = argmax(Cnt)
Cnt[arg1] = 0
a11 = N//2-max(Cnt)


Cnt = [0]*100001

for v in V2:
    Cnt[v] += 1
a2 = N//2-max(Cnt)
arg2 = argmax(Cnt)
Cnt[arg2] = 0
a22 = N//2-max(Cnt)
#print(arg1, arg2, a1, a11, a2, a22)
if arg1==arg2:
    print(min(a1+a22, a2+a11))
else:
    print(a1+a2)
import sys
input = sys.stdin.readline
n = int(input())
D = list(map(int,input().split()))

C = [0] * 13
C[0] = 1
for i in range(n):
    C[D[i]] += 1

if C[0] >= 2 or C[12] >=2:
    print(0)
    sys.exit()

for i in range(n):
    if C[i] >= 3:
        print(0)
        sys.exit()

D = []
for i in range(13):
    for j in range(C[i]):
        D.append(i)
n = len(D)
A = [0] * n
ans0 = 0
for i in range(2**n):
    ib = format(i, "b").zfill(n)
    for j in range(n):
        A[j] = D[j] * (-1) ** int(ib[j])
    ans = 30
    for j in range(n):
        for k in range(j+1, n):
            di = abs(A[k] - A[j])
            # print(ans)
            ans = min(ans, min(di, 24-di))
    # print(ib, ans0,ans)
    ans0 = max(ans0, ans)
print(ans0)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
D = list(map(int,input().split()))
# from random import randint

# n = randint(1, 50)
# D = [randint(0, 12) for i in range(n)]

C = [0] * 13
C[0] = 1
for i in range(n):
    C[D[i]] += 1

if C[0] >= 2 or C[12] >=2:
    print(0)
    sys.exit()

for i in range(13):
    if C[i] >= 3:
        print(0)
        sys.exit()

# D = []
# for i in range(13):
#     for j in range(C[i]):
#         D.append(i)
# n = len(D)
# A = [0] * n

# print(C)
ans0 = 0
for i in range(2**13):
    zero = 0
    ib = format(i, "b").zfill(13)
    A = []
    for j in range(13):
        if C[j] == 1:
            A.append(j * (-1) ** int(ib[j]))
        if C[j] == 2:
            if int(ib[j]) == 0:
                A.append(j)
                A.append(-j)
            else:
                zero = 1
    if zero == 1:
        continue
    # print("not cont")
    ans = 30
    # if len(A)>1:
        # print(A)
    # print(ib, A)
    for j in range(len(A)):
        for k in range(j+1, len(A)):
            di = abs(A[k] - A[j])
            # print(ans)
            ans = min(ans, min(di, 24-di))
            if ans <= ans0:
                break
        if ans <= ans0:
            break
    # print(ib, ans0,ans)
    ans0 = max(ans0, ans)
print(ans0)
n,p = map(int,input().split())
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
a = primes(int(p**(1/n)))
res = 1
for j in range(len(a)):
 q = p
 if q%(a[j]**n) == 0:
  c = 0
  while q%(a[j]**n) == 0:
   q = q//(a[j]**n)
   c += 1
  res = res*(a[j]**c)
print(res)

### FIXED CODE ###

n,p = map(int,input().split())
if n == 1:
  print(p)
  exit()
a = 1
for k in range(2,1000001):
  c = 0
  while p%k == 0:
    p = p//k
    c += 1
  a *= k**(c//n)
  if p == 1:
    break
print(a)
input()
A = [int(_) for _ in input().split()]
A = [A[0]] + [j for i, j in zip(A, A[1:]) if i >= j]
N = len(A)


def is_possible(K):
    dp = [0] * A[0]
    for i in range(1, N):
        dp = dp[:A[i]]
        while True:
            if dp[-1] < K - 1:
                dp[-1] += 1
                break
            else:
                dp.pop()
            if not dp:
                return False
    return True


def bis(x, y):
    if y == x + 1:
        return y
    elif is_possible((x + y) // 2):
        return bis(x, (x + y) // 2)
    else:
        return bis((x + y) // 2, y)


print(bis(0, N))


### FIXED CODE ###

import random
input()
A = [int(_) for _ in input().split()]
A = [A[0]] + [j for i, j in zip(A, A[1:]) if i >= j]
N = len(A)


def cut(array, index):
    if index < 1:
        return []
    if index <= array[0][0]:
        return [(index, array[0][1])]
    for _ in range(len(array)-1, 0, -1):
        if array[_ - 1][0] < index:
            return array[:_] + [(index, array[_][1])]


def is_possible(K):
    dp = [(A[0], 0)]
    for a in A[1:]:
        if a <= dp[-1][0]:
            dp = cut(dp, a)
        else:
            dp += [(a, 0)]
        is_added = False
        for j in range(len(dp) - 1, -1, -1):
            if dp[j][1] < K - 1:
                dp = cut(dp, dp[j][0] - 1) + [(dp[j][0], dp[j][1] + 1)]
                if dp[-1][0] < a:
                    dp += [(a, 0)]
                is_added = True
                break
        if not is_added:
            return False
    return True


def bis(x, y):
    if y == x + 1:
        return y
    elif is_possible((x + y) // 2):
        return bis(x, (x + y) // 2)
    else:
        return bis((x + y) // 2, y)


print(bis(0, N))
import numpy as np
# from numba import njit
# from numba import jit

# @jit(cache = True)
def main(N, K, A):
    A = np.array(A, dtype = int)
    for k in range(K):
        # print(k)
        B = np.zeros(N, dtype = int)
        for x in range(N):
            minimum = max(0, x - A[x])
            maximum = min(N, x + A[x] + 1)
            # B[minimum:maximum] += 1
            B[minimum] += 1
            B[maximum] -= 1
            A = np.cumsum(B)
        if np.all(A == N):
            # print(k)
            break
    print(' '.join([str(i) for i in A]))



if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    main(N, K, A)

### FIXED CODE ###

import numpy as np
from numba import njit


def main(N, K, A):
    @njit(cache = True) # numpyの高速化．雲泥の差になった．知らなかった．
    def rep(N, A):
        B = np.zeros(N + 1, dtype=np.int64) # np.int64としないとnjitがエラー
        for x in range(N):
            minimum = max(0, x - A[x])
            maximum = min(N, x + A[x] + 1)
            # B[minimum:maximum] += 1   # これだと実質for文回してるような感じだから遅い？
            B[minimum] += 1
            B[maximum] -= 1
        # return B  # これだと実質for文回してるような感じだから遅い？
        return np.cumsum(B)[:-1]

    A = np.array(A, dtype=np.int64)
    for k in range(K):
        B = rep(N, A)
        if np.array_equal(A, B):
            break
        else:
            A = B
    return A



if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    print(' '.join([str(i) for i in main(N, K, A)]))