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

from collections import defaultdict

class Solution:
    def main(self):
        N = int(input())
        A = []
        for i in range(N):
            a = list(map(lambda x: int(x)-1, input().split())) + [-1]
            A.append(a)

        hashmap = defaultdict(set)
        for i in range(N):
            hashmap[A[i][0]].add(i)

        # print(hashmap)

        cnt = 0
        old_cnt = 0
        checklist = set(range(N))

        for day in range(1, N*(N-1)+1):
            cands = set()
            for i in checklist:
                if i in hashmap and A[i][0] in hashmap[i]:
                    if i < A[i][0]:
                        cands.add((i, A[i][0]))
                    else:
                        cands.add((A[i][0], i))

            for x, y in cands:
                # print(x, y)
                hashmap[y].remove(x)
                hashmap[x].remove(y)
                hashmap[A[x][1]].add(x)
                hashmap[A[y][1]].add(y)
                A[x].pop(0)
                A[y].pop(0)
                cnt += 1

            if cnt == N*(N-1)//2:
                print(day)
                break
            elif cnt == old_cnt:
                print(-1)
                break
            else:
                old_cnt = cnt
                checklist = set().union(*cands)
                # print(cands)
                # print(checklist)


if __name__ == '__main__':
    Solution().main()


### FIXED CODE ###

from collections import defaultdict

class Solution:
    def main(self):
        N = int(input())
        A = []
        for i in range(N):
            a = list(map(lambda x: int(x)-1, input().split())) + [-1]
            A.append(a)

        hashmap = defaultdict(set)
        for i in range(N):
            hashmap[A[i][0]].add(i)

        # print(hashmap)

        cnt = 0
        old_cnt = 0
        checklist = set(range(N))

        for day in range(1, N*(N-1)+1):
            cands = set()
            for i in checklist:
                if i in hashmap and A[i][0] in hashmap[i]:
                    if i < A[i][0]:
                        cands.add((i, A[i][0]))
                    else:
                        cands.add((A[i][0], i))

            for x, y in cands:
                # print(x, y)
                hashmap[y].remove(x)
                hashmap[x].remove(y)
                hashmap[A[x][1]].add(x)
                hashmap[A[y][1]].add(y)
                A[x].pop(0)
                A[y].pop(0)
                cnt += 1

            if cnt == N*(N-1)//2:
                print(day)
                break
            elif cnt == old_cnt:
                print(-1)
                break
            else:
                old_cnt = cnt
                checklist = set().union(*cands)
                # print(cands)
                # print(checklist)


if __name__ == '__main__':
    Solution().main()
### BUGGY CODE ###

from itertools import groupby
from math import ceil

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

block = [sum(1 for _ in it) for k, it in groupby(s)]
if s[0] != '1':
    block.insert(0, 0)

res = 0
for i in range(0, len(block), 2):
    res = max(sum(block[i:i+2*k+1]), res)
    if i+2*k+1 > n:
        break
print(res)


### FIXED CODE ###

from itertools import groupby
from math import ceil

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

block = [sum(1 for _ in it) for k, it in groupby(s)]
if s[0] != '1':
    block.insert(0, 0)

m = len(block)
left, right = 0, 2*k
res = val = sum(block[left:right-1])
while right <= m:
    val += block[right-1] if right == m else block[right-1] + block[right]
    res = max(res, val)
    val -= block[left] + block[left+1]
    left += 2
    right += 2
print(res)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N, M, P = map(int, input().split())
    Edges = [list(map(int, input().split())) for _ in range(M)]
    INF = 10**18

    graph1 = [[] for _ in range(N+1)]
    graph2 = [[] for _ in range(N+1)]
    for a, b, c in Edges:
        graph1[a].append(b)
        graph2[b].append(a)

    checked1 = [False]*(N+1)
    checked1[1] = True
    q = [1]
    while q:
        qq = []
        for p in q:
            for np in graph1[p]:
                if not checked1[np]:
                    checked1[np] = True
                    qq.append(np)
        q = qq
    
    checked2 = [False]*(N+1)
    checked2[N] = True
    q = [N]
    while q:
        qq = []
        for p in q:
            for np in graph2[p]:
                if not checked2[np]:
                    checked2[np] = True
                    qq.append(np)
        q = qq
    
    Canuse = [False]*(N+1)
    for i in range(1, N+1):
        if checked1[i] and checked2[i]:
            Canuse[i] = True



    D = [INF for _ in range(N+1)]
    D[1] = 0
    for i in range(2*N+100):
        update = False
        for a, b, c in Edges:
            if not Canuse[a] or not Canuse[b]: continue
            if D[b] > D[a] + P - c:
                D[b] = D[a] + P - c
                update = True


    if update:
        print(-1)
    else:
        print(max(-D[N], 0))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, M, P = map(int, input().split())
    Edges = [list(map(int, input().split())) for _ in range(M)]
    INF = 10**18

    graph1 = [[] for _ in range(N+1)]
    graph2 = [[] for _ in range(N+1)]
    for a, b, c in Edges:
        graph1[a].append(b)
        graph2[b].append(a)

    checked1 = [False]*(N+1)
    checked1[1] = True
    q = [1]
    while q:
        qq = []
        for p in q:
            for np in graph1[p]:
                if not checked1[np]:
                    checked1[np] = True
                    qq.append(np)
        q = qq
    
    checked2 = [False]*(N+1)
    checked2[N] = True
    q = [N]
    while q:
        qq = []
        for p in q:
            for np in graph2[p]:
                if not checked2[np]:
                    checked2[np] = True
                    qq.append(np)
        q = qq
    
    Canuse = [False]*(N+1)
    for i in range(1, N+1):
        if checked1[i] and checked2[i]:
            Canuse[i] = True



    D = [INF for _ in range(N+1)]
    D[1] = 0
    for i in range(2*N+100):
        update = False
        for a, b, c in Edges:
            if not Canuse[a] or not Canuse[b]: continue
            if D[b] > D[a] + P - c:
                D[b] = D[a] + P - c
                update = True


    if update:
        print(-1)
    else:
        print(max(-D[N], 0))

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

"""
各山のgrundy数がわかればよい

基本的にループする
"""

N = int(input())

ans = 0

for i in range(N):

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

    while True:

        if A % K == 0:
            ans ^= A // K
            break

        elif A == K-1:
            ans ^= 0
            break

        else:
            A = A - A // K - 1

if ans == 0:
    print ("Aoki")
else:
    print ("Takahashi")


### FIXED CODE ###

"""
各山のgrundy数がわかればよい

基本的にループする
"""

N = int(input())

ans = 0

for i in range(N):

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

    

    while True:

        if A % K == 0:
            ans ^= A // K
            break

        elif A == K-1:
            ans ^= 0
            break

        else:

            if A // K != (A - A//K -1) // K:
                A = A - A // K - 1
            else:
                A -= (A - (A // K) * K) // (A // K+1) * (A//K+1)

    

if ans == 0:
    print ("Aoki")
else:
    print ("Takahashi")
### BUGGY CODE ###

n = int(input())
d = list(map(int, input().split()))
a = 1
flag = False
for i in range(n):
  a *= d[i]
if a > 10**18:
  print(-1)
else:
  print(a)

### FIXED CODE ###

n = int(input())
d = list(map(int, input().split()))
c_nega = 0
flag = False
for i in range(n):
  if d[i] == 0:
    flag = True
    break

if flag:
  print(0)
else:
  a = 1
  for i in range(n):
    a *= d[i]
    if a > 10**18:
      flag = True
      break
  if flag:
    print(-1)
  else:
    print(a)
### BUGGY CODE ###

import numpy as np
import fractions 
#from functools import reduce
import functools

MOD = 10**9+7


def main():
    N = int(input())
    A = list(map(int, input().split()))

    def lcm(x, y):
        return x * y // fractions.gcd(x, y)
        
    
    x = functools.reduce(lcm, A, 1)
        
    b = sum(x//a%MOD for a in A)
    print(b%MOD)
if __name__== "__main__":
    main()


### FIXED CODE ###

import fractions 
#from functools import reduce
import functools

MOD = 10**9+7


def main():
    # N = int(input())
    # A = list(map(int, input().split()))
    N, *A = map(int, open(0).read().split())
            
    x = 1
    for a in A:
        x *= a //  fractions.gcd(x, a)
        
    b = sum(x//a for a in A)
    print(b%MOD)
    
if __name__== "__main__":
    main()
### BUGGY CODE ###

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

max_num = int(m/n)
ans = -1
for i in reversed(range(max_num + 1)):
  if(m % i == 0):
    ans = i
    break

print(ans)

### FIXED CODE ###

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

max_num = int(m/n)
ans = -1
for i in reversed(range(max_num + 1)):
  if(m % i == 0):
    ans = i
    break

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

import collections

N = int(input())
texts = []
for i in range(N):
    texts.append((input()))
    
counters = []
count = 0
for i in range(N):
    for j in range(0,i-1):
        if collections.Counter(texts[j]) == collections.Counter(texts[i]):
            count += 1
    else:
        continue
print(count)

### FIXED CODE ###

N = int(input())
texts = []
for i in range(N):
    texts.append((input()))

import collections
counters = []
count = 0
for text in texts:
    text_list = list(text)
    text_list.sort()
    text = "".join(text_list) 
    c = collections.Counter(text)
    counters.append(c)



ccccc = []
anss = []
for ccc in counters:
    ccc = str(ccc)
    ccccc.append(ccc)
    

dd = collections.Counter(ccccc)
for v in dd.values():
    ans = v * (v-1) / 2
    anss.append(ans)
    
print(int(sum(anss)))
### BUGGY CODE ###

n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
ans=0
for i in range(l[0][0],l[0][1]+1):
    if all([i in range(l[k][0],l[k][1]+1) for k in range(1,m)]):
        ans+=1
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
a=0
z=10**5
for i in range(m):
    a=max(a,l[i][0])
    z=min(z,l[i][1])
if a<=z:
    print(z-a+1)
else:
    print(0)
### BUGGY CODE ###

n,k,q = map(int,input().split())
import numpy as np
p_list = np.zeros(n) +  k

for i in range(q):
    a_i = int(input())
    p_list = p_list-1
    p_list[a_i-1] += 1
    

for i in range(n):
    if p_list[i] <= 0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

n,k,q = map(int,input().split())
p_list =[k-q]*n

for i in range(q):
    a_i = int(input())
    p_list[a_i-1] += 1  

for i in range(n):
    if p_list[i] <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

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

# A内の整数値を用いて作られる最小の整数を求めよ、という問題


def gcd(a, b):
    """
    自然数a, b の最大公約数を求める
    """
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


ans = float('inf')
for i in range(N):
    for j in range(i, N):
        ans = min(ans, gcd(A[i], A[j]))


print(ans)

### FIXED CODE ###

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

# A内の整数値を用いて作られる最小の整数を求めよ、という問題


def gcd(a, b):
    """
    自然数a, b の最大公約数を求める
    """
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


ans = gcd(A[0], A[1])
for i in range(1, N):
    ans = min(ans, gcd(ans, A[i]))


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

A, B, C, D, E, F = map(int, input().split())

density = 0
s_water = 0
sugar = 0
for a in range(31):
    for b in range(31):
        for c in range(101):
            for d in range(101):
                w = (100*A)*a + (100*B)*b
                s = C*c + D*d
                if w == 0:
                    continue
                if w + s > F:
                    continue
                if w/100 * E >= s:
                    tmp = 100*s / (w + s)
                    if tmp > density:
                        density = tmp
                        s_water = w + s
                        sugar = s
print(s_water, sugar)

### FIXED CODE ###

A, B, C, D, E, F = map(int, input().split())

density = -1
s_water = -1
sugar = -1
for a in range(31):
    for b in range(31):
        for c in range(101):
            for d in range(101):
                w = (100*A)*a + (100*B)*b
                s = C*c + D*d
                if w == 0:
                    continue
                if w + s > F:
                    continue
                if w/100 * E >= s:
                    tmp = 100*s / (w + s)
                    if tmp > density:
                        density = tmp
                        s_water = max(w + s, 100*A)
                        sugar = s
print(s_water, sugar)
### BUGGY CODE ###

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

score = 1
for i in range(k):
  score *= arr[i]

s = 0

for i in range(k, n):
  tmp = score * arr[i] // arr[s]
  if tmp > score:
    print("Yes")
  else:
    print("No")
  score = tmp
  s += 1

### FIXED CODE ###

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

s = 0

for i in range(k, n):
  before = arr[s]
  after = arr[i]
  if after > before:
    print("Yes")
  else:
    print("No")
  s += 1
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(N-1):
    s = sum(A[i+1:])
    ans += A[i]*s 
print(ans % (10**9+7))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
s = sum(A[1:])
for i in range(N-1):
    ans += A[i]*s 
    s = s - A[i+1]
print(ans % (10**9+7))
### BUGGY CODE ###

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

def gcd_array(A):
    n = len(A)
    s = A[0]
    for i in range(1,n):
        s = gcd(s,A[i])
    return s

if __name__ == "__main__":
    N = int(input())
    B = list(map(int,input().split()))
    max = 0
    for i in range(N):
        A = [i for i in B]
        A.pop(i)
        d = gcd_array(A)
        if max <= d:
            max = d
    print(max)

### FIXED CODE ###

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

def gcd_array(A):
    n = len(A)
    s = A[0]
    i = 1
    Down = [0]
    while(i < n):
        t = gcd(s,A[i])
        if t < s:
            Down.append(i)
        s = t
        i += 1
    return s,Down

if __name__ == "__main__":
    N = int(input())
    B = list(map(int,input().split()))
    max = 0
    d,Down = gcd_array(B)
    C = [i//d for i in B]
    c = C[0]
    K = 1
    for j in Down:
        A = [i for i in C]
        c = A.pop(j)
        l = gcd_array(A)[0]
        if K < l:
            K = l
    print(K * d)
### BUGGY CODE ###

import math
import numpy as np
 
N, K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))

A_n = np.array(A)
F_n = np.array(F)
A_sort = np.sort(A_n)
F_sort = np.sort(F_n)[::-1]
 
for j in range(K):
    A_sort.sort()

    np_list = A_sort*F_sort
    max_index = np_list.argmax()
    if max(A_sort) == 0:
        break
    else:
        A_sort[max_index] -= 1
    
ans = 0
A_sort.sort()
print(max(A_sort*F_sort))


### FIXED CODE ###

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

A_sort = sorted(A)
F_sort = sorted(F,reverse=True)

l = -1
r = 0
for i in range(N):
    r = max(r,A_sort[i]*F_sort[i])

def judge(c):
    s = 0
    for i in range(N):
        s += max(A_sort[i]-c//F_sort[i],0)
    return s <= K

while r-l > 1:
    c = (l+r)//2
    if judge(c):
        r = c
    else:
        l = c
print(r)
### BUGGY CODE ###

import math
import heapq
 
n, m = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x:x*(-1), A))
for i in range(m):
    heapq.heapify(A)
    min = (-1)*((-1)*(heapq.heappop(A))//2)
    heapq.heappush(A, min)
 
 
print(int(sum(A))*(-1))

### FIXED CODE ###

import math
import heapq

n, m = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x:x*(-1), A))
heapq.heapify(A)
for i in range(m):
    min = (-1)*((-1)*(heapq.heappop(A))//2)
    heapq.heappush(A, min)


print(int(sum(A))*(-1))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import collections
import fractions
from fractions import Fraction
from collections import defaultdict
import math

n=int(input())
a= [list(map(int, input().split())) for i in range(n)]
b=defaultdict(int)
c=defaultdict(int)
b0=0
c0=0
mod=1000000007
ans=1
cnt=0
for i,j in a:
    if i!=0 and j!=0:
        x=i
        y=j
        i //= math.gcd(x, y)
        j //= math.gcd(x, y)
        b[Fraction(i,j)]+=1
        c[Fraction(j,i)]+=1
    elif i==0 and j!=0:
        b0+=1
    elif i!=0 and j==0:
        c0+=1
    else:
        cnt+=1
w=[]
if c0!=0 or b0!=0:
    ans*=pow(2,c0+b0)-((pow(2,c0,mod)-1)*(pow(2,b0,mod)-1))


for k,v in b.items():
    if c[-k]!=0:
        ans*=(pow(2,c[-k]+v,mod)-(pow(2,c[-k],mod)-1)*(pow(2,v,mod)-1))
        w.append((pow(2,c[-k]+v,mod)-(pow(2,c[-k],mod)-1)*(pow(2,v,mod)-1)))
        ans%=mod
    else:
        ans*=pow(2,v,mod)
        ans%=mod

w=collections.Counter(w)
w=list(w.most_common())

for i,j in w:
    for k in range(j//2):
        ans*=pow(i,mod-2,mod)
ans+=cnt-1
print(int(ans%mod))

### FIXED CODE ###

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

n=int(input())
a= [list(map(int, input().split())) for i in range(n)]
b=defaultdict(int)
c=defaultdict(int)
b0=0
c0=0
mod=1000000007
ans=1
cnt=0
for i,j in a:
    if i!=0 and j!=0:
        x=i
        y=j
        i //= math.gcd(x, y)
        j //= math.gcd(x, y)
        i=abs(i)
        j=abs(j)
        if x*y>0:
            b[(i,j,0)]+=1
            c[(j,i,1)]+=1
        else:
            b[(i,j,1)]+=1
            c[(j,i,0)]+=1

    elif i==0 and j!=0:
        b0+=1
    elif i!=0 and j==0:
        c0+=1
    else:
        cnt+=1
w=[]
if c0!=0 or b0!=0:
    ans*=pow(2,c0+b0)-((pow(2,c0,mod)-1)*(pow(2,b0,mod)-1))

for k,v in b.items():
    if c[k]!=0:
        ans*=(pow(2,c[k]+v,mod)-(pow(2,c[k],mod)-1)*(pow(2,v,mod)-1))
        w.append((pow(2,c[k]+v,mod)-(pow(2,c[k],mod)-1)*(pow(2,v,mod)-1)))
        ans%=mod
    else:
        ans*=pow(2,v,mod)
        ans%=mod

w=collections.Counter(w)
w=list(w.most_common())
for i,j in w:
    for k in range(j//2):
        ans*=pow(i,mod-2,mod)
ans+=cnt-1
print(int(ans%mod))
### BUGGY CODE ###

n,m=map(int,input().split())
L=[list(map(int,input().split()))for _ in range(m)]
N=[1]*n
for l,r in L:N[:l-1]=[0]*(l-1);N[r:]=[0]*(n-r)
print(sum(N))

### FIXED CODE ###

n, m = map(int, input().split())
L = [0]*m
R = [0]*m
for i in range(m): 
    *I, = map(int, input().split())
    L[i] = I[0]
    R[i] = I[1]
print(max(min(R)-max(L)+1, 0))
### BUGGY CODE ###

n = int(input())
s = str(input())
r = [i + 1 for i in range(n) if s[i] == 'R']
g = [i + 1 for i in range(n) if s[i] == 'G']
b = [i + 1 for i in range(n) if s[i] == 'B']

def count(x,y,z):
    c = 0
    for i in x:
        for j in y:
            if i > j: continue 
            for k in z:
                if j > k: continue 
                if j - i != k - j:
                    c += 1
    return c

ans = 0
ans += count(r,g,b)
ans += count(r,b,g)
ans += count(b,r,g)
ans += count(b,g,r)
ans += count(g,r,b)
ans += count(g,b,r)

print(ans)

### FIXED CODE ###


def main():
    n = int(input())
    s = str(input())
    cnt = 0
    r = s.count('R')
    g = s.count('G')
    b = s.count('B')

    for i in range(n):
        for j in range(i,n):
            if i == j:
                continue
            k = 2 * j - i
            if k > len(s) - 1:
                continue
            if s[i] == s[j] or s[j] == s[k] or s[k] == s[i]:
                continue

            cnt +=1

    all = r * g * b
    print(all - cnt) 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N, M = map(int, input().split())
X = list(map(int, input().split()))

X.sort()
X_subtraction = []
for i in range(len(X)-1):
    X_subtraction.append(X[i+1] - X[i])

for _ in range(N-1):
    try:
        X_subtraction.remove(max(X_subtraction))
    except:
        break

print(sum(X_subtraction))

### FIXED CODE ###

N, M = map(int, input().split())
X = list(map(int, input().split()))

X.sort()
X_subtraction = []
for i in range(len(X)-1):
    X_subtraction.append(X[i+1] - X[i])

X_subtraction.sort(reverse=True)
del X_subtraction[0:N-1]

print(sum(X_subtraction))
### BUGGY CODE ###

S = input().strip()
n = len(S)

A=[]
n = 0
for i in range(len(S)):
  if int(S[i:])%2019!=0:
    A.append(int(S[i:])%2019)
  else:
    n += 1

from collections import Counter
cnt = Counter(A)
for v in cnt.values():
    n += v*(v-1)/2
print(int(n))


### FIXED CODE ###

S = input()[::-1]
n = len(S)

cnt = [0] * 2019
cnt[0] = 1
m = 0
d = 1
for i in S:
  m += int(i) * d
  m %= 2019
  cnt[m] += 1
  d *= 10
  d %= 2019

ans=0
for i in cnt:
  ans += int(i*(i-1)/2)
print(ans)
### BUGGY CODE ###

x, k, d = map(int, input().split())

ans = float("inf")
for i in range(k + 1):
    ans = min(ans, abs(x + (d * i) - (d * (k - i))))
print(ans)    

### FIXED CODE ###

x, k, d = map(int, input().split())
x = abs(x)

a = x // d
b = x % d
if a > k:
    ans = x - (k * d)
else:
    if (k - a) % 2 == 0:
        ans = b
    else:
        ans = d - b
print(ans)
### BUGGY CODE ###

from heapq import*
h,w=map(int,input().split())
grid=[["#"]*(w+2)]+[list("#"+input()+"#") for x in range(h)]+[["#"]*(w+2)]

stack=[]
for y in range(1,h+1):
    for x in range(1,w+1):
        if grid[y][x]=="#":
            grid[y][x]=0
            heappush(stack,(y,x))

for i in range(h*w):
    tmp=[]
    for my,mx in stack:
        for y,x in ([0,1],[1,0],[-1,0],[0,-1]):
            if grid[my+y][mx+x]==".":
                grid[my+y][mx+x]=i+1
                heappush(tmp,[my+y,mx+x])
    if all(all(j!="." for j in i)for i in grid):
        print(max(max(i[1:-1])for i in grid[1:-1]))
        exit()
    stack=tmp


### FIXED CODE ###

from heapq import*
h,w=map(int,input().split())
grid=[["#"]*(w+2)]+[list("#"+input()+"#")for x in range(h)]+[["#"]*(w+2)]

stack=[]
for y in range(1,h+1):
    for x in range(1,w+1):
        if grid[y][x]=="#":
            grid[y][x]=0
            stack.append((y,x))

for i in range(h*w):
    tmp=[]
    for my,mx in stack:
        for y,x in ([0,1],[1,0],[-1,0],[0,-1]):
            if grid[my+y][mx+x]==".":
                grid[my+y][mx+x]=i+1
                tmp.append([my+y,mx+x])
    stack=tmp
    if len(tmp)==0:
        print(i)
        break