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

import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class Comb:
    def __init__(self, N):
        F = [1] * (N + 1)
        for i in range(N):
            F[i + 1] = (i + 1) * F[i] % mod

        self.d_inv = {}
        self.d_comb = {}
        self.F = F

    def inv(self, a):
        if a not in self.d_inv:
            self.d_inv[a] = pow(a, mod - 2, mod)
        return self.d_inv[a]

    def comb(self, a, b):
        if (a, b) not in self.d_comb:
            self.d_comb[(a, b)] = (self.F[a] * self.inv(self.F[a - b]) * self.inv(self.F[b])) % mod
            self.d_comb[(a, a - b)] = self.d_comb[(a, b)]
        return self.d_comb[(a, b)] 


def main():
    K = int(input())
    S = input().strip()

    F25 = [1] * (K + 1)
    F26 = [1] * (K + 1)
    for i in range(K):
        F25[i + 1] = (25 * F25[i]) % mod
        F26[i + 1] = (26 * F26[i]) % mod

    comb = Comb(K + len(S) + 1)

    res = 0
    for k in range(K + 1):
        res += ((F25[K - k] * F26[k]) % mod * comb.comb(K - k + len(S) - 1, len(S) - 1)) % mod
        res %= mod
     
    print(res)


if __name__ == "__main__":
    main()



### FIXED CODE ###

import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class Comb:
    def __init__(self, N):
        F = [1] * (N + 1)
        for i in range(N):
            F[i + 1] = (i + 1) * F[i] % mod

        self.d_inv = {}
        self.d_comb = {}
        self.F = F

    def inv(self, a):
        if a not in self.d_inv:
            self.d_inv[a] = pow(a, mod - 2, mod)
        return self.d_inv[a]

    def comb(self, a, b):
        if (a, b) not in self.d_comb:
            self.d_comb[(a, b)] = (self.F[a] * self.inv(self.F[a - b]) * self.inv(self.F[b])) % mod
            self.d_comb[(a, a - b)] = self.d_comb[(a, b)]
        return self.d_comb[(a, b)] 


def main():
    K = int(input())
    S = input().strip()

    F25 = [1] * (K + 2)
    F26 = [1] * (K + 2)
    T = [1] * (K + 2)
    for i in range(K + 1):
        F25[i + 1] = (25 * F25[i]) % mod
        F26[i + 1] = (26 * F26[i]) % mod
        if i != 0:
            T[i] = pow(i, mod - 2, mod)

    r = 1
    res = 0
    for k in range(K + 1):
        res += ((F25[k] * F26[K - k]) % mod * r) % mod
        r *= (len(S) - 1 + k + 1)
        r %= mod
        r *= T[k + 1]
        r %= mod
        res %= mod
     
    print(res)


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

s = input()
n = len(s)

countdic = {}
mod = 2019

for i in range(1,n+1):
    num = int(s[n-i:n])
    remainder = num%mod
    if remainder in countdic:
        countdic[remainder] += 1
    if remainder not in countdic:
        countdic[remainder] = 1

ans = 0
for key in countdic:
    ans += countdic[key]*(countdic[key]-1)//2

if 0 in countdic:
    ans += countdic[0]

print(ans)


### FIXED CODE ###

s = list(map(int, list(input())))
n = len(s)

countdic = {}
mod = 2019

num = 0
d = 1
for i in range(1,n+1):
    num += s[n-i]*d
    num %= mod
    if num in countdic:
        countdic[num] += 1
    if num not in countdic:
        countdic[num] = 1
    d = (10*d)%mod

ans = 0
for key in countdic:
    ans += countdic[key]*(countdic[key]-1)//2

if 0 in countdic:
    ans += countdic[0]

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

N = int(input())

srt_n = str(N)
keta = len(srt_n)

ans = [0] * ( keta + 1 )
N_list = [0] * (keta+1)
ans_num = 0

for i in reversed(range(keta)):
    N_list[keta-i-1] = int(srt_n[i])

for i in range(keta+1):
    if N_list[i] == 5 and N_list[i+1] >= 5:
        ans[i] = 0
        N_list[i+1] += 1
        ans_num += 10 - N_list[i]
    elif N_list[i] > 5:
        ans[i] = 0
        N_list[i+1] += 1
        ans_num += 10 - N_list[i]
    else:
        ans[i] =  N_list[i]
        ans_num += N_list[i]
#print(ans)
print(ans_num)

### FIXED CODE ###

N = input()

keta = len(N)

#ans = [0] * ( keta + 1 )
N_list = [0] * (keta+1)
ans_num = 0

for i in reversed(range(keta)):
    N_list[keta-i-1] = int(N[i])

for i in range(keta+1):
    if N_list[i] == 5 and N_list[i+1] >= 5:
        #ans[i] = 0
        N_list[i+1] += 1
        ans_num += 10 - N_list[i]
    elif N_list[i] > 5:
        #ans[i] = 0
        N_list[i+1] += 1
        ans_num += 10 - N_list[i]
    else:
        #ans[i] =  N_list[i]
        ans_num += N_list[i]
#print(ans)
print(ans_num)
### BUGGY CODE ###

import sys
from itertools import product

def main():
    input = sys.stdin.readline
    X, Y, Z, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    A = sorted(A, key=lambda x: -x)
    B = sorted(B, key=lambda x: -x)
    C = sorted(C, key=lambda x: -x)

    n = 1
    while n^3 < K:
        n += 1

    A = A[:n]
    B = B[:n]
    C = C[:n]

    delicious = []
    for x in product(A, B, C):
        delicious.append(sum(x))

    delicious = sorted(delicious, key=lambda x: -x)
    for i in range(K):
        print(delicious[i])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from heapq import heappush, heappop

def main():
    input = sys.stdin.readline
    X, Y, Z, K = map(int, input().split())
    A = sorted(list(map(int, input().split())), key=lambda x: -x)
    B = sorted(list(map(int, input().split())), key=lambda x: -x)
    C = sorted(list(map(int, input().split())), key=lambda x: -x)

    deli = []
    heappush(deli, (-A[0]-B[0]-C[0], 0, 0, 0))
    pushed = set((0,0,0))
    for _ in range(K):
        d = heappop(deli)
        i, j, k = d[1], d[2], d[3]

        if i+1 < X and (i+1, j, k) not in pushed:
            heappush(deli, (-A[i+1]-B[j]-C[k], i+1, j, k))
            pushed.add((i+1, j, k))

        if j+1 < Y and (i, j+1, k) not in pushed:
            heappush(deli, (-A[i]-B[j+1]-C[k], i, j+1, k))
            pushed.add((i, j+1, k))

        if k+1 < Z and (i, j, k+1) not in pushed:
            heappush(deli, (-A[i]-B[j]-C[k+1], i, j, k+1))
            pushed.add((i, j, k+1))

        print(-d[0])


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

arr = [0 for i in range(2019)]
arr[0] = 1

s = input()
n = len(s)

for i in range(1,n+1):
    num = int(s[-i:])
    arr[num%2019] += 1

ans = 0
for m in arr:
    if m==0: continue
    ans += m*(m-1)//2

print(ans)



### FIXED CODE ###

arr = [0 for i in range(2019)]
arr[0] = 1

s = input()
n = len(s)

num = 0
for i,ele in enumerate(s[::-1]):
    num += int(ele) * pow(10, i, 2019)
    arr[num%2019] += 1


ans = 0
for m in arr:
    if m==0: continue
    ans += m*(m-1)//2

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

import numpy as np

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]

p = np.ones(N)*K
for i in range(Q):
  p -= 1
  p[A[i]-1] += 1
  
for i in range(N):
  if p[i] > 0: print('Yes')
  else: print('No')

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
 
p = [K-Q]*N
for i in range(Q):
  p[A[i]-1] += 1
  
for i in range(N):
  if p[i] > 0: print('Yes')
  else: print('No')
### BUGGY CODE ###

n,p = map(int,input().split())
s = list(input())
ans = 0

for i in range(n):
  for j in range(i,n):
    if int(''.join(s[i:j+1]))%p == 0:
      ans += 1
print(ans)

### FIXED CODE ###

n,p = map(int,input().split())
s = list(map(int,list(input())))
ans = 0
cnt = [0]*p
cnt[0] = 1

if p == 2:
  for i in range(n):
    if s[i] in [0,2,4,6,8] :
      ans += i + 1
elif p == 5:
  for i in range(n):
    if s[i] in [0,5]:
      ans += i + 1
else:
  sum = 0
  for i in range(n):
    sum = (sum+s[n-i-1]*pow(10,i,p))%p
    cnt[sum] += 1
  for j in range(p):
    cj = cnt[j]
    ans += cj * (cj-1)//2
print(ans)
### BUGGY CODE ###

# -*- coding:utf8 -*-

l, r = map(int, input().split())
if (l - r) >= 2019:
    ans = 0
elif 0 in [n % 2019 for n in range(l, r+1)]:
    ans = 0
elif 0 in [n % 673 for n in range(l, r+1)] and 0 in [n % 3 for n in range(l, r+1)]:
    ans = 0
else:
    m = sorted([(i * j) % 2019 for i in range(l, r) for j in range(i + 1, r + 1)])
    ans = m[0]
print(ans)

### FIXED CODE ###

# -*- coding:utf8 -*-

l, r = map(int, input().split())
if (l - r) >= 2019:
    ans = 0
else:
    ans = 2018
    for i in range(l, r):
        for j in range(i + 1, r + 1):
            m =  (i * j) % 2019
            if m == 0:
                print(m)
                exit()
            elif m < ans:
                ans = m
print(ans)
### BUGGY CODE ###

N = int(input())
P = [float(p) for p in input().split()]

DP = [[0 for n in range(N+1)] for _ in range(N)]
DP[0][0] = 1-P[0]
DP[0][1] = P[0]

for i in range(1, N):
    use = P[i]
    dontuse = 1 - use
    for j in range(N):
        if j == 0: DP[i][0] = DP[i-1][0] * dontuse
        else:
            DP[i][j] = DP[i-1][j] * dontuse + DP[i-1][j-1] * use
    if i == N-1: DP[N-1][N] = DP[N-2][N-1] * use

print(sum(DP[N-1][N//2+1:]))

### FIXED CODE ###

N = int(input())
P = [float(p) for p in input().split()]

DP = [[0 for n in range(N+1)] for _ in range(N)]
DP[0][0] = 1-P[0]
DP[0][1] = P[0]

for i in range(1, N):
    use = P[i]
    DP[i][0] = DP[i-1][0] * (1-use)
    for j in range(1, i+2):
        DP[i][j] = DP[i-1][j] * (1-use) + DP[i-1][j-1] * use

print(sum(DP[N-1][N//2+1:]))
### BUGGY CODE ###

import sys
import numpy as np

input = sys.stdin.readline
n = int(input())
s = list(int(input()) for _ in range(n))
i = 0
maxn = 0
s2 = []
while i < n:
    s2 = s.copy()
    del s2[i]
    print(np.max(np.array(s2)))
    i += 1


### FIXED CODE ###

n = int(input())
s = list(int(input()) for _ in range(n))
i = 0
sort_s = sorted(s)

for i in s:
    if i == sort_s[-1]:
        print(sort_s[-2])
    else:
        print(sort_s[-1])
### BUGGY CODE ###

"""
python3 a.py < input.txt
"""
import math
import itertools as it
import heapq

N=int(input())
S=input()

T=[S[0]]
U=[1]
for si in S[1:]:
    if T[-1] == si:
        U[-1] = U[-1]+1
    else:
        T.append(si)
        U.append(1)
M=len(T)
B=[U[i] if T[i] == "#" else 0 for i in range(M)]
W=[U[i] if T[i] == "." else 0 for i in range(M)]
l=[sum(B), sum(W)]
for i in range(M):
    if T[i] == "#":
        l.append(sum(B[:i]) + sum(W[min(i+1, M-1):]))

#print(S)
#print(T)
#print(U)
#print(B)
#print(W)
#print(l)
print(min(l))

### FIXED CODE ###

"""
python3 a.py < input.txt
"""
import math
import itertools as it
import heapq

N=int(input())
S=input()

T=[S[0]]
U=[1]
for si in S[1:]:
    if T[-1] == si:
        U[-1] = U[-1]+1
    else:
        T.append(si)
        U.append(1)
M=len(T)

B=[U[i] if T[i] == "#" else 0 for i in range(M)]
sumB=[B[0]]
for b in B[1:]:
    sumB.append(sumB[-1]+b)

W=[U[i] if T[i] == "." else 0 for i in range(M)]
sumW=[W[-1]]
for w in reversed(W[:-1]):
    sumW.append(sumW[-1]+w)
sumW=list(reversed(sumW))

l=[sum(B), sum(W)]
for i in range(M):
    if T[i] == "#":
        l.append(sumB[max(0, i-1)] + sumW[min(i+1, M-1)])

#print(S)
#print(T)
#print("U   ",U)
#print("B   ",B)
#print("sumB",sumB)
#print("W   ",W)
#print("sumW",sumW)
#print("l   ",l)
print(min(l))
### BUGGY CODE ###

from collections import Counter

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

bous = Counter(bou)
hen = []
ans = -1

i = 0
while(i<2):
    if len(bous) == 0:
        ans = 0
        break
    
    mkey = max(bous.keys())
    if bous[mkey] > 3:
        bous[mkey] = bous[mkey] - 2
        hen.append(mkey)
        i += 1
    elif bous[mkey] > 1:
        hen.append(mkey)
        bous.pop(mkey)
        i += 1
    else:
        bous.pop(mkey)
    
if ans:
    print(hen[0]*hen[1])
else:
    print(ans)

### FIXED CODE ###

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

a.sort(reverse=True)

num = None
hen = []
en = 0

for i in a:
    if en == 2:break
    if num == i:
        hen.append(num)
        num = None
        en += 1
    else:
        num = i
        
if en == 2:
    print(hen[0]*hen[1])
else:
    print(0)
### BUGGY CODE ###

H,W = map(int,input().split())
S = list(input() for i in range(H))
Grid1 = [[0]*W for i in range(H)]
#print(S)
ans = 0
ws = [0]*W
for i in range(H):
    cou = 0
    l = 0
    for j in range(W):
        #print(i,j,S[i][j])
        if S[i][j] == ".":
            cou += 1
        else:
            for x in range(l,j):
                ws[x] = cou
            ws[j] = 0
            l = j+1
            cou = 0
        for x in range(l,j+1):
            ws[x] = cou
    Grid1[i] = ws.copy()
ws = [0]*H
    
for i in range(W):
    cou = 0
    l = 0
    for j in range(H):
        #print(i,j,S[i][j])
        if S[j][i] == ".":
            cou += 1
        else:
            for x in range(l,j):
                ws[x] = cou
            ws[j] = 0
            l = j+1
            cou = 0
        for x in range(l,j+1):
            ws[x] = cou
    for j in range(H):
        ans =max(Grid1[j][i] +ws[j], ans)

print(ans-1)

### FIXED CODE ###

H,W = map(int,input().split())
S = list(input() for i in range(H))
Grid1 = [[0]*W for i in range(H)]
for i in range(H):
    cou = 0
    l = 0
    for j in range(W):
        if S[i][j] == ".":
            cou += 1
        else:
            for x in range(l,j):
                Grid1[i][x] = cou
            l = j+1
            cou = 0
    for x in range(l,j+1):
        Grid1[i][x] = cou    
for i in range(W):
    cou = 0
    l = 0
    for j in range(H):
        #print(i,j,S[i][j])
        if S[j][i] == ".":
            cou += 1
        else:
            for x in range(l,j):
                Grid1[x][i] += cou
            l = j+1
            cou = 0
    for x in range(l,j+1):
        Grid1[x][i] += cou

print(max(max(Grid1[i]) for i in range(H))-1)
### BUGGY CODE ###

def main():
  k, q = map(int, input().split())
  d = tuple(map(int, input().split()))
  for i in range(q):
    n, x, m = map(int, input().split())
    x %= m
    d_mod = []
    for i in d:
      i_mod = i % m
      if i_mod == 0:
        d_mod.append(m)
      else:
        d_mod.append(i_mod)
    d_mod_sum = sum(d_mod)
    rep = (n-1) // k
    rem = (n-1) % k
    rem_sum = sum(d_mod[:rem])
    ans = n - 1 - (x + d_mod_sum * rep + rem_sum) // m
    print(ans)
if __name__ == '__main__':
  main()

### FIXED CODE ###

def main():
  import numpy as np
  k, q = map(int, input().split())
  d = np.array(list(map(int, input().split())))
  for i in range(q):
    n, x, m = map(int, input().split())
    x %= m
    d_mod = d % m
    zero_d = k - np.count_nonzero(d_mod)
    d_mod_sum = np.sum(d_mod) + m * zero_d
    rep = (n-1) // k
    rem = (n-1) % k
    zero_rem = len(d_mod[:rem]) - np.count_nonzero(d_mod[:rem])
    rem_sum = np.sum(d_mod[:rem]) + m * zero_rem
    ans = n - 1 - (x + d_mod_sum * rep + rem_sum) // m
    print(ans)
if __name__ == '__main__':
  main()
### BUGGY CODE ###

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree2 = FenwickTree(N+1)
    m = [tuple(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(range(Q), key=lambda i: m[i][1])

    right = 0
    pos = [-1] * (N+1)
    ans = [None] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            if pos[c[i]] != -1:
                tree2.add(pos[c[i]], -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    print(*ans, sep="\n")


if __name__ == '__main__':
    solve()


### FIXED CODE ###

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree2 = FenwickTree(N+1)
    m = [list(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(list(range(Q)), key=lambda i: m[i][1])

    right = 0
    pos = [-1] * (N+1)
    ans = [-1] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            x = pos[c[i]]
            if x != -1:
                tree2.add(x, -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    print(*ans, sep="\n")


if __name__ == '__main__':
    solve()
### BUGGY CODE ###

K=int(input())

import fractions,itertools
data = [i for i in range(1,K+1)]

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
ans = 0
for a,b,c in itertools.product(data, repeat=3):
    ans += gcd(a,b,c)
print(ans)



### FIXED CODE ###

K=int(input())

import itertools,math
from functools import reduce

data = [i for i in range(1,K+1)]

def gcd(*numbers):
    return reduce(math.gcd, numbers)

ans = 0
for a,b,c in itertools.product(data, repeat=3):
    ans += gcd(a,b,c)
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))
from itertools import product

def main():
    N = int(input())
    adj = [inpl() for _ in range(N)]
    need = [[True]*N for _ in range(N)]
    ok = True
    res = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if adj[i][j] < adj[i][k] + adj[k][j]:
                    continue
                elif i == k or j == k:
                    continue
                elif adj[i][j] == adj[i][k] + adj[k][j]:
                    need[i][j] = False
                    need[j][i] = False
                else:
                    ok = False
    if ok:
        for i in range(N):
            for j in range(i+1, N):
                if need[i][j]:
                    res += adj[i][j]
        print(res)
    else:
        print(-1)

main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import combinations

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

N = int(input())
res = 0
exist = True
A = []

for _ in range(N):
    A.append(inpl())

for i, j in combinations(range(N), 2):
    vervose = False

    for k in range(N):
        if A[i][j] > A[i][k] + A[k][j]:
            exist = False
            break
    
    if not exist:
        break
    
    for k in range(N):
        if i == k or j == k:
            pass
        elif A[i][j] == A[i][k] + A[k][j]:
            vervose = True
            break
        
    if not vervose:
        res += A[i][j]
if exist:
    print(res)
else:
    print(-1)
### BUGGY CODE ###

import  collections 
N = int(input())
list_a = [input() for i in range(N)]
dict_a = collections.Counter(list_a)


list_ans = []

list_ans.append(dict_a.most_common()[0][0])
for i in range (1,len(dict_a)):
    if dict_a.most_common()[0][1] == dict_a.most_common()[i][1]:
        list_ans.append(dict_a.most_common()[i][0])

list_ans.sort()
for i in range (0,len(list_ans)):
    print(list_ans[i])

### FIXED CODE ###

N = int(input())
S = [input() for i in range(N)]
dictionary = {}
for word in S:
    if word in dictionary:
        dictionary[word] += 1
    else:
        dictionary[word] = 1

maximum = max(dictionary.values())
for key, value in sorted(dictionary.items()):
    if value == maximum:
        print(key)
### BUGGY CODE ###

import bisect


x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

ans_p = sorted(p, reverse=True)[:x][::-1]
ans_q = sorted(q, reverse=True)[:y][::-1]

r.sort(reverse=True)
for max_r in r:
    if ans_p[0] < ans_q[0]:
        if ans_p[0] < max_r:
            del ans_p[0]
            bisect.insort(ans_p, max_r)
        else:
            break
    else:
        if ans_q[0] < max_r:
            del ans_q[0]
            bisect.insort(ans_q, max_r)
        else:
            break
print(sum(ans_p)+sum(ans_q))

### FIXED CODE ###

x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

ans_p = sorted(p, reverse=True)[:x][::-1]
ans_q = sorted(q, reverse=True)[:y][::-1]
r.sort(reverse=True)

p_index = 0
q_index = 0
used_r_sum = 0

for max_r in r:
    ans_p_p_index = ans_p[p_index] if p_index < x else float('inf')
    ans_q_q_index = ans_q[q_index] if q_index < y else float('inf')
    if ans_p_p_index < ans_q_q_index:
        if ans_p_p_index < max_r:
            p_index += 1
            used_r_sum += max_r
        else:
            break
    else:
        if ans_q_q_index < max_r:
            q_index += 1
            used_r_sum += max_r
        else:
            break


print(sum(ans_p[p_index:])+sum(ans_q[q_index:])+used_r_sum)
### BUGGY CODE ###

import copy

if __name__ == '__main__':
    h, w = map(int, input().split())
    field = [list(input()) for i in range(h)]
    queue = []
    for y in range(h):
        for x in range(w):
            if field[y][x] == "#":
                queue.append((x, y))

    queue_cand = []
    d = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    cnt = 0
    while True:
        cnt += 1
        queue_cand = []
        for (x, y) in queue:
            for (dx, dy) in d:
                if 0 <= (x + dx) < w and 0 <= (y + dy) < h:
                    if field[y + dy][x + dx] == ".":
                        field[y + dy][x + dx] = cnt
                        queue_cand.append((x + dx, y + dy))

                    elif field[y + dy][x + dx] != "#":
                        if field[y + dy][x + dx] > cnt:
                            field[y + dy][x + dx] = min(field[y + dy][x + dx], cnt)
                            queue_cand.append((x + dx, y + dy))
        if len(queue_cand) == 0:
            break
        queue = copy.deepcopy(queue_cand)

    ans = 0
    for y in range(h):
        for x in range(w):
            if field[y][x] != "#":
                ans = max(ans, field[y][x])
    print(ans)


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())

a = [[False] * (w + 2)]
for y in range(h):
    a.append([False] + [x != '#' for x in input()] + [False])
a.append([False] * (w + 2))

s = deque()
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if not a[i][j]:
            s.append((i, j))

ans = -1
while s:
    ns = deque()
    for i, j in s:
        if a[i - 1][j]:
            a[i - 1][j] = False
            ns.append((i - 1, j))
        if a[i + 1][j]:
            a[i + 1][j] = False
            ns.append((i + 1, j))
        if a[i][j - 1]:
            a[i][j - 1] = False
            ns.append((i, j - 1))
        if a[i][j + 1]:
            a[i][j + 1] = False
            ns.append((i, j + 1))

    s = ns
    ans += 1

print(ans)