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

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.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

apb =  []

for a in A:
    for b in B:
        apb.append(a+b)
apb.sort(reverse=True)

apb = apb[:K]
ans = []

for k in apb:
    for c in (C):
        ans.append(k+c)
ans.sort(reverse=True)

for k in range(K):
    print(ans[k])

    


### FIXED CODE ###

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.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

apb =  []

for a in A:
    for b in B:
        apb.append(a+b)
apb.sort(reverse=True)

apb = apb[:K]
ans = []

for k in apb:
    for c in (C):
        ans.append(k+c)
ans.sort(reverse=True)

for k in range(K):
    print(ans[k])
### BUGGY CODE ###

def swap(A,i,j):
    A[i],A[j] = A[j],A[i]
    return A

def mincost(A):
    B = sorted(A)
    cost = 0
    
    for j, bj in enumerate(B):
        t = 0
        i = A.index(bj)
        tmp_cost = 0
        
        # swap in a cyclic group
        while j != i:
            t += 1
            bi = B[i]
            k = A.index(bi)
            tmp_cost += bi + bj #= ak + ai
            swap(A,j,k)
            j = k
        
        # diff. to swap with min(B)
        dec = t * (bj - B[0])
        inc = 2 * (bj + B[0])
        
        if dec < inc:
            cost += tmp_cost
        else:
            cost += tmp_cost - dec + inc
    return cost

if __name__ == "__main__":
    input()
    A = list(map(int, input().strip().split()))
    cost = mincost(A)
    print(cost)

### FIXED CODE ###

def swap(A,i,j):
    A[i],A[j] = A[j],A[i]
    return A

def mincost(A):
    B = sorted(A)
    cost = 0
    b0 = B[0]
    
    for i, bi in enumerate(B):
        t = 0
        j = A.index(bi)
        tmp_cost = 0
        
        # swap in a cyclic group
        while j != i:
            t += 1
            bj = B[j]
            k = A.index(bj)
            tmp_cost += bi + bj
            swap(A,j,k)
            j = k
        
        # diff. to swap with min(B)
        dec = t * (bi - b0)
        inc = 2 * (bi + b0)
        
        if dec < inc:
            cost += tmp_cost
        else:
            cost += tmp_cost - dec + inc
    return cost

if __name__ == "__main__":
    input()
    A = list(map(int, input().strip().split()))
    cost = mincost(A)
    print(cost)
### BUGGY CODE ###

n = int(input())
ns = list(map(int, input().split()))
ans = 0
from collections import Counter
c = Counter(ns)
dubbles = set([key for key, value in c.items() if value >= 2])
ns = sorted([i for i in ns if i not in dubbles])
n = len(ns)

def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    return divisors

for i in range(n):
    if make_divisors(ns[i]) & dubbles:
        dubbles.add(ns[i])
        continue
    ans += 1
    dubbles.add(ns[i])
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
ns = list(map(int, input().split()))
c = Counter(ns)
ans = 0

l = [True] * (max(ns)+1)
for i in sorted(set(ns)):
    if l[i]:
        j = i*2
        while j < len(l):
            l[j] = False
            j += i

a = set([key for key, value in c.items() if value == 1])
for i in a:
    if l[i]:
        ans += 1
print(ans)
### BUGGY CODE ###

A,B =[int(x) for x in input().split()]

def bunkai(n):
    sosu= [1]
    tmp = n
    
    if tmp%2 == 0:
        while tmp%2==0:
            tmp //=2
        sosu.append(2)
    
    for i in range(3,int(n/2)+1,2):
        if tmp%i == 0:
            while tmp%i==0:
                tmp //=i
            sosu.append(i)

    if tmp!=1:
        sosu.append(tmp)
                
    if sosu==[]:
        sosu.append[n]
    
    return sosu

def check_sosu(n,x):
    ans=0
    tmp = n
    for i in x:
        if (tmp % i) == 0:
            ans+=1
    return ans

ans = check_sosu(B,bunkai(A))

print(ans)

### FIXED CODE ###


A,B =[int(x) for x in input().split()]

def bunkai(n):
    sosu= {1}
    tmp = n
    stop_flag = n
    
    if tmp%2 == 0:
        while tmp%2==0:
            tmp //=2
        sosu.add(2)
    
    for i in range(3,n+1,2):
        if tmp%i == 0:
            while tmp%i==0:
                tmp //=i
            sosu.add(i)
            stop_flag = tmp 
            
        if i > stop_flag:
            break
        else:
            stop_flag = int(n/i)+1
            
    if tmp!=1:
        sosu.add(tmp)
                
    if sosu==[1]:
        sosu.add(n)
    
    return sosu

def check_sosu(n,x):
    ans=0
    tmp = n
    for i in x:
        if (tmp % i) == 0:
            ans+=1
    return ans

ans = check_sosu(B,bunkai(A))

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

import sys

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

def main():
    N = int(input())
    a = list(map(int,input().split()))
    cnt = 0

    for i in range(min(a),max(a)+1):
        cnt = max(a.count(i-1)+a.count(i)+a.count(i+1),cnt)
    print(cnt)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

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

def main():
    N = int(input())
    a = list(map(int,input().split()))
    cnt = [0] * (max(a) + 2)

    for i in a:
        if i != 0:
            cnt[i-1] += 1
        cnt[i] += 1
        cnt[i+1] += 1
    print(max(cnt))

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

import sys

INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())

sys.setrecursionlimit(10 ** 9)


def main():
    N, Q = MAP()
    S = INPUT()
    L = [1 if S[i:i+2] == "AC" else 0 for i in range(N-1)]

    ans = []
    for i in range(Q):
        l, r = MAP()
        ans.append(sum(L[l-1:r-1]))

    print(*ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())

sys.setrecursionlimit(10 ** 9)


def main():
    N, Q = MAP()
    S = INPUT()
    
    L = [0]
    for i in range(N-1):
        L.append(L[-1] + (1 if S[i:i+2] == "AC" else 0))

    ans = []
    for i in range(Q):
        l, r = MAP()
        ans.append(L[r-1] - L[l-1])

    print(*ans)


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

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

L = []
R = []
for i in range(K):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

dp = [0] * (N + 1)
dp[1] = 1
dp_sum = [0] * (N + 1)
dp_sum[1] = 1
for i in range(2, N + 1):
    for j in range(K):
        li = i - R[j]
        ri = i - L[j]
        if ri < 1:
            continue
        li = max(1, li)
        dp[i] += dp_sum[ri] - dp_sum[li - 1]
    dp_sum[i] = dp_sum[i - 1] + dp[i]

print(dp[-1] % MOD)


### FIXED CODE ###

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

L = []
R = []
for i in range(K):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

dp = [0] * (N + 1)
dp[1] = 1
dp_sum = [0] * (N + 1)
dp_sum[1] = 1
for i in range(2, N + 1):
    for j in range(K):
        li = max(i - R[j], 1)
        ri = i - L[j]
        if ri < 1:
            continue
        dp[i] += (dp_sum[ri] - dp_sum[li - 1]) % MOD
    dp_sum[i] = (dp_sum[i - 1] + dp[i]) % MOD

print(dp[-1] % MOD)
### BUGGY CODE ###

import math
a, b = map(int, input().split())
ans = math.ceil(a / 0.08)
while b != math.floor(ans*0.1):
    ans += 1

if math.floor(ans*0.08) == a:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

import math
a, b = map(int, input().split())
for i in range(1, 1010):
    if int(i*0.08)==a and int(i*0.1)==b:
        print(i)
        exit()
print(-1)
### BUGGY CODE ###

def check_prime(k):
    if k == 1:return 1
    num = int(k ** 0.5 // 1)
    for i in range(2, num + 1):
        if k % i == 0:
            if check.get(i) or check.get(k//i):return 0

    return 1

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
double = dict()
check = dict()
if a[0] == 1:
    if n == 1 or a[1] != 1:
        print(1)
        exit()
    else:
        print(0)
        exit()

for i in range(n):
    if i < n - 1 and a[i] == a[i + 1]:
        double[a[i]] = 1
        check[a[i]] = 1
        continue
    if double.get(a[i]):continue


    temp = check_prime(a[i])
    if temp:
        check[a[i]] = 1
        ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
check = [True] * (a[-1] + 1)
cnt = Counter(a)

for i in range(n):
    if check[a[i]] == False:continue
    for j in range(a[i], a[-1] + 1, a[i]):
        if j == a[i]:continue
        check[j] = False

ans = 0
for i in range(n):
    if check[a[i]] and cnt[a[i]] == 1:ans += 1

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

A, B, N = map(int, input().split())
ans = []
for x in range(N+1):
    a = int(A * x / B) - A * int(x / B)
    ans.append(a)
print(max(ans))

### FIXED CODE ###

A, B, N = map(int, input().split())
if N < B:
    ans = int(A * N / B) - A * int(N / B)
else:
    ans = int((B - 1) / B * A)
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n = int(raw_input())
s = str(raw_input())

l = s.strip()
memo=[]
for i in range(0,n):
    memo.append(-1)
memo[0]=0

for i in range(1,n):
    if s[i] == ".":
        memo[i] = min(s[:i].count("#"), memo[i-1]+1)
    else:
        memo[i] = min(memo[i-1], s[:i].count(".")+1)

print memo[n-1]


### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(raw_input())
s = str(raw_input())

ans=[]
black=[]
for i in range(0,n):
    ans.append(-1)
    black.append(-1)
ans[0]=0
if s[0]==".":
    black[0]=0
else:
    black[0]=1

for i in range(1,n):
    if s[i] == ".":
        black[i] = black[i-1]
        ans[i] = min(black[i-1], ans[i-1]+1)
    else:
        black[i] = black[i-1] + 1
        ans[i] = min(ans[i-1], black[i-1]+1)

print ans[n-1]
### BUGGY CODE ###

from sys import stdin, stdout, setrecursionlimit
setrecursionlimit = 1000000

input  = stdin.readline

n,m = list(map(int,input().split()))
par = [[] for _ in range(n+1)]
dis = [0]*(n+1)
vis = dis[:]

def dfs(n):
	sta = []
	sta.append(n)
	while(sta):
		n = sta.pop(-1)
		for i in par[n]:
			dis[i] = max(dis[i], dis[n]+1)
			sta.append(i)

for _ in range(m):
	x,y = map(int,input().split())
	par[x].append(y)

for i in range(1,n+1):
	if not vis[i]:
		dfs(i)

print(max(dis))


### FIXED CODE ###

import collections
import sys
from functools import lru_cache
sys.setrecursionlimit(int(10**9))
n, m  = [int(i) for i in input().strip().split(' ')] 
edges = collections.defaultdict(list)
for i in range(m):
    s,d = [int(i) for i in input().strip().split(' ')]
    edges[s-1].append(d-1) 
# dp = [-1]*n
maxPath = 0 
@lru_cache(None)
def dfs(node): 
    ans = 0 
    for i in edges[node]:
        ans = max(ans,dfs(i)+1)
    return ans
 
for i in range(n):
    maxPath = max(dfs(i), maxPath) 
print(maxPath)
### BUGGY CODE ###

n,m=map(int,input().split())
L={}

for i in range(n):
    a,b=map(int,input().split())
    if a in L:
        L[a].append(b)
    else:
        L[a]=[b]

ans=0
tab=[0 for i in range(m)]
for i in range(m):
    if i+1 in L:
        tab.extend(L[i+1])
    tab.sort()
    ans+=tab.pop(-1)

print(ans)
    

### FIXED CODE ###

import heapq
import queue

n,m=map(int,input().split())
L=[]
for inp in range(n):
    a,b=map(int,input().split())
    L.append((a,b))
L.sort(reverse=True)

pq=[]
heapq.heapify(pq)

    
ans=0
for i in range(1,m+1):
    while len(L)>0 and L[-1][0]==i:
        heapq.heappush(pq,L.pop()[1]*-1)
    #print(pq)
    if len(pq)==0:
        continue
    else:    
        ans-=heapq.heappop(pq)

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

def main():
    H, N = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(N)]
    dp = [[(10**8) for i in range(H + 1)] for j in range(N+1)]
    for i in range(N+1):
        dp[i][0] = 0

    for i in range(1, N + 1):
        for h in range(H + 1):
            dp[i][h] = min(dp[i][max(h - AB[i - 1][0], 0)] +
                           AB[i - 1][1], dp[i - 1][h])
    print(dp[N][H])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    H, N = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(N)]
    dp = [[(10**8) for i in range(H + 1)] for j in range(N+1)]
    for i in range(N+1):
        dp[i][0] = 0

    for i in range(1, N + 1):
        for h in range(H + 1):
            dp[i][h] = min(dp[i][max(h - AB[i - 1][0], 0)] +
                           AB[i - 1][1], dp[i - 1][h])
    print(dp[N][H])


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

N = int(input())
X = str(input())
X10 = int(X,2)

one_num = X.count("1")

for i in range(N):
    target = int(X[i])
    if target == 0:
        plus = pow(2,N-i-1)
        ones = one_num + 1
    else:
        plus = -pow(2,N-i-1)
        ones = one_num-1
    Xnow = X10+plus
    count = 0
    if Xnow == 0:
        print(count)
        continue
    else:
        Xnow = Xnow%ones
        count+=1
        for j in range(1000):
            if Xnow == 0:
                break
            Xnow2 = bin(Xnow)
            ones = Xnow2.count("1")
            Xnow = Xnow%ones
            count+=1
        print(count)


### FIXED CODE ###

N = int(input())
x2 = input()
x10 = int(x2, 2)
popc =  x2.count("1")
#print("x10", x10)
#print("popc", popc)
#popc: Nを2進数で表したときの1の個数

#以下で1つフリップさせた時の入力に対する余りを事前に計算
if popc <= 1:
    xp = x10%(popc+1)
    xm = 0
else:
    xp = x10%(popc+1)
    xm = x10%(popc-1)
#print("xp", xp)
#print("xm", xm)

#以下でフリップさせた場所のみを計算
for i in range(N):
    if x2[i] == "1":
        if popc == 1:
            print(0)
            continue
        tmp = (xm - pow(2, N-i-1, popc-1))%(popc-1)
    else:
        tmp = (xp + pow(2, N-i-1, popc+1))%(popc+1)
        
    #print("tmp", tmp)
    ans = 1
    while tmp > 0:
        tmp %= bin(tmp).count("1")
        ans += 1
    print(ans)
### BUGGY CODE ###

import sys
import copy
from collections import deque
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces
maxr = 10**18
_ = ni()
a = na()
res = 1
for item in a:
    res *= item

print(res if res <= maxr else -1)



### FIXED CODE ###

import sys
import copy
from collections import deque
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces
maxr = 10**18
_ = ni()
a = na()
res = 1

if 0 in a:
    print(0)
    exit(0)

for item in a:
    res *= item
    if res > maxr:
        print(-1)
        exit(0)

print(res)
### BUGGY CODE ###

N = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())

d = {
    1: N,
    2: 0,
    3: 0,
    4: 0,
    5: 0,
    6: 0,
}

ans = 0
while d[6] != N:
    m = min(d[5], E)
    d[5] -= m
    d[6] += m

    m = min(d[4], D)
    d[4] -= m
    d[5] += m

    m = min(d[3], C)
    d[3] -= m
    d[4] += m

    m = min(d[2], B)
    d[2] -= m
    d[3] += m

    m = min(d[1], A)
    d[1] -= m
    d[2] += m

    ans += 1

print(ans)


### FIXED CODE ###

from math import ceil

N = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())

min_move = min(A, B, C, D, E)

ans = ceil(N / min_move) + 4

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

from random import shuffle
N = int(input())
P = [int(c)-1 for c in input().split()]
#shuffle(P)
import numba
import numpy as np
#N = int(input())
#P = [int(c)-1 for c in input().split()]
# Mat = [[min(y, N-1-y, x, N-1-x) for y in range(N)] for x in range(N)]
# Mat = np.array(Mat)
@numba.njit()
def proc(N, P):
    ans = 0
    Removed = np.zeros((N, N), dtype=np.int32)
    closed = np.zeros((N,N), dtype=np.int32)
    Mat = np.zeros((N, N), dtype=np.int32)
    Dy, Dx = [1,0,-1,0], [0,1,0,-1]

    for y in range(N):
        for x in range(N):
            Mat[y, x] = min(y, N-1-y, x, N-1-x)
    #print(Mat)
    for i in range(N*N):
        p = P[i]
        y, x = divmod(p, N)
        ans += Mat[y][x]
        #print(p, Mat[y][x])
        Removed[y][x] = True
        #Mat[y][x] -= 1
        st = [(y, x)]
        clsd = [(y, x)]
        closed[y][x] = True
        while st:
            vy, vx = st.pop()
            vr = Removed[vy][vx]
            val = Mat[vy][vx]
            for dy, dx in zip(Dy, Dx):
                uy = vy + dy
                ux = vx + dx
                if not (0<=uy<N and 0<=ux<N):
                    continue
                ur = Removed[uy][ux]
                if vr:
                    if Mat[uy][ux] >= val+1:
                        Mat[uy][ux] = val
                        st.append((uy, ux))
                else:
                    if Mat[uy][ux] >= val+2:
                        Mat[uy][ux] = val+1
                        st.append((uy, ux))
        for y, x in clsd:
            closed[y][x] = False
    # for m in Mat:
    #     print(m)
    print(ans)
proc(N, P)



### FIXED CODE ###

import numba
import numpy as np
N = int(input())
P = np.array([int(c)-1 for c in input().split()])

#from random import shuffle
#N = 500
#P = list(range(N*N))
#shuffle(P)
#P = np.array(P)

@numba.njit("void(i8,i8[:])")
def proc(N, P):
    ans = 0
    Removed = np.zeros((500, 500), dtype=np.int8)
    Mat = np.zeros((500, 500), dtype=np.int16)
    Dy, Dx = [1,0,-1,0], [0,1,0,-1]

    for y in range(N):
        for x in range(N):
            Mat[y, x] = min(y, N-1-y, x, N-1-x)
    #print(Mat)
    for i in range(N*N):
        p = P[i]
        y, x = divmod(p, N)
        ans += Mat[y,x]
        Removed[y,x] = 1
        st = [(y, x)]
        while st:
            vy, vx = st.pop()
            vr = Removed[vy,vx]
            val = Mat[vy,vx]
            #for dy, dx in zip(Dy, Dx):
            for j in range(4):
                dy = Dy[j]
                dx = Dx[j]
                uy = vy + dy
                ux = vx + dx
                if not (0<=uy<N and 0<=ux<N):
                    continue
                ur = Removed[uy,ux]
                if vr:
                    if Mat[uy,ux] >= val+1:
                        Mat[uy,ux] = val
                        st.append((uy, ux))
                else:
                    if Mat[uy,ux] >= val+2:
                        Mat[uy,ux] = val+1
                        st.append((uy, ux))
    # for m in Mat:
    #     print(m)
    print(ans)
proc(N, P)
### BUGGY CODE ###

n = int(input())
S = {}
cnt = 0
for _ in range(n):
    s = input()
    s = sorted(s)
    u = ""
    for i in range(len(s)):
      u += s[i]
    if u in S.keys():
        S[u] += 1
    else:
        S[u] = 1
for x in S.values():
    x = x-1
    cnt += x*(x+1)//2
print(cnt)

### FIXED CODE ###

n = int(input())
S = {}
cnt = 0
for _ in range(n):
    s = input()
    s = sorted(s)
    u = ""
    for i in range(len(s)):
      u += s[i]
    if u in S.keys():
        S[u] += 1
    else:
        S[u] = 1
for x in S.values():
    x = x-1
    cnt += x*(x+1)//2
print(cnt)
### BUGGY CODE ###

import heapq
N,M = (int(x) for x in input().split())
pref = [[] for _ in range(N)]
ans = [0] * M
prefnumber = 0
for i in range(M):
    P,Y = (int(x) for x in input().split())
    pref[P-1].append((Y,i))
for p in pref:
    prefnumber += 1
    count = 1
    while p:
        heapq.heapify(p)
        temp = heapq.heappop(p)
        ans[temp[1]] = ''.join([str(prefnumber).zfill(6),str(count).zfill(6)])
        count += 1
print('\n'.join(ans))

### FIXED CODE ###

import sys
input = sys.stdin.readline

import heapq
N,M = (int(x) for x in input().split())
pref = [[] for _ in range(N)]
ans = [0] * M
prefnumber = 0
for i in range(M):
    P,Y = (int(x) for x in input().split())
    pref[P-1].append((Y,i))
for p in pref:
    prefnumber += 1
    count = 1
    if p:
        heapq.heapify(p)
        while p:
            temp = heapq.heappop(p)
            ans[temp[1]] = ''.join([str(prefnumber).zfill(6),str(count).zfill(6)])
            count += 1
print('\n'.join(ans))
### BUGGY CODE ###


X, K, D = map(int, input().split())
K2 = K
#X=１に近いものにおきかえる
if X >= 0:
  a= 1
else:
  a = -1
for i in range(K2):
  Y = X - a *D
  if a*Y< 0:
    break
  X=Y
  K-=1
  
#print(X, K, D)
      


flg = 0
minx = abs(X)
Xnow = X
Xprepre = 0
for i in range(K):
  if i != 0:
    Xprepre = Xpre
  Xpre = Xnow #前回
  X1 = Xnow -D
  X2 = Xnow +D
  if abs(X1) < abs(X2):
    Xnow = X1
  else:
    Xnow = X2
  #繰り返したらおわり
  if Xprepre == Xnow:
    flg = 1
    if (K-i+1)%2 == 0:
      print(abs(Xnow))
    else:
      print(abs(Xpre))
    break
if flg == 0:
  print(abs(Xnow))


### FIXED CODE ###


X, K, D = map(int, input().split())
K2 = K
#X=１に近いものにおきかえる
if X >= 0:
  a= 1
else:
  a = -1
#何回引けるか
h = min(K, int(a*X/D))
K = K-h
X = X - a*D*h

#print(X, K, D)
      


flg = 0
minx = abs(X)
Xnow = X
Xprepre = 0
for i in range(K):
  if i != 0:
    Xprepre = Xpre
  Xpre = Xnow #前回
  X1 = Xnow -D
  X2 = Xnow +D
  if abs(X1) < abs(X2):
    Xnow = X1
  else:
    Xnow = X2
  #繰り返したらおわり
  if Xprepre == Xnow:
    flg = 1
    if (K-i+1)%2 == 0:
      print(abs(Xnow))
    else:
      print(abs(Xpre))
    break
if flg == 0:
  print(abs(Xnow))
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)