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

def main():
  import collections
  import sys
  input = sys.stdin.readline
  H, W = map(int, input().split())
  A = [list(input()) for i in range(H)]
  dp = [[-1]*W for i in range(H)]

  q = collections.deque()
  for i in range(H):
    for j in range(W):
      if A[i][j] == "#":
          dp[i][j] = 0
          q.append([i, j])


  while(q):
    x, y = q.popleft()
    if x > 0:
      if dp[x-1][y] == -1:
          dp[x-1][y] = dp[x][y]+1
          q.append([x-1, y])
    if x < H-1:
      if dp[x+1][y] == -1:
          dp[x+1][y] = dp[x][y]+1
          q.append([x+1, y])
    if y > 0:
      if dp[x][y-1] == -1:
          dp[x][y-1] = dp[x][y]+1
          q.append([x, y-1])
    if y < W-1:
      if dp[x][y+1] == -1:
          dp[x][y+1] = dp[x][y]+1
          q.append([x, y+1])
  ans = 0
  for i in range(H):
    ans = max(ans, max(dp[i]))
  print(ans)
main()


### FIXED CODE ###

import collections
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
dp = [[H+W]*W for i in range(H)]

q = collections.deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            dp[i][j] = 0
            q.append([i, j])
            break
    if q:
        break


while(q):
    x, y = q.popleft()
    if x > 0:
        if dp[x-1][y] > dp[x][y]+1:
            if A[x-1][y] == ".":
                dp[x-1][y] = dp[x][y]+1
            else:
                dp[x-1][y] = 0
            q.append([x-1, y])
    if x < H-1:
        if dp[x+1][y] > dp[x][y]+1:
            if A[x+1][y] == ".":
                dp[x+1][y] = dp[x][y]+1
            else:
                dp[x+1][y] = 0
            q.append([x+1, y])
    if y > 0:
        if dp[x][y-1] > dp[x][y]+1:
            if A[x][y-1] == ".":
                dp[x][y-1] = dp[x][y]+1
            else:
                dp[x][y-1] = 0
            q.append([x, y-1])
    if y < W-1:
        if dp[x][y+1] > dp[x][y]+1:
            if A[x][y+1] == ".":
                dp[x][y+1] = dp[x][y]+1
            else:
                dp[x][y+1] = 0
            q.append([x, y+1])
ans = 0
for i in range(H):
    ans = max(ans, max(dp[i]))
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
As = set(map(lambda a: int(a) >> 1, input().split()))

from fractions import gcd
from functools import reduce

l = reduce(lambda a, b: a * b // gcd(a, b), As)

i = 2
while l & (i - 1) == 0:
    i <<= 1
i = (i >> 1) - 1

fg = False
if i > 0:
    for a in As:
        if a & i > 0:
            fg = True
            break

if fg:
    print(0)
else:
    print(M // l - M // (l * 2))

### FIXED CODE ###

N, M = map(int, input().split())
As = list(map(lambda a: int(a) >> 1, input().split()))

from fractions import gcd

l = As[0]
for a in As:
    l = l * a // gcd(l, a)
    if l > M:
        break

if l <= M:
    i = 2
    while l & (i - 1) == 0:
        i <<= 1
    i = (i >> 1) - 1

    fg = False
    if i > 0:
        for a in As:
            if a & i > 0:
                fg = True
                break

    if fg:
        print(0)
    else:
        print(M // l - M // (l * 2))
else:
    print(0)
### BUGGY CODE ###



if __name__ == "__main__":

    n = int(input())

    number_list = list(map(int,input().split()))
    tmp_list = number_list[:]
    tmp_list.sort()

    for number in number_list:
        i = tmp_list.index(number)
        if i < (n/2):
            print(tmp_list[int(n/2)])
        else :
            print(tmp_list[int(n/2)-1])


### FIXED CODE ###



n = int(input())

number_list = list(map(int,input().split()))
tmp_list = sorted(number_list)


for number in number_list:
    if number < tmp_list[n//2]:
        print(tmp_list[n//2])
    else :
        print(tmp_list[n//2-1])
### BUGGY CODE ###

import sys
imput=sys.stdin.readline
n,m=map(int,input().split())
l=[int(input()) for i in range(m)]
#print(l)
dp=[0]*(n+1)
dp[0]=1
if 1 not in l:
    dp[1]=1
else:dp[1]=0 
for i in range(2,n+1):
    if i in l:
        dp[i]=0
    else:
        dp[i]=(dp[i-1]%(10**9+7)+dp[i-2]%(10**9+7))%(10**9+7)
print(dp[-1]%(10**9+7))

### FIXED CODE ###

n,m=map(int,input().split())
a=[-1]
for i in range(m):
    s=int(input())
    a.append(s)  
a.append(n+1)
if 1 in a:
    a=a[1:]
if n-1 in a:
    a=a[:-1]
b=[]
for i in range(len(a)-1):
    b.append(a[i+1]-a[i]-2)
l=[1,1,2]
for i in range(3,n+1):
    l.append(l[i-2]+l[i-1])
ans=1
#print(a,b,l)
for i in range(len(b)):
    if b[i]<0:
        print(0)
        break
    else:
        ans*=l[b[i]]%1000000007
else:
    print(ans%1000000007)
### BUGGY CODE ###

h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
flag = [[False] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        flag[i][j] = s[i][j] == "."
a = [[0] * w for i in range(h)]
for i in range(h):
    count = 0
    for j in range(w):
        if flag[i][j]:
            count += 1
            a[i][j] = count
        else:
            count = 0
for i in range(h - 1, -1, -1):
    m = 0
    for j in range(w - 1, -1, -1):
        if flag[i][j]:
            if m:
                a[i][j] = m
            else:
                m = a[i][j]
        else:
            m = 0
b = [[0] * w for i in range(h)]
for j in range(w):
    count = 0
    for i in range(h):
        if flag[i][j]:
            count += 1
            b[i][j] = count
        else:
            count = 0
for j in range(w - 1, -1, -1):
    m = 0
    for i in range(h - 1, -1, -1):
        if flag[i][j]:
            if m:
                b[i][j] = m
            else:
                m = b[i][j]
        else:
            m = 0
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, a[i][j] + b[i][j] - 1)
print(ans)

### FIXED CODE ###

h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
hc = [[0] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            if j > 0:
                hc[i][j] = hc[i][j - 1] + 1
            else:
                hc[i][j] = 1
for i in range(h):
    for j in range(w - 1, -1, -1):
        if s[i][j] == ".":
            if j < w - 1:
                if hc[i][j] < hc[i][j + 1]:
                    hc[i][j] = hc[i][j + 1]
wc = [[0] * h for i in range(w)]
for i in range(w):
    for j in range(h):
        if s[j][i] == ".":
            if j > 0:
                wc[i][j] = wc[i][j - 1] + 1
            else:
                wc[i][j] = 1
for i in range(w):
    for j in range(h - 1, -1, -1):
        if s[j][i] == ".":
            if j < h - 1:
                if wc[i][j] < wc[i][j + 1]:
                    wc[i][j] = wc[i][j + 1]
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, hc[i][j] + wc[j][i] - 1)
print(ans)
### BUGGY CODE ###

import numpy as np


n = int(input())
h = list(map(int, input().split()))
ans = 0
for i in range(n-1):
    num = min(n, i + h[i] + 1)
    s = np.array(h[num:])
    diff = h[i]
    u = np.arange(len(s)) + 1
    s -= u
    t = np.count_nonzero(s)
    ans += len(s) - t
print(ans)


### FIXED CODE ###

from collections import Counter

n = int(input())
h = list(map(int, input().split()))
a = []
b = []
for i in range(n):
    a.append(i + h[i])
    b.append(i - h[i])

x = Counter(a)
y = Counter(b)

z = set(a)
ans = 0
for i in z:
    ans += x[i] * y[i]

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

mod = 7+10**9

def expo(x):
  ans = 1
  n = mod-2
  while n>0:
    if n%2 == 1:
      ans = ans*x%mod
    x = x*x%mod
    n = n >> 1
  return ans

def combi(n,k):
  return (fac[n]*(expo_fac[k])%mod)*expo_fac[n-k]%mod

n,k = map(int,input().split())
fac = [1]+[0]*n
for i in range(1,n+1):
  fac[i] = fac[i-1]*i%mod

expo_fac = [expo(fac[i]) for i in range(n+1)]

ans = 0
for i in range(min(n,k+1)):
  ans = (ans + combi(n,i)*combi(n-1,i)%mod)%mod
print(ans)

### FIXED CODE ###

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

mod = 10**9 + 7
l = 10**7
fac = [1]*l
facr = [1]*l

for i in range(l-1):
    fac[i+1] = fac[i]*(i+1)%mod
facr[l-1] = pow(fac[l-1],mod - 2,mod)
for i in range(1,l)[::-1]:
    facr[i-1] = facr[i]*i%mod

def combi(N,K):
    return fac[N]*facr[N-K]%mod*facr[K]%mod

ans = 1
for i in range(1,min(n,k+1)):
    ans += combi(n,i)*combi(n-1,i)%mod
    ans %= mod
print(ans)
### BUGGY CODE ###

N = int(input())
a = [int(x) for x in input().split(" ")]
sum = 0
pow = 0
while any(a):
    one = 0
    for i in range(N):
        if a[i] & 1:
            one += 1
        a[i] >>= 1
    sum += one * (N - one) * 2 ** pow
    sum %= (10 ** 9 + 7)
    pow += 1
print(sum)

### FIXED CODE ###

import numpy as np

N = int(input())
a = np.array([int(x) for x in input().split(" ")], np.int64)
sum = 0
pow = 0
while any(a):
    one = np.count_nonzero(a & 1)
    sum += one * (N - one) * 2 ** pow
    sum %= (10 ** 9 + 7)
    pow += 1
    a >>= 1
print(sum)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
#from decimal import *

def dijkstra(E, start): #最短経路のみ
	N_d = len(E)
	dist = [INF] * N_d
	dist[start] = 0
	q = [(0, start)]
	while q:
		dist_v, v = heappop(q)
		if dist[v] != dist_v:
			continue
		for u, dist_vu in E[v]:
			dist_u  = dist_v + dist_vu
			if dist[u] > dist_u:
				dist[u] = dist_u
				heappush(q, (dist_u, u))
	return dist	

N, X, Y = MAP()

graph = [[[1, 1]]] + [[[i-1, 1], [i+1, 1]] for i in range(1, N-1)] + [[[N-2, 1]]]
graph[X-1].append([Y-1, 1])
graph[Y-1].append([X-1, 1]) 

dic = defaultdict(int)

ans = 0
for i in range(N):
	ans = dijkstra(graph, i)
	for key in ans:
		dic[key] += 1

for i in range(1, N):
	print(dic[i]//2)


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
#from decimal import *

def dijkstra(E, start): #最短経路のみ
	N_d = len(E)
	dist = [INF] * N_d
	dist[start] = 0
	q = [(0, start)]
	while q:
		dist_v, v = heappop(q)
		if dist[v] != dist_v:
			continue
		for u, dist_vu in E[v]:
			dist_u  = dist_v + dist_vu
			if dist[u] > dist_u:
				dist[u] = dist_u
				heappush(q, (dist_u, u))
	return dist	

N, X, Y = MAP()

graph = [[[1, 1]]] + [[[i-1, 1], [i+1, 1]] for i in range(1, N-1)] + [[[N-2, 1]]]
graph[X-1].append([Y-1, 1])
graph[Y-1].append([X-1, 1]) 

dic = defaultdict(int)

ans = 0
for i in range(N):
	ans = dijkstra(graph, i)
	for key in ans:
		dic[key] += 1

for i in range(1, N):
	print(dic[i]//2)
### BUGGY CODE ###

from numba import jit
N = int(input())
ans = 0

@jit
def num(n):
  num = 0
  for i in range(1,int(n**0.5)+1):
    if n%i==0:
      num+=1
      if n!=i**2:
        num+=1
  return num
  
for n in range(1,N):
  ans+=num(n)

print(ans)

### FIXED CODE ###

N = int(input())
ans = 0

for n in range(1,N):
  ans+=(N-1)//n

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

N,K = map(int,input().split())
h = list(map(int,input().split()))
if N <= K+1:
    print(abs(h[0]-h[-1]))
else:
    dp = [0]*N
    for i in range(K+1):
        dp[i] = abs(h[i]-h[0])
    for i in range(K+1,N):
        m = float("inf")
        for j in range(1,K+1):
            m = min(m,dp[i-j]+abs(h[i]-h[i-j]))
        dp[i] = m
    print(dp[-1])

### FIXED CODE ###

import numpy as np

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = np.zeros(N, dtype=int)
h = np.array(h)
 
for i in range(1, N):
    start = max(0, i-K)
    dp[i] = min(dp[start:i] + np.abs(h[i] - h[start:i]))
 
print(dp[-1])
### BUGGY CODE ###

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

def resolve():
    import numpy as np
    n=int(input())
    l=[list(map(int,input().split())) for i in range(n)]
    import itertools
    ans=0
    p=list(itertools.permutations(l))
    for x in p:
        z = list(x)
        for y in range(n-1):
            a=np.array(z[y])
            b=np.array(z[y+1])
            ans+=np.linalg.norm(a-b)
    print(ans/len(list(p)))
resolve()

### FIXED CODE ###

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

def resolve():
    n=int(input())
    l=[list(map(int,input().split())) for i in range(n)]
    import itertools
    ans=0
    p=list(itertools.permutations(l))
    for x in p:
        z = list(x)
        for y in range(n-1):
            ans+=((z[y][0]-z[y+1][0])**2+(z[y][1]-z[y+1][1])**2)**0.5
    print(ans/len(list(p)))
resolve()
### BUGGY CODE ###

from collections import defaultdict

N = int(input())
S = [str(input()) for _ in range(N)]

d = defaultdict(int)
for key in S:
    d[key] += 1
    
hoge = []

for key in d.keys():
  if d[key] == max(d.values()):
    hoge.append(key)

hoge.sort()
for i in range(len(hoge)):
	print(hoge[i])

### FIXED CODE ###

from collections import defaultdict

N = int(input())
S = [str(input()) for _ in range(N)]

d = defaultdict(int)
for key in S:
    d[key] += 1
    
dl = sorted(d.items(), key=lambda x: x[0], reverse=False)
Max = max(d.values())

for i in range(len(dl)):
  if dl[i][1] == Max:
    print(dl[i][0])
### BUGGY CODE ###

N_M = [int(x.strip()) for x in input().split()]
price_maxnum_list = [[int(i) for i in input().split()] for i in range(0, N_M [0])]
price_list = [i[0] for i in price_maxnum_list]
maxnum_list = [i[1] for i in price_maxnum_list]
if len(set(price_list)) ==1:
    print(price_list[0]*N_M[1])
else:
    total = 0
    nokori = N_M[1]
    while nokori > 0:
        ind = price_list.index(min(price_list))
        total += min(price_list) * min(maxnum_list[ind], nokori)
        nokori -= min(maxnum_list[ind], nokori)
        price_list.pop(ind)
        maxnum_list.pop(ind)
    print(total)

### FIXED CODE ###

N_M = [int(x.strip()) for x in input().split()]
price_l = [[int(i) for i in input().split()] for i in range(0, N_M[0])]
price_l.sort(key=lambda x: x[0])
total = 0
remain = N_M[1]
while remain > 0:
    if len(price_l)<1:
        break
    price_n = price_l.pop(0)
    total += price_n[0] * min(price_n[1], remain)
    remain -= min(price_n[1], remain)
print(total)
### BUGGY CODE ###

n = int(input())

power = 1
for i in range(1,n+1):
    power *= i

print(power%(10**9+7))

### FIXED CODE ###

import math
n = int(input())

power = math.factorial(n)
print(power%(10**9+7))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
M = 10**9+7
n = int(input())
l = list(map(int,input().split()))
x = max(l)
s = bin(x)
u = len(s)-2
o = [0]*u
z = [0]*u
for i in l:
    x = bin(i)
    x = x[2:]
    a = list(x)
    d = u - len(a)
    a = (["0"] * d) + a
    j = 0
    while(j < len(o)):
        if a[j] == "1":
            o[j] = o[j]+1

        else:
            z[j] = z[j]+1

        j = j+1


o = o[::-1]
z = z[::-1]
cnt = 0
for j in range(len(o)):
    cnt = (cnt+((o[j]*z[j]*(2**j))%M))%M


print(cnt)

### FIXED CODE ###

def readinput():
    n=int(input())
    l=list(map(int,input().split()))
    return n,l

def main(n,a):
    MOD=10**9+7
    hist=[0]*61
    bs=[]
    for i in range(n):
        # s=list(reversed(bin(a[i])[2:]))
        # for j in range(len(s)):
        #     if s[j]=='1':
        #         hist[j]+=1
        # bs.append(s)

        s=bin(a[i])[2:]
        for j in range(len(s)):
            if s[j]=='1':
                hist[len(s)-j-1]+=1
        # j=0
        # ai=a[i]
        # while ai>0:
        #     if ai&1==1:
        #         hist[j]+=1
        #     ai = ai >> 1
        #     j+=1


    #print(bs)
    #print(hist)
    #print(hist)
    sum=0
    # for i in range(n-1):
    #     s=bs[i]
    #     b=1
    #     for j in range(len(s)):
    #         if s[j]=='0':
    #             sum=(sum+hist[j]*b)%MOD
    #         else:
    #             sum=(sum+( n-i-hist[j] )*b)%MOD
    #             hist[j]-=1
    #         b*=2
    #     for j in range(len(s),61):
    #         sum=(sum+hist[j]*b)%MOD
    #         b*=2
    b=1
    for j in range(61):
        sum=(sum+( hist[j]*(n-hist[j])*b )%MOD )%MOD
        b*=2

    return sum

if __name__=='__main__':
    n,l=readinput()
    ans=main(n,l)
    print(ans)
### BUGGY CODE ###

import sys
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
from collections import deque 

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

INF = 1001001001

# ---------------------------------------



n, k = inpl()
p = [0] + inpl()
c = [0] + inpl()

ans = - INF

for i in range(1, n + 1):
    cycle_cnt = 0
    cycle_sum = 0
    v = i

    while True:
        v = p[v]
        cycle_cnt += 1
        cycle_sum += c[v]
        if v == i: break
    
    cnt = 0
    path = 0

    while True:
        v = p[v]
        cnt += 1
        path += c[v]

        if cnt > k: break

        num = (k - cnt) // cycle_cnt
        score = path + max(0, cycle_sum) * num
        ans = max(ans, score)

        if v == i: break

print(ans)


### FIXED CODE ###

import sys
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
from collections import deque 

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

INF = 1001001001

# ---------------------------------------



n, k = inpl()
p = [0] + inpl()
c = [0] + inpl()

ans = - INF

for i in range(1, n + 1):
    cycle_cnt = 0
    cycle_sum = 0
    v = i

    while True:
        v = p[v]
        cycle_cnt += 1
        cycle_sum += c[v]
        if v == i: break
    
    cnt = 0
    path = 0

    while True:
        v = p[v]
        cnt += 1
        path += c[v]

        if cnt > k: break

        num = (k - cnt) // cycle_cnt
        score = path + max(0, cycle_sum) * num
        ans = max(ans, score)

        if v == i: break

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

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

if d_l[0] != 0 or d_l.count(0) != 1:
    ans = 0
else:
    ans = 1

d_l.sort()
d_l = d_l[1:]
count_l = [1,]

for i in range(1,n):
    count_l.append(d_l.count(i))
    d_l = d_l[count_l[i]:]
    ans = (ans*(count_l[i-1]**count_l[i]))%998244353
    if d_l == [] or ans == 0:
        break

print(ans)

### FIXED CODE ###

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

count_dict = {}
for i in range(n):
    count_dict[i] = 0
for val in d_l:
    count_dict[val] += 1

if d_l[0] != 0 or count_dict[0] != 1:
    ans = 0
else:
    ans = 1

for i in range(1,n):
    ans = (ans*(count_dict[i-1]**count_dict[i])) %998244353
    if ans == 0:
        break

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

n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
ma=max(A)
import heapq
BB=[]
Chk=[False]*n
for i in range(n):
  if A[i]==B[i]:
    Chk[i]=True
for i in range(n):
  BB.append([-B[i],i])
heapq.heapify(BB)
ans=0
while BB:
  b,ind=heapq.heappop(BB)
  if Chk[ind]:
    continue
  else:
    if ind==0:
      d=B[-1]+B[1]
    elif ind==n-1:
      d=B[-2]+B[0]
    else:
      d=B[ind-1]+B[ind+1]
    if d>=-b:
      break
    else:
      b_next=max(d,A[ind])
      ans+=(-b-b_next-1)//d+1
      b+=d*((-b-b_next-1)//d+1)
      B[ind]=-b
      if b>0:
        break
      elif A[ind]==-b:
        Chk[ind]=True
      else:
        heapq.heappush(BB,[b,ind])
  
print(-1 if BB else ans)


### FIXED CODE ###

n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

from heapq import heappop, heappush
push = lambda x,i: heappush(BB,(-x,i))
BB=[]

for i,b in enumerate(B):
  push(b,i)

ans=0
while BB:
  b,ind=heappop(BB)
  b,ai=-b,A[ind]
  if b<ai:
    ans=-1
    break
  d=B[(ind-1)%n]+B[(ind+1)%n]
  dd=(b-ai)//d
  if dd==0:
    if b==ai:
      continue
    ans=-1
    break
  ans+=dd
  B[ind]-=d*dd
  push(b-d*dd,ind)
  
print(ans)
### BUGGY CODE ###

import numpy as np

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

def imos(A):
    B = np.zeros_like(A)
    for i,x in enumerate(A):
        a = max(0, i-x)
        b= min(i+x, N-1)
        B[a] += 1
        if b+1 <= N-1:
            B[b+1] -= 1
    B = np.cumsum(B)
    return B

for i in range(K):
    if i >= 50:
        break
    A = imos(A)
print(*A)

### FIXED CODE ###

import numpy as np
from numba import njit

N, K = map(int, input().split())
A = np.array((list(map(int, input().split()))), dtype=np.int64)

@njit
def imos(A):
    B = np.zeros(N, dtype=np.int64)
    for i,x in enumerate(A):
        a = max(0, i-x)
        b = min(i+x, N-1)
        B[a] += 1
        if b+1 <= N-1:
            B[b+1] -= 1
    B = np.cumsum(B)
    return B

for i in range(K):
    if i >= 50:
        break
    A = imos(A)
print(*A)
### BUGGY CODE ###

s = input()
K = int(input())
n = len(s)
A =[]
import bisect
for i in range(n):
    for j in range(i+1,n+1):
        sub = s[i:j]  
        if sub not in A:
            x = bisect.bisect_left(A,sub)
            A.insert(x,sub)
print(A[K-1])

### FIXED CODE ###

s = input()
K = int(input())
n = len(s)
A =[]
import bisect
for i in range(n):
    for j in range(1,K+1):
        sub = s[i:i+j]  
        if sub not in A:
            x = bisect.bisect_left(A,sub)
            A.insert(x,sub)
            if len(A) > K:
                A.pop(K)

print(A[K-1])
### BUGGY CODE ###

s = input()
n = len(s)
#RLはフリップの関係にある、[RL]以外のマスの移動を考える
cost_map = [1]*n
ans=0
while True:
    new_map=cost_map.copy()
    for i in range(n):
        if cost_map[i]>0:
            if s[i]=='R':
                new_map[i+1]+=cost_map[i]
                new_map[i]-=cost_map[i]
            if s[i]=='L':
                new_map[i-1]+=cost_map[i]
                new_map[i]-=cost_map[i]
    new2_map = new_map.copy()
    for i in range(n):
        if new_map[i]>0:
            if s[i]=='R':
                new2_map[i+1]+=new_map[i]
                new2_map[i]-=new_map[i]
            if s[i]=='L':
                new2_map[i-1]+=new_map[i]
                new2_map[i]-=new_map[i]        

    ans+=1
    if cost_map==new2_map:
        if ans%2==0:
            print(' '.join(map(str,new_map)))
        else:
            print(' '.join(map(str,new2_map)))
        break
    cost_map=new_map

### FIXED CODE ###

s = input()
n = len(s)

#RRLRL=(R2L),(RL)
#ランレングス圧縮でRLを圧縮し、数の偶奇で分配する
#n<=10**5なので、10**5移動させた後の値でも求められる
v=[]
def RLE(s,v):
    for i in range(len(s)):
        if len(v)==0 or v[-1][0]!=s[i]:
            v.append([s[i],1])
        else:
            v[-1][1]+=1
    return v
rle_li = RLE(s,v)

string_li = [0]*n
for i in range(1,n):
    if s[i-1]=='R' and s[i]=='L':
        x = rle_li.pop(0)[1]
        y = rle_li.pop(0)[1]
        if x==1 and y==1:
            string_li[i-1]=1
            string_li[i]=1
        else:
            if y%2==0:
                string_li[i-1]+=y//2
                string_li[i]+=y//2
            else:
                string_li[i-1]+=y//2
                string_li[i]+=y//2+1
            if x%2==0:
                string_li[i-1]+=x//2
                string_li[i]+=x//2
            else:
                string_li[i-1]+=x//2+1
                string_li[i]+=x//2
print(' '.join(map(str,string_li)))