Harryxun/stf_run huggingface dataset:
import time


def main():

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

    sum = [0] * (N + 100)

    for i in range(N+1):
        if S[i] == 'A' and S[i+1] == 'C': sum[i+1] = sum[i] + 1
        else: sum[i+1] = sum[i]

    for i in range(Q):
        l, r = map(int, input().split())
        print(sum[r-1] - sum[l-1])


if __name__ == '__main__':
    start = time.perf_counter()

    main()

    end = time.perf_counter()
    # print(end - start)


### FIXED CODE ###

import time


def main():

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

    sum = [0] * (N + 1)

    for i in range(1, N):
        if S[i-1] == 'A' and S[i] == 'C': sum[i] = sum[i-1] + 1
        else: sum[i] = sum[i-1]

    for i in range(Q):
        l, r = map(int, input().split())
        print(sum[r-1] - sum[l-1])


if __name__ == '__main__':
    start = time.perf_counter()

    main()

    end = time.perf_counter()
    # print(end - start)
S = input()
flag = 0
for i in range(N):
	if i%2 = 0 and (S[i] not in ['R', 'U', 'D']):
		flag = 1
	if i%2 = 1 and (S[i] not in ['L', 'U', 'D']):
		flag = 1
if flag == 0:
	print('Yes')
else:
	print('No')

### FIXED CODE ###

S = input()
flag = 0
for i in range(len(S)):
	if i%2 == 0 and (S[i] not in ['R', 'U', 'D']):
		flag = 1
	if i%2 == 1 and (S[i] not in ['L', 'U', 'D']):
		flag = 1
if flag == 0:
	print('Yes')
else:
	print('No')
n, m = list(map(int, input().split()))
A = list(map(int, input().split()))
sum = sum(A)
for a in A:
  if a * 4 * m < sum:
    cnt += 1
if cnt >= m:
  print("Yes")
else:
  print("No")
  

### FIXED CODE ###

n, m = list(map(int, input().split()))
A = list(map(int, input().split()))
sum = sum(A)
cnt = 0
for a in A:
  if a * 4 * m >= sum:
    cnt += 1
if cnt >= m:
  print("Yes")
else:
  print("No")
import sys
stdin=sys.stdin

ns=lambda:input().rstrip()
ni=lambda:int(input().rstrip())
nm=lambda:map(int,input().split())
nl=lambda:list(map(int,input().split()))

N,Q=nm()
AB=[nl() for i in range(N-1)]
PQ=[nl() for i in range(Q)]
root=[[] for i in range(N)]
N_val=[0]*N
ans_val=[0]*N
d=[0]*N

def dfs(x,d,s):
  for i in root[x]:
    if(d[i]==0):
      s+=N_val[i]
      ans_val[i]=s
      d[i]=1
      dfs(i,d,s)
      s-=N_val[i]
      

for i in range(N-1):
  root[AB[i][0]-1]+=[AB[i][1]-1]
  root[AB[i][1]-1]+=[AB[i][0]-1]
  
for i in range(Q):
  N_val[PQ[i][0]-1]+=PQ[i][1]

  
ans_val[0]=N_val[0]
d[0]=1
dfs(0,d,N_val[0])
print(*ans_val)

### FIXED CODE ###

import sys
from collections import deque
stdin=sys.stdin

ns=lambda:input().rstrip()
ni=lambda:int(input().rstrip())
nm=lambda:map(int,input().split())
nl=lambda:list(map(int,input().split()))

N,Q=nm()
AB=[nl() for i in range(N-1)]
PQ=[nl() for i in range(Q)]
root=[[] for i in range(N)]
N_val=[0]*N
ans_val=[0]*N
d=[0]*N

def bfs():
  que=deque([])
  que.append(0)
  while que:
    p=que.popleft()
    for i in root[p]:
       if(d[i]==0):
         ans_val[i]=ans_val[p]+N_val[i]
         que.append(i)
         d[i]=1
      
def dfs(x,d,s):
  for i in root[x]:
    if(d[i]==0):
      s+=N_val[i]
      ans_val[i]=s
      d[i]=1
      dfs(i,d,s)
      s-=N_val[i]
      

for i in range(N-1):
  root[AB[i][0]-1]+=[AB[i][1]-1]
  root[AB[i][1]-1]+=[AB[i][0]-1]
  
for i in range(Q):
  N_val[PQ[i][0]-1]+=PQ[i][1]

  
ans_val[0]=N_val[0]
d[0]=1
#dfs(0,d,N_val[0])
bfs()
print(*ans_val)
x, n = map(int, input().split())
if n == 0:
    print(x)
else:
    p = list(map(int, input().split()))

    p.sort()
    y = 0

    for i in range(n):
        if p[i] <= x:
            y = i
            if i != n-1 and x < p[i+1]:
                break 

    i = 0
    while 1 == 1:
        if x - i != p[y - i]:
            print(x - i)
            break
        if x + i != p[y + i]:
            print(x + i)
            break
        i = i + 1

### FIXED CODE ###

x, n = map(int, input().split())
if n == 0:
    print(x)
else:
    p = list(map(int, input().split()))

    p.sort()
    y = 0

    for i in range(n):
        if p[i] <= x:
            y = i
            if i != n-1 and x < p[i+1]:
                break 

    i = 0
    while 1 == 1:
        if y - i < 0:
            print(p[0] - 1)
            break
        elif x - i != p[y - i]:
            print(x - i)
            break
        if n <= y + i:
            print(p[n - 1] + 1)
            break
        elif x + i != p[y + i]:
            print(x + i)
            break
        i = i + 1
2
ip cc

### FIXED CODE ###

n = int(input())
s,t = map(str, input().split())
moji = ""

for i in range(n):
  moji += s[i] + t[i]

print(moji)
A = input()
s = 0
for i in range(0,2):
  if A[i]="1":
    s = s + 1
print(s)    

### FIXED CODE ###

A = input()
s = 0
for i in range(len(A)):
  if A[i]=="1":
    s = s + 1
print(s)
X, A, B = input().split()
if B <= A:
  print("delicious")
else:
  if B - A <= X:
    print("safe")
  else:
    print("dangerous")

### FIXED CODE ###

X, A, B = map(int, input().split())
if B <= A:
  print("delicious")
else:
  if B - A <= X:
    print("safe")
  else:
    print("dangerous")
n,a,b = map(int, input().split())
ans=b
tr = n*a
if tr < b
	ans=tr
print(ans)

### FIXED CODE ###

n,a,b = map(int, input().split())
ans=b
tr = n*a
if tr < b:
	ans=tr
print(ans)
while True:
    m, f, r = [int(i) for i in input().split()]

    if m == f ==r -1:
        break

    if m + f  <= 80:
        return 'A'

    if m + f <= 60 and m + f > 80:
        return 'B'

    if m + f <= 50 and m + f > 65:
        return 'C'

    if m + f <= 30 and m + f > 50:
        return 'D'

    if r <= 50:
        return 'C'

    else:
        return 'F'

### FIXED CODE ###

while True:
    m, f, r = [int(i) for i in input().split()]

    if m == f == r == -1:
        break

    total = m + f
    if m == -1 or f == -1 or total < 30:
        print('F')

    elif total < 50 and r < 50:
        print('D')

    elif total < 65:
        print('C')
        
    elif total < 80:
        print('B')

    else:
        print('A')
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
total1=0
total2=0
def pon(p):
  s=1
  for i in range(1,p+1):
  s*=i
  return s
x=1
y=1
for i in a:
  total1+=(i-1)*pon(n-x)
  x+=1
for i in b:
  total2+=(i-1)*pon(n-y)
  y+=1
print(abs(total1-total2))

### FIXED CODE ###

import itertools
n=int(input())
a=tuple(map(int,input().split()))
b=tuple(map(int,input().split()))
lst=[i for i in itertools.permutations(range(1,n+1))]
cnt=0
for i in lst:
  if a==i:
    a=cnt
  if b==i:
    b=cnt
  cnt+=1
print(abs(a-b))
v=int(input())
while v<=10
    v=v%10
if v=3:
    print("bon")
elif v%2==1:
    print("pon")
else:
    print("hon")

### FIXED CODE ###

v=int(input())

v=v%10
if v==3:
    print("bon")
elif v==0 or v==1 or v==6 or v==8:
    print("pon")
else:
    print("hon")
n = int(input())
s = input()

ans = 0

for i in range(n):
    if s[i] == 'A':
        if s[i+1] == 'B':
            if s[i+2] == 'C':
                ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()

ans = 0

for i in range(n-2):
    if s[i] == 'A':
        if s[i+1] == 'B':
            if s[i+2] == 'C':
                ans += 1
print(ans)
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    graph[x-1].append(y-1) # 有向グラフ

# メモ化再帰
dp = [0 for _ in range(100100)]
def rec(v):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for i in graph[v]:
        res = max(res, rec(i) + 1)
    dp[v] = res
    return res

for i in range(N):
    dp[i] = -1
res = 0
for v in range(N):
    res = max(res, rec(v))
print(res)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    graph[x-1].append(y-1) # 有向グラフ

# メモ化再帰
dp = [-1 for _ in range(100100)]
def rec(v):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for i in graph[v]:
        res = max(res, rec(i) + 1)
    dp[v] = res
    return res

res = 0
for v in range(N):
    res = max(res, rec(v))
print(res)
if N > 100000000:
    N /= 10000000
syou = int(N/K)
print(syou)
min_1 = int(N - syou*K + 0.5)
min_2 = -int(N - (syou+1)*K - 0.5)
print('{} {}'.format(min_1,min_2))
if min_1 < min_2:
    print(min_1)
else :
    print(min_2)


### FIXED CODE ###

N,K = map(int, input().split())
syou = N//K
min_1 = N - syou*K
min_2 = -(N - (syou+1)*K)
if min_1 < min_2:
    print(min_1)
else :
    print(min_2)
import functools as ft
#import math as ft


prime = 10**9+7

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

an.sort()


lcm_ = 1
for a in an :
    lcm_ = a*lcm_//ft.gcd(a,lcm_)
#    print(lcm_)
    
ans = 0
bn = [0]*n
for i, a in enumerate(an):
    t = lcm_//a
    ans += t 
    ans %= prime

print(ans)

### FIXED CODE ###


import fractions as fr
import functools as ft
#import math as fr


prime = 10**9+7

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

an.sort()


lcm_ = 1
for a in an :
    lcm_ = a*lcm_ // fr.gcd(a, lcm_)
#    print(lcm_)
    
#ans = 0
#for a in an:
#    ans += lcm_ // a
#    ans = ans % prime if ans >= prime else ans

ans = ft.reduce(lambda x,y: (x + lcm_//y), an ,0 )

print(ans%prime)
def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
            if p==n: return cnt
        cnt+=n-p
    return cnt

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
l,r=a[0]*2,a[-1]*2

while r-l>0:
    if r-l==1:
        md=l
        break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0
for i in range(n-1,-1,-1):
    while p<n and a[i]+a[p]<=md:
        p+=1
    cnt+=n-p
    ans+=a[i]*(n-p)*2

ans+=(m-cnt)*md

print(ans)

### FIXED CODE ###

import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2
md=(r+l)//2
while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
    except:
        b=1
        while True:
            b+=1

    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)
while True: 
(H, W) = [int(x) for x in input().split()]
if H == W == 0:
    break

for hc in range(H):
    print('#' * W)

print()

### FIXED CODE ###

while True:
    H,W = map(int, input().split())
    if W == H == 0:
        break;
    L="#"*W
    for i in range(H):
        print(L)
    print("")
import itertools
import math
N=int(input())
P=list(map,int,input().split())
Q=list(map,int,input().split())
L=list(map(list,list(itertools.permutations(list(i for i in range(1,N+1)),N))))
a=L.index(P)
b=L.index(Q)
print(abs(a-b))




### FIXED CODE ###

import itertools
import math
N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
L = list(map(list,list(itertools.permutations(list(i for i in range(1,N+1)),N))))
a = L.index(P)
b = L.index(Q)
print(abs(a-b))
import numpy as np
N = int(input())
x = [0]*N
u = [0]*N
for i in range(N):
    x[i], u[i]= map(input().split())
    
x_int = [float(j) for j in x]
u_replace = [1 if k =="JPY" else 380000.0 for k in u]

x_arr = np.array(x_int)
u_arr = np.array(u_replace).reshape(N, 1)

ans = np.dot(x_arr, u_arr)
print(ans)

### FIXED CODE ###

import numpy as np
N = int(input())
x = [0]*N
u = [0]*N
for i in range(N):
    x[i], u[i]= map(str, input().split())
    
x_int = [float(j) for j in x]
u_replace = [1 if k =="JPY" else 380000.0 for k in u]

x_arr = np.array(x_int)
u_arr = np.array(u_replace).reshape(N, 1)

ans = np.dot(x_arr, u_arr)
print(ans[0])
a, b = map(int, input().split())

if a*b%2 == 0:
  puts("Even")
else:
  puts("Odd")

### FIXED CODE ###

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

if a*b%2 == 0:
  print("Even")
else:
  print("Odd")
import math
N, K = map(int, input().split())

k = math.gcd(N, K)

if K == 1:
    print(0)
else:
    print(k)


### FIXED CODE ###

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

if N > K:
    N = N - K*(N//K)

if N==K:
    print(0)
else:
    print(min(N,K-N))
ok=True
a,b=map(int,input().split())
val=[]
for i in range(b):
    c,d=map(int,input().split())
    val.append([c,d])
val=sorted(val)
for i in range(b-1):
    if val[i][0]==val[i+1][0] and val[i][1]!=val[i+1][1]:
        ok=False
        print(-1)
        break
if ok:
    e=[0 for i in range(a)]
    strr=""
    for i in val:
        e[i[0]-1]=i[1]
    if e[0]==0:
        if e==[0]:
            print(0)
        for i in range(1,a):
            strr+=str(e[i])
        if set(strr)=={'0'}:
            print(-1)
        else:
            print(int(strr))
    else:
        for i in range(a):
            strr+=str(e[i])
        print(strr)

### FIXED CODE ###

ok=True
okay=True
a,b=map(int,input().split())
val=[]
for i in range(b):
    c,d=map(int,input().split())
    val.append([c,d])
    if c==1 and d==0:
        okay=False
val=sorted(val)
for i in range(b-1):
    if val[i][0]==val[i+1][0] and val[i][1]!=val[i+1][1]:
        ok=False
        print(-1)
        break
if ok:
    e=[0 for i in range(a)]
    strr=""
    for i in val:
        e[i[0]-1]=i[1]
    if e[0]==0:
        if e==[0]:
            print(0)
        else:
            if okay:
                for i in range(1,a):
                    strr+=str(e[i])
                strr="1"+strr
                print(strr)
            else:
                print(-1)
    else:
        for i in range(a):
            strr+=str(e[i])
        print(int(strr))
import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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



N, M =two_int()

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    
    temp=[0 for i in range(N)]
    for j in many_int():
        temp[N-j-1]=1
    treasures.append("0b"+"".join(list(map(str,temp))))

max_index=2**N
INF=10**15

dp=[INF for i in range(max_index)]
dp[0]=0

for i in range(max_index):
    for j in range(M):
        new_i = int(bin(treasures[j] | i),2)
        cost = dp[i] + key_list[j]
        dp[new_i] = min(dp[new_i], cost) 

goal_index=max_index-1
if dp[goal_index]!=INF:
    print(dp[goal_index])
else:
    print(-1)



### FIXED CODE ###

import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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


def main():
    N, M =two_int()

    key_list=[]
    treasures=[]
    check={}

    for i in range(M):
        mon,_ =two_int()
        temp = map(lambda x: 1<<(x-1), many_int())
        sums = sum(temp)
        
        if sums in check:
            if check[sums] > mon:
                check[sums]=mon
        else:
            check[sums]=mon
            
    for k,v in check.items():
        key_list.append(v)
        treasures.append(k)

    max_index=2**N
    INF=10**15

    dp=[INF for i in range(max_index)]
    dp[0]=0
    M=len(key_list)

    for i in range(max_index-1):
        for j in range(M):
            new_i = int(bin(treasures[j] | i),2)
            cost = dp[i] + key_list[j]
            dp[new_i] = min(dp[new_i], cost) 
        
    goal_index=max_index-1
    if dp[goal_index]!=INF:
        print(dp[goal_index])
    else:
        print(-1)

main()
a,b=map(int,ieput().split())
print((a+b)//2+(a+b)%2)

### FIXED CODE ###

a,b=map(int,input().split())
print((a+b)//2+(a+b)%2)
N, M = input().split()
for i in range(1, M+1):
    a, b = input().split()
for i in range(1, N+1):
    print(a.count("i")+b.count("i"))

### FIXED CODE ###

n, m = map(int, input().split())
a, b = [0]*m, [0]*m
for i in range(m):
    a[i], b[i] = map(int, input().split())
for j in range(1,n+1):
    print(a.count(j)+b.count(j))
N = int(input())
A=sorted(list(map(int,input().split())))
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
def gcdlist(lista):
    if len(lista) == 1:
        return lista[0]
    else:
        from functools import reduce
        return reduce(gcd,lista)
first = A.pop(0)
ans = []
second = A[0]
gcda = gcdlist(A[1:])
for i in range(first,second+1):
    ans.append(gcd(i,gcda))
print(max(ans))

### FIXED CODE ###

N = int(input())
A=sorted(list(map(int,input().split())))
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
ans = []
gcdlist = [A[0]]
for i in range(1,N):
    gcdlist.append(gcd(gcdlist[i-1],A[i]))
gcdlistr = [A[-1]]
for i in range(N-2,-1,-1):
    gcdlistr.append(gcd(gcdlistr[N-i-2],A[i]))
gcdlistr.reverse()
gcdlist.insert(0,0)
gcdlist.append(0)
gcdlistr.insert(0,0)
gcdlistr.append(0)
for i in range(N):
    ans.append(gcd(gcdlist[i],gcdlistr[i+2]))
print(max(ans))
a = int(input())
b = int(input())

if a >= 10 or b >= 10:
    print(-1)
else:
    print(a * b)


### FIXED CODE ###

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

if a >= 10 or b >= 10:
    print(-1)
else:
    print(a * b)
S=input()
Q=int(input())
ref=0
for i in range(Q):
    T=input().split()
    if T[0] == '2':
        if (T[1]=='1' and ref%2==0):
            S=T[2]+S
        elif (T[1]=='2' and ref%2==0):
            S=S+T[2]
        elif (T[1]=='1' and ref%2==1):
            S=S+T[2]
        elif (T[1]=='2' and ref%2==1):
            S=T[2]+S
    else:
        ref+=1
    print(S)
print(S if ref%2==0 else S[::-1])

### FIXED CODE ###

from collections import deque
S=deque(input())
Q=int(input())
ref=0
for i in range(Q):
    T=input().split()
    if T[0] == '2':
        if (T[1]=='1' and ref%2==0):
            S.appendleft(T[2])
        elif (T[1]=='2' and ref%2==0):
            S.append(T[2])
        elif (T[1]=='1' and ref%2==1):
            S.append(T[2])
        elif (T[1]=='2' and ref%2==1):
            S.appendleft(T[2])
    else:
        ref+=1
for i in range(len(S)):
    if ref%2==0:
        char=S.popleft()
        print(char,end='')
    else:
        char=S.pop()
        print(char,end='')
a,b,c=map(int, input().split())
if a>b:
 i=a
 a = b
 b = i
if b>c:
 i=b
 b=c
 c=b
if a>c
 i=a
 a=c
 c=i

str="{d} {e} {f}"
print(str.format(d=a, e=b, f=c)

### FIXED CODE ###

a,b,c=map(int, input().split())
if a>b:
 i=a
 a = b
 b = i
if b>c:
 i=b
 b=c
 c=i
if a>b:
 i=a
 a=b
 b=i

str="{d} {e} {f}"
print(str.format(d=a, e=b, f=c))
s = input()
ans=[]
for i in range(len(s)):
    if(s[i] == '0' or s[i] == '1'):
        ans.append(s[i])

    else:
        del ans[-1]

for i in range(len(ans)):
    print(ans[i], end ="")

### FIXED CODE ###

s = input()
ans=[]
for i in range(len(s)):
    if(s[i] == '0' or s[i] == '1'):
        ans.append(s[i])

    else:
        if(len(ans) != 0):
            del ans[-1]

for i in range(len(ans)):
    print(ans[i], end ="")
import math;print(math.factorial(int(input()))%(7+1e9))

### FIXED CODE ###

import math;print(math.factorial(int(input()))%int(7+1e9))
scores=[input() for _ in range(N)]
AC=WA=TLE=RE=0
for score in scores:
  if score == 'AC':
    AC += 1
  elif score == 'WA':
    WA += 1
  elif score == 'TLE':
    TLE += 1
  else:
    RE += 1
print('AC x ' + str(AC))
print('WA x ' + str(WA))
print('TLE x ' + str(TLE))
print('RE x ' + str(RE))

### FIXED CODE ###

N=int(input())
scores=[input() for _ in range(N)]
AC=WA=TLE=RE=0
for score in scores:
  if score == 'AC':
    AC += 1
  elif score == 'WA':
    WA += 1
  elif score == 'TLE':
    TLE += 1
  else:
    RE += 1
print('AC x ' + str(AC))
print('WA x ' + str(WA))
print('TLE x ' + str(TLE))
print('RE x ' + str(RE))
#貪欲に埋める
from collections import deque
h,w,k = map(int,input().split( ))

s = []
ichigo = []
for i in range(h):
    si = input()
    si+="."
    s.append(si)
    for j in range(w):
        if si[j]=="#":
            ichigo.append((i,j))

Nm = [[-1]*w for _ in range(h)]

tmp = 1
for ich in ichigo:
    Nm[ich[0]][ich[1]]=tmp
    tmp += 1
#print(Nm)
for ich in ichigo:
    Q = deque()
    Q.append(ich)
    #print(ich)
    now = Nm[ich[0]][ich[1]]
    while Q:
        b,c = Q.popleft()
        for i in range(c+1,w):
            if Nm[b][i]<0:
                Nm[b][i] = now
            else:
                i-=1
                break

        for j in range(c-1,-1,-1):
            if Nm[b][j]<0:
                Nm[b][j] = now
            else:
                j+=1##
                break
        for u in range(b+1,h):
            flag = True
            for t in range(j,i+1):
                if Nm[u][t]>=0:
                    flag = False
                    break
            if flag:
                for t in range(j,i+1):
                    Nm[u][t] = now
            else:
                break
        for u in range(b-1,-1,-1):
            flag = True
            for t in range(j,i+1):
                if Nm[u][t]>=0:
                    flag = False
                    break
            if flag:
                for t in range(j,i+1):
                    Nm[u][t] = now
            else:
                break
            
for i in range(h):
    print(*Nm[i])

### FIXED CODE ###

h,w,k = map(int, input().split())
s = []
Nm = [[0]*w for i in range(h)]
nm = 1
Q = []
empty =[]
for i in range(h):
    si = input()
    s.append(si)
    berry = False
    for j in range(w):
        if si[j]=="#":
            berry = True
            Nm[i][j]=nm
            nm+=1
            Q.append((i,j))
    if not berry:
        empty.append(i)

for i,j in Q:#横に伸ばす
    for t in range(j+1,w):
        if Nm[i][t]==0:
            Nm[i][t]=Nm[i][j]
        else:
            break
    for t in range(j-1,-1,-1):
        if Nm[i][t]==0:
            Nm[i][t]=Nm[i][j]
        else:
            break
if not empty:
    for i in range(h):
        print(*Nm[i])
    exit()
j=0###
if 0 in empty:#下から延ばす必要がある場合
    j = 0
    while empty[j]==j:
        j+=1
        if j<len(empty):
            continue
        else:
            break
    for t in range(j):
        for s in range(w):
            Nm[t][s] = Nm[j][s]
#print(j)
for i in empty[j:]:#縦下に伸ばす
    for j in range(w):
        Nm[i][j] = Nm[i-1][j]

for i in range(h):
    print(*Nm[i])
n,k=map(int,input()split())

while True:
  x=n
  n=abs(n-k)
  if x==n:
    break
  
  print n
  

### FIXED CODE ###

n,k=map(int,input().split())
a=n%k
b=k-a
print(min(a,b))
import math
n,k = map(int,input().split())

if k == 1:
	print(0)
else:
	print(math.gcd(n,k))



### FIXED CODE ###

from fractions import gcd
n,k = map(int,input().split())

def process(a,b):
	if a%b == 0:
		return 0
	a = a%b

	for i in range(100000):
		a = min(a,abs(a-b))
	return a
if n == 0:
	print(0)
elif n ==1:
	if k == 1:
		print(0)
	else:
		print(1)
elif k == 1:
	print(0)
else:
	print(process(n,k))
n = int(input())
lists = list(map(int,input().split())

ma = max(lists)
if sum(lists) - ma >ma:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

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

ma = max(lists)
if sum(lists) - ma >ma:
    print("Yes")
else:
    print("No")
r=int(input())
print(3.1416* r**2  3.1416* r*2)


### FIXED CODE ###

from math import pi
r = float(input())
a = pi*r*r
b = 2*pi*r
print(a,b)
n=int(input())
#s=list(input().split())
#s,t=list(input().split())
#a=list(map(int,input().split()))
#k,x=map(int,input().split())
p=list(input().split())
q=list(input().split())
p=[int(i) for i in p]
q=[int(i) for i in q]
import itertools
import math
fulllist=list(itertools.permutations([i for i in range(1,n+1)]))
for i in range(math.factorial(n)):
    if p==list(fulllist[i]):
        p_index=i+1
    elif q==list(fulllist[i]):
        q_index=i+1
print(abs(p_index-q_index))


### FIXED CODE ###

n=int(input())
#s=list(input().split())
#s,t=list(input().split())
#a=list(map(int,input().split()))
#k,x=map(int,input().split())
p=list(input().split())
q=list(input().split())
p=[int(i) for i in p]
q=[int(i) for i in q]
import itertools
import math
p_index,q_index=0,0
fulllist=list(itertools.permutations([i for i in range(1,n+1)]))
for i in range(math.factorial(n)):
    if p==list(fulllist[i]):
        p_index=i+1
    if q==list(fulllist[i]):
        q_index=i+1
print(abs(p_index-q_index))