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

import sys

sys.setrecursionlimit(100000)

N = int(input())
palette = [1]
colors = [None] * N
ends = [None] * N
edges = {}

for edge in range(1,N):
    ends[edge] = [int(n) for n in input().split()]

for edge in range(1,N):
    a, b = ends[edge]
    if a not in edges:
        edges[a] = [edge]
    else:
        edges[a].append(edge)
    if b not in edges:
        edges[b] = [edge]
    else:
        edges[b].append(edge)


def color_edges(parent, root):
    current_palette = palette[:]
    if parent > 0:
        del current_palette[current_palette.index(colors[parent])]
    for edge in edges[root]:
        if colors[edge]:
            continue
        if len(current_palette) > 0:
            colors[edge] = current_palette[0]
            del current_palette[0]
        else:
            color = len(palette) + 1
            palette.append(color)
            colors[edge] = color
    for edge in edges[root]:
        if edge == parent:
            continue
        a, b = ends[edge]
        if a == root:
            color_edges(edge, b)
        else:
            color_edges(edge, a)

max_edges = 1
root = 1
for node in range(1,N+1):
    if len(edges[node]) > max_edges:
        max_edges = len(edges[node])
        root = node

color_edges(0, root)

print(len(palette))
for edge in range(1,N):
    print(colors[edge])


### FIXED CODE ###

import sys

sys.setrecursionlimit(100000)

N = int(input())
palette = 1
colors = {}
ends = {}
edges = {}

for edge in range(1,N):
    ends[edge] = [int(n) for n in input().split()]

    a, b = ends[edge]
    if a not in edges:
        edges[a] = [edge]
    else:
        edges[a].append(edge)
    if b not in edges:
        edges[b] = [edge]
    else:
        edges[b].append(edge)


def color_edges(parent, root):
    ng = {}
    global palette
    if parent > 0:
        ng[colors[parent]] = True
    for edge in edges[root]:
        if edge in colors:
            color = colors[edge]
        elif palette - len(ng) > 0:
            color = 1
            while color in ng:
                color += 1
            colors[edge] = color
        else:
            palette += 1
            color = palette
            colors[edge] = color

        ng[color] = True
    for edge in edges[root]:
        if edge == parent:
            continue
        a, b = ends[edge]
        if a == root:
            color_edges(edge, b)
        else:
            color_edges(edge, a)

max_edges = 1
root = 1
for node in range(1,N+1):
    if len(edges[node]) > max_edges:
        max_edges = len(edges[node])
        root = node

color_edges(0, root)

print(palette)
for edge in range(1,N):
    print(colors[edge])
### BUGGY CODE ###

from fractions import gcd
n,m=map(int,input().split())
ans=1
for i in range(m//n+1):
  if gcd(m-i*(n-1),i)==i:
    ans=i
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
def divisors(n):
  div=[]
  for i in range(1,int(n**0.5)+1):
    if n%i==0:
      div.append(i)
      if not i==n//i:
        div.append(n//i)
  div=sorted(div)[::-1]
  return div
ans=1
for i in divisors(m):
  if m-i*(n-1)>0:
    ans=i
    break
print(ans)
### BUGGY CODE ###

import numpy as np
N, M =map(int, input().split())
A = np.array(list(map(int, input().split())))
#print(A)
for i in range(M):
    A = np.sort(A)[::-1]
    A[0] = A[0]/2
    #print(A)

A = np.trunc(A)
print(int(A.sum()))


### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)  # aを優先度付きキューに

for _ in range(m):
    tmp_min = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-tmp_min//2))  # 計算誤差の関係で-1を2回かけてます
print(-sum(a))
### BUGGY CODE ###

from math import factorial

n = int(input())
a = list(map(int, input().split()))
a.sort()
max_a = max(a)
a.pop()
ans = -1
comb = 0
for a_i in a:
    if a_i >= max_a//2:
        comb = max(comb, (factorial(max_a) // factorial(max_a - a_i) * factorial(a_i)))
        ans = a_i
        break

for a_i in a[::-1]:
    if a_i <= max_a//2:
        if comb < factorial(max_a) // factorial(max_a - a_i) * factorial(a_i):
            ans = a_i
        break
print(max_a, ans)

        


### FIXED CODE ###

from math import factorial

n = int(input())
a = list(map(int, input().split()))
max_a = max(a)
a.remove(max_a)
dis = float('inf')
ans = 0
for a_i in a:
    if abs(a_i - max_a//2) < dis:
        ans = a_i
        dis = abs(a_i - max_a//2)

print(max_a, ans)
### BUGGY CODE ###

from math import sqrt
def main():
    n, p = map(int, input().split())
    if n == 1:
        print(p)
    else:
        ans = 1
        cnt = 0
        while p % 2 == 0:
            p //= 2
            cnt += 1
        if cnt >= n:
            ans *= 2**(cnt//n)
        x = 3
        while x**n <= p:
            cnt = 0
            while p % x == 0:
                p //= x
                cnt += 1
            if cnt >= n:
                ans *= x**(cnt//n)
            x += 1
        print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from math import log
def main():
    n, p = map(int, input().split())
    if n == 1:
        print(p)
    else:
        ans = 1
        if n > int(log(p, 2))+2:
            print("1")
            sys.exit()
        if p % (2**n) == 0:
            while p % (2**n) == 0:
                ans *= 2
                p //= (2**n)
        for i in range(3, 10**6+1, 2):
            while p % (i**n) == 0:
                ans *= i
                p //= (i**n)
        print(ans)

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

from collections import deque

s = input()
q = int(input())
Q = [list(map(str, input().split())) for i in range(q)]

ans = deque(s)

reverse_num = 0
for i in range(q):
  if int(Q[i][0]) == 1:
    reverse_num += 1
  else:
    if int(Q[i][1]) == 1:
      if reverse_num % 2 == 0:
        ans.appendleft(Q[i][2])
      else:
        ans.append(Q[i][2])
    else:
      if reverse_num % 2 != 0:
        ans.appendleft(Q[i][2])
      else:
        ans.append(Q[i][2])

res = ''
for i in range(len(ans)):
  res += ans[i]
if reverse_num % 2 == 0:   
  print(res)
else:
  print(res[::-1])


### FIXED CODE ###

from collections import deque

s = input()
q = int(input())
Q = [list(map(str, input().split())) for i in range(q)]

ans = deque(s)

reverse_num = 0
for i in range(q):
  if int(Q[i][0]) == 1:
    reverse_num += 1
  else:
    if int(Q[i][1]) == 1:
      if reverse_num % 2 == 0:
        ans.appendleft(Q[i][2])
      else:
        ans.append(Q[i][2])
    else:
      if reverse_num % 2 != 0:
        ans.appendleft(Q[i][2])
      else:
        ans.append(Q[i][2])

res = ''
if reverse_num % 2 == 0: 
  for i in range(len(ans)):
    res += ans.popleft()
  print(res)
else:
  for i in range(len(ans)):
    res += ans.pop()
  print(res)
### BUGGY CODE ###

N=int(input())
count=0
s=[sorted(input()) for i in range(N)]
s=sorted(s)
for t in range(N):
    for i in range(t+1,N):
        if s[i]==s[t]:
            count+=1
print(count)

### FIXED CODE ###

N=int(input())
S=[''.join(sorted((input()))) for i in range(N)]
P={}
for i in range(N):
    if S[i] in P:
        P[S[i]]+=1
    else:
        P[S[i]]=0
for i in P.keys():
    if P[i]>=2:
        P[i]=P[i]*(P[i]+1)/2
print(int(sum(P.values())))
### BUGGY CODE ###

N=int(input())
A=sorted(map(int,input().split()))[::-1]
ans=A[0]
while True:
    M=A[0]
    m=A[1]
    del A[0]
    if m==0:break
    A.append(M%m)
    A=sorted(A)[::-1]
    ans=min(ans,A[0])
print(ans)

### FIXED CODE ###

import functools,fractions
n=input()
a=list(map(int,input().split()))
print(functools.reduce(fractions.gcd,a))
### BUGGY CODE ###

import bisect
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
count = 0
# ソートして
for c in C:
  under_c = bisect.bisect_left(B, c)
  for b in B[:under_c]:
    under_b = bisect.bisect_left(A, b)
    count += under_b
print(count)


### FIXED CODE ###

import bisect
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
count = 0
# ソートして
for b in B:
  upeer_b = N - bisect.bisect_right(C, b)
  downer_b = bisect.bisect_left(A, b)
  count += upeer_b * downer_b

# for c in C:
#   under_c = bisect.bisect_left(B, c)
#   for b in B[:under_c]:
#     under_b = bisect.bisect_left(A, b)
#     count += under_b

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

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

def get_cd(x1,x2):
    cd=[]
    for i in range(1,min(x1,x2)+1):
        if x1%i==0 and x2%i==0:
            cd.append(i)
    return cd

cd_AB=get_cd(A,B)

for j in range (0,len(cd_AB)-1):
    for k in range(j+1,len(cd_AB)):
        if(cd_AB[k]!=0):
            if(len(get_cd(cd_AB[j],cd_AB[k]))>1):
                cd_AB[k]=0

print(len(cd_AB)-cd_AB.count(0))

### FIXED CODE ###

def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        count=0
        while n % b == 0:
            n //= b
            count+=1
            if(count==1):
                fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

A,B=map(int,input().split())
g=gcd(A,B)
if(g==1):
    print("1")
else:
    print(len(factorize(g))+1)
### BUGGY CODE ###


N = int(input())

cnt_dict = {}

for i in range(N):
    s_list = list(input())
    s_list.sort()
    s_str = "".join(s_list)
    if s_str not in cnt_dict.keys():
        cnt_dict[s_str] = 1
        continue
    cnt_dict[s_str] += 1

import itertools
comb = itertools.combinations

total = 0
for key in cnt_dict.keys():
    cnt = cnt_dict[key]
    if cnt < 2:
        continue
    total += len(list(comb(range(cnt), 2)))

print(total)




### FIXED CODE ###


N = int(input())

cnt_dict = {}

for i in range(N):
    s_list = list(input())
    s_list.sort()
    s_str = "".join(s_list)
    if s_str not in cnt_dict.keys():
        cnt_dict[s_str] = 1
        continue
    cnt_dict[s_str] += 1

import itertools
comb = itertools.combinations

total = 0
for key in cnt_dict.keys():
    cnt = cnt_dict[key]
    if cnt < 2:
        continue
    total += cnt * (cnt - 1) // 2

print(total)
### BUGGY CODE ###

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

b_low=-1*(10**20)
b_high=10**20
b_low_d=sum([abs(a[i]-(b_low+2+i)) for i in range(n)])-sum([abs(a[i]-(b_low+1+i)) for i in range(n)])
b_high_d=sum([abs(a[i]-(b_high+2+i)) for i in range(n)])-sum([abs(a[i]-(b_high+1+i)) for i in range(n)])

while b_high-b_low>10:
  b_tmp=(b_low+b_high)//2
  b_tmp_d=sum([abs(a[i]-(b_tmp+2+i)) for i in range(n)])-sum([abs(a[i]-(b_tmp+1+i)) for i in range(n)])
  if b_tmp_d>0:
    b_high=b_tmp
  else:
    b_low=b_tmp

ans=10**20
for j in range(b_low,b_high):
  ans=min(ans,sum([abs(a[i]-(j+2+i)) for i in range(n)]))

print(ans)

### FIXED CODE ###

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

b_low=-1*(10**12)
b_high=10**12
b_low_d=sum([abs(a[i]-(b_low+2+i)) for i in range(n)])-sum([abs(a[i]-(b_low+1+i)) for i in range(n)])
b_high_d=sum([abs(a[i]-(b_high+2+i)) for i in range(n)])-sum([abs(a[i]-(b_high+1+i)) for i in range(n)])

while b_high-b_low>10:
  b_tmp=(b_low+b_high)//2
  b_tmp_d=sum([abs(a[i]-(b_tmp+2+i)) for i in range(n)])-sum([abs(a[i]-(b_tmp+1+i)) for i in range(n)])
  if b_tmp_d>0:
    b_high=b_tmp
  else:
    b_low=b_tmp

ans=10**20
for j in range(b_low,b_high):
  ans=min(ans,sum([abs(a[i]-(j+2+i)) for i in range(n)]))

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

import math
X = int(input())
default = 100
year = 1
while True:
    default = default + math.floor(default * (1 / default))
    if default == X:
        print(year)
        break
    year += 1



### FIXED CODE ###

import math

X = int(input())
year = 0
yokin = 100

while yokin < X:
    year += 1
    yokin += math.floor(yokin * 0.01)
print(year)
### BUGGY CODE ###

n, m = map(int, input().split())
a=[]
b=[]
for i in range(n):
    ab=list(map(int, input().split()))
    a.append(ab[0])
    b.append(ab[1])

total_cost = 0
while(1):
    new_shop = a.index(min(a))
    new_drinks = b[new_shop]
    if m-new_drinks>0:
        total_cost = total_cost + a[new_shop] * b[new_shop]
        m=m-new_drinks
        a.pop(new_shop)
        b.pop(new_shop)
    else:
        total_cost = total_cost + a[new_shop] * m
        break
print(total_cost)

### FIXED CODE ###

from numpy import argsort
n, m = map(int, input().split())
a=[]
b=[]
for i in range(n):
    ab=list(map(int, input().split()))
    a.append(ab[0])
    b.append(ab[1])

total_cost = 0
order = argsort(a)
for i in range(len(a)):
    new_shop = order[i]
    new_drinks = b[new_shop]
    if m-new_drinks>0:
        total_cost = total_cost + a[new_shop] * b[new_shop]
        m=m-new_drinks
    else:
        total_cost = total_cost + a[new_shop] * m
        break
print(total_cost)
### BUGGY CODE ###

def cc(c):
    if c<2: return 0
    return int(c*(c-1)/2)

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

acnt=dict()
for elem in set(a):
    acnt[elem] = a.count(elem)

memo = [-1]*2000010
for ak in a:
    if memo[ak] != -1:
        print(memo[ak])
        continue

    cnt=0
    for k,kcnt in acnt.items():
        if ak==k:
            cnt+= cc(kcnt-1)
        else:
            cnt+=cc(kcnt)
    memo[ak]=cnt

    print(cnt)




### FIXED CODE ###

from collections import Counter
n=int(input())
a=[int(A) for A in input().split()]

cnt=Counter(a)
s=sum([c*(c-1)//2 for c in cnt.values()])

for k in a:
    print(s-(cnt[k]-1))
### BUGGY CODE ###

# coding: utf-8

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

while k>0:
    if h:
        h.remove(max(h))
        k-=1
    elif not h:
        break

if h:
    print(sum(h))
elif not h:
    print(0)

### FIXED CODE ###

# coding: utf-8

import sys
input=sys.stdin.readline

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

if n<=k:
    print(0)
else:
    h.sort()
    print(sum(h[:len(h)-k]))
### BUGGY CODE ###

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

ppc = {}

def popcount(n):    
  if n in ppc:
    return ppc[n]  
  if n == 0:
    return 0
  b = bin(n).count('1')  
  tmp = n%b
  ppc[n] = popcount(tmp) + 1
  return ppc[n]

bit = int('0b'+x,0)
for i in range(n,0,-1):      
  print(popcount(bit ^ (1 << (i-1))))

### FIXED CODE ###

n = int(input())
X = input()

def goes_to_zero(n):
  cnt = 0
  while(n > 0):
    n %= bin(n).count('1')
    cnt += 1
  return cnt
  
c1 = X.count('1')
xint = int(X,2)
xtp = xint % (c1 + 1)
if (c1 - 1) == 0:  
  xtm = 0
else:
  xtm = xint % (c1 - 1)
  
for i in range(n)  :
  if X[i] == '0':
    print(goes_to_zero( (xtp + pow(2,n-1-i,(c1+1))) % (c1+1) ) + 1)
  else:
    if (c1-1) == 0:
      print(0)
    else:
      print(goes_to_zero( (xtm - pow(2,n-1-i,(c1-1)) ) % (c1-1) ) +1)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    A = []
    tmp = (0,)*(N+1)
    A.append(tmp)
    for i in range(N):
        tmp = (0,) + tuple(map(int, input().split()))
        A.append(tmp)
    B = [1]*(N+1)
    C = [[0]*N for i in range(N+1)]
    count = 0
    flag = 0
    while count < N*(N-1)//2 and flag == 0:
        flag = 1
        for i in range(1,N+1):
            if B[i] < N:
                j = A[i][B[i]]
                if A[j][B[j]] == i:
                    k = max(C[i][B[i]-1], C[j][B[j]-1]) + 1
                    C[i][B[i]] = k
                    C[j][B[j]] = k
                    B[i] +=  1
                    B[j] += 1
                    count += 1
                    flag = 0
                    
    #print(C)
    ans = 0
    for i in C:
        if i[-1] > ans:
            ans = i[-1]
    if ans == 0:
        print(-1)
    else:
        print(ans)
    
    
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    A = []
    tmp = (0,)*(N+1)
    A.append(tmp)
    for i in range(N):
        tmp = (0,) + tuple(map(int, input().split()))
        A.append(tmp)
    B = [1]*(N+1)
    C = [[0]*N for i in range(N+1)]
    count = 0
    flag = 0
    
    #1試合目
    Q = []
    nextQ = []
    for i in range(1,N+1):
        j = A[i][B[i]]
        if A[j][B[j]] == i:
            ii = min(i,j)
            jj = max(i,j)
            if not (ii,jj) in nextQ:
                nextQ.append((ii,jj))
    
    day = 0    
    while count < N*(N-1)//2 and len(nextQ) >= 1:
        day += 1
        Q = nextQ
        nextQ = []
        for T in Q:
            i = T[0]
            j = T[1]
            k = max(C[i][B[i]-1], C[j][B[j]-1]) + 1
            C[i][B[i]] = k
            C[j][B[j]] = k
            B[i] += 1
            B[j] += 1
            count += 1
            if B[i] < N:
                I = A[i][B[i]]
                if A[I][B[I]] == i:
                    ii = min(i,I)
                    jj = max(i,I)
                    if not (ii,jj) in nextQ:
                        nextQ.append((ii,jj))
            if B[j] < N:
                J = A[j][B[j]]
                if A[J][B[J]] == j:
                    ii = min(j,J)
                    jj = max(j,J)
                    if not (ii,jj) in nextQ:
                        nextQ.append((ii,jj))
            
                    
    #print(C)
    if count < N*(N-1)//2:
        print(-1)
    else:
        print(day)
    
    
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
B=[0]*n
j=0
for i in range(n):
    while b[i]>=c[j] and j<n-1:j+=1
    B[i]=n-j
ans=0
j=0
for i in range(n):
    while a[i]>=b[j] and j<n-1:j+=1
    if a[i]<b[j]:ans+=sum(B[j:])
print(ans)

### FIXED CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
B=[0]*n
j=0
for i in range(n):
    while b[i]>=c[j] and j<n-1:j+=1
    if b[i]<c[j]:B[i]=n-j
ans=0
s=sum(B)
j=0
for i in range(n):
    while a[i]>=b[j] and j<n-1:s-=B[j];j+=1
    if a[i]<b[j]:ans+=s
print(ans)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N = int(readline())
m = map(int,read().split())
AB = zip(m,m)
 
E=[[] for _ in range(N)]
for A,B in AB:
    E[A-1].append(B-1)
    E[B-1].append(A-1)
MOD=10**9+7

#dp=子ノードの数+1(自分)
dp=[1]*N

root=0
parent=[0]*N
order=[]
def dfs():
    parent[root]=root
    stack=[root]
    while stack:
        node=stack.pop()
        order.append(node)
        for ss in E[node]:
            if parent[node]!=ss:
                stack.append(ss)
                parent[ss]=node

def solve():
    ans=0
    inv2=pow(2,MOD-2,MOD)
    #p0=すべての部分木に黒頂点が1つも含まれない確率
    p0=pow(1<<(N-1),MOD-2,MOD)
    for i in reversed(order):
        if root!=i:
            dp[parent[i]]+=dp[i]
        p=0
        if len(E[i])>=2:
            #p0*(p1-1)=どれか1つの各部分木に黒頂点が1つ以上含まれる確率
            p1=1
            for s in E[i]:
                size=0
                if parent[i]!=s:
                    size=dp[s]
                elif i!=root:
                    size=N-dp[i]
                else:
                    continue
                p1+=(1<<size)-1
                p1%=MOD
            p=1-(p0*p1)
            p%=MOD
        ans+=p
        ans%=MOD
    #頂点iが白の確率
    ans=ans*inv2%MOD
    print(ans)

dfs()
solve()


### FIXED CODE ###

N=int(input())
E=[[] for _ in range(N)]
for _ in range(N-1):
    A,B=map(int,input().split())
    E[A-1].append(B-1)
    E[B-1].append(A-1)
MOD=10**9+7

#dp=子ノードの数+1(自分)
dp=[1]*N

root=0
parent=[0]*N
order=[]
def dfs():
    parent[root]=root
    stack=[root]
    while stack:
        node=stack.pop()
        order.append(node)
        for ss in E[node]:
            if parent[node]!=ss:
                stack.append(ss)
                parent[ss]=node

pow2=[1]*(N+1)
for i in range(1,len(pow2)):
    pow2[i]=pow2[i-1]*2%MOD

def solve():
    ans=0
    inv2=pow(2,MOD-2,MOD)
    #p0=すべての部分木に黒頂点が1つも含まれない確率
    p0=pow(pow2[N-1],MOD-2,MOD)
    for i in reversed(order):
        if root!=i:
            dp[parent[i]]+=dp[i]
        p=0
        if len(E[i])>=2:
            #p0*(p1-1)=どれか1つの各部分木に黒頂点が1つ以上含まれる確率
            p1=1
            for s in E[i]:
                size=0
                if parent[i]!=s:
                    size=dp[s]
                elif i!=root:
                    size=N-dp[i]
                else:
                    continue
                p1+=pow2[size]-1
            p=1-(p0*p1)
            p%=MOD
        ans+=p
        ans%=MOD
    #頂点iが白の確率
    ans=ans*inv2%MOD
    print(ans)

dfs()
solve()
### BUGGY CODE ###

import heapq

def solve():
  h,w = (int(i) for i in input().split())
  maze = ["0"*(w+2)]
  for i in range(h):
    maze.append("0"+input()+"0")
  maze.append("0"*(w+2))
  black = []
  count = 0
  visit = [[False]*(w+2) for _ in range(h+2)]
  for i in range(h+2):
    for j in range(w+2):
      if maze[i][j] == "#":
        heapq.heappush(black,(0,i,j)) #move,h,w

  d = [(1,0),(0,1),(-1,0),(0,-1)]
  ans = 0
  
  while count != h*w:
    move,y,x = heapq.heappop(black)
    #print(move,y,x)
    if visit[y][x]:
      continue
    else:
      visit[y][x] = True
      count += 1
      for dy,dx in d:
        ny,nx = y+dy,x+dx
        if visit[ny][nx]:
          continue
        elif maze[ny][nx] =="0" or maze[ny][nx] == "#":
          continue
        else:
          heapq.heappush(black,(move+1,ny,nx))
  print(move)
          

    
solve()

### FIXED CODE ###


from collections import deque
def solve():
  h,w = (int(i) for i in input().split())
  maze = ["0"*(w+2)]
  for i in range(h):
    maze.append("0"+input()+"0")
  maze.append("0"*(w+2))
  black = deque([])
  count = 0
  visit = [[False]*(w+2) for _ in range(h+2)]
  
  for i in range(h+2):
    for j in range(w+2):
      if maze[i][j] == "#":
        black.append((0,i,j)) #move,h,w

  d = [(0,1),(1,0),(-1,0),(0,-1)]
  ans = 0
  
  while count != h*w:
    move,y,x = black.popleft()
    #print(move,y,x)
    if visit[y][x]:
      continue
    else:
      visit[y][x] = True
      count += 1
      for dy,dx in d:
        ny,nx = y+dy,x+dx
        if visit[ny][nx]:
          continue
        elif maze[ny][nx] ==".":
          black.append((move+1,ny,nx))
  print(move)
          

    
solve()
### BUGGY CODE ###

import re
n = int(input())
s = input()
ans = 0
for i in range(1000):
    i = str(i).zfill(3)
    if re.search('{}.*{}.*{}'.format(i[0],i[1],i[2]), s):
        ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for i in range(1000):
    key = str(i).zfill(3)
    idx = 0
    target = key[idx]
    for ii in s:
        if target == ii:
            idx += 1
            if idx > 2:
                ans += 1
                break
            target = key[idx]
print(ans)
### BUGGY CODE ###

A, B = map(int, input().split())
ans = B
for i in range(A,B):
	ans = i ^ ans
print(ans)

### FIXED CODE ###

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

def test(A):
	if A % 2 == 1:
		if (A+1)/2 % 2 == 1:
			tmp_A = 1
		else:
			tmp_A = 0
	else:
		if A/2 % 2 == 1:
			tmp_A = 1 ^ A
		else:
			tmp_A = 0 ^ A
	return tmp_A

print(test(A-1)^test(B))
### BUGGY CODE ###

import numpy as np
N,M=map(int,input().split())
A=list([int(input()) for _ in range(M)])

mod=10**9+7

dp=np.zeros(N+1)
dp[0]=1
if 1 not in A:
    dp[1]=1
else:
    dp[1]=0

for i in range(2,N+1):
    if i in A:
        continue
    dp[i]=dp[i-1]+dp[i-2]
    dp[i]%=mod

print(int(dp[N]))

### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

print(dp[N])
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [0]*n
count = 0

for i in range(k):
  for j in range(n):
    for m in range(n):
      if a[m] >= abs(m-j):
        b[j] += 1
  a = b  
  b = [0]*n
print(*a)


### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[0]*n
c=[0]*n
cnt=0
while cnt<min(k,101):
  cnt+=1
  for i in range(n):
    b[max(0,i-a[i])]+=1
    if i+a[i]<n-1:
      b[i+a[i]+1]-=1
    c[0]=b[0]
  for j in range(n-1):
    c[j+1]=c[j]+b[j+1]
  a=c
  b=[0]*n
  c=[0]*n
print(*a)