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

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

hantei = False
ans = 0

isleft = True
kosu_original = N//4
for i in range(N-kosu_original+1):
    temp = S[i:i+kosu_original]
    # print("比較する文字列1:", temp)
    # print("比較する文字列2:",S[0:i] + "|" + S[i+kosu_original:],"\n")
    if temp in S[0:i] + "|" + S[i+kosu_original:]:
        # print("Trueの時\n-----------------")
        ans = kosu_original
        isleft = False
        break

if isleft:
    for kosu in range(kosu_original-1, 0, -1):
        if hantei:
            break

        for i in range(N-kosu+1):
            if hantei:
                break
            else:
                temp = S[i:i+kosu]
                # print("比較する文字列1:", temp)
                # print("比較する文字列2:",S[0:i] + "|" + S[i+kosu:],"\n")
            if temp in S[0:i] + "|" + S[i+kosu:]:
                # print("Trueの時\n-----------------")
                ans = kosu
                hantei = True
                break
else:
    for kosu in range(N//2, kosu_original, -1):
        if hantei:
            break

        for i in range(N-kosu+1):
            if hantei:
                break
            else:
                temp = S[i:i+kosu]
                # print("比較する文字列1:", temp)
                # print("比較する文字列2:",S[0:i] + "|" + S[i+kosu:],"\n")
            if temp in S[0:i] + "|" + S[i+kosu:]:
                # print("Trueの時\n-----------------")
                ans = kosu
                hantei = True
                break

print(ans)


### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    l1 = length = 0
    l2 = 1

    while (l2 + length < N):
        if S[l1:l2] in S[l2:]:
            length = l2 - l1
            l2 += 1
        else:
            l1 += 1
            l2 = l1 + length + 1
    print(length)

main()
### BUGGY CODE ###

from heapq import *
import numpy as np
n,m,s,t=map(int,input().split())
a=[[]for i in range (n+1)]
b=[[]for i in range(n+1)]
for i in range(m):
    p,q,r,g=map(int,input().split())
    a[p].append([q,r])
    a[q].append([p,r])
    b[p].append([q,g])
    b[q].append([p,g])
def f(x,r):
    p=[float("INF")]*(n+1)
    p[x],q=0,[[0,x]]
    while q:
        y,z=heappop(q)
        for i in r[z]:
            if p[i[0]]>y+i[1]:
                p[i[0]]=y+i[1]
                heappush(q,[y+i[1],i[0]])
    return p[1:]
s1,t1=f(s,a),f(t,b)
p=[]
for i in range(n):
    p.append([s1[i]+t1[i],i+1])
p,e=sorted(p),0
for i in range(n):
    while p[e][1]<=i: e+=1
    print(10**15-p[e][0])

### FIXED CODE ###

from heapq import heappush,heappop
n,m,s,t=map(int,input().split())
a,b=[[]for i in range (n+1)],[[]for i in range(n+1)]
for i in range(m):
    p,q,r,g=(int(i) for i in input().split())
    a[p].append((q,r))
    a[q].append((p,r))
    b[p].append((q,g))
    b[q].append((p,g))
def f(x,r):
    p=[float("inf")for i in range(n+1)]
    p[x],q=0,[[0,x]]
    while q:
        y,z=heappop(q)
        for i,j in r[z]:
            if p[i]>y+j:
                p[i]=y+j
                heappush(q,[p[i],i])
    return p
s1,t1,p=f(s,a),f(t,b),[]
for i in range(1,n+1):
    p.append((s1[i]+t1[i],i))
p,e=sorted(p),0
for i in range(n):
    while p[e][1]<=i: e+=1
    print(10**15-p[e][0])
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
ans=0
r,g,b=max(r,g,b),r+g+b-max(r,g,b)-min(r,g,b),min(r,g,b)
for i in range(n//r+1):
  for j in range(n//g+1):
    if (n-i*r-j*g)%b or (n-i*r-j*g)<0:
      continue
    ans+=1
print(ans)


### FIXED CODE ###

r,g,b,n=map(int,input().split())
ans=0
r,g,b=max(r,g,b),r+g+b-max(r,g,b)-min(r,g,b),min(r,g,b)
for i in range(n//r+1):
  for j in range(n//g+1):
    if (n-i*r-j*g)%b or (n-i*r-j*g)<0:
      continue
    ans+=1
print(ans)
### BUGGY CODE ###

import numpy as np
def resolve():
	# N: 品物の個数、W: 容量の上限
	N, W = map(int, input().split())
	# DP配列の宣言: DP[N][W]
	dp = np.empty((N+1, W+1), dtype=np.int64)
	# DP配列の初期化
	dp[0,:] = 0
	for i in range(N):
		w_n, v_n = map(int, input().split())
		dp[i+1, :w_n] = dp[i, :w_n]
		for j in range(w_n, W+1):
			dp[i+1, j] = max(
				dp[i, j-w_n]+v_n,	# バッグに入れた時の価値
				dp[i, j]			# バッグにいれない時の価値
			)
	print(dp[N, W])
resolve()

### FIXED CODE ###

import numpy as np
def resolve():
	# N: 品物の個数、W: 容量の上限
	N, W = map(int, input().split())
	# DP配列の宣言: DP[N][W]
	dp = np.empty((N+1, W+1), dtype=np.int64)
	# DP配列の初期化
	dp[0,:] = 0
	for i in range(N):
		w_n, v_n = map(int, input().split())
		dp[i+1, :w_n] = dp[i, :w_n]
		dp[i+1, w_n:] = np.maximum(
			dp[i, w_n:],
			dp[i, :(W+1-w_n)] + v_n
		)
	print(dp[N, W])
resolve()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def solve():
    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def addValue(iA, A):
        iB = iA + 1
        while iB <= numPow2:
            data[iB] += A
            iB += iB & -iB
    def getSum(iA):
        iB = iA + 1
        ans = 0
        while iB > 0:
            ans += data[iB]
            iB -= iB & -iB
        return ans

    N, M = map(int, input().split())
    querys = []
    for _ in range(N):
        L, R = map(int, input().split())
        querys.append((L, R, 0))
    for d in range(1, M+1):
        for k in range(1, M//d+1):
            querys.append((k*d, M, d, +1))
            querys.append((k*d, k*d-1, d, -1))
            querys.append(((k-1)*d, M, d, -1))
            querys.append(((k-1)*d, k*d-1, d, +1))

    querys.sort()

    data, numPow2 = makeBIT(M+1)

    anss = [0] * (M+1)
    for query in querys:
        _, y, *vs = query
        if vs[0] == 0:
            addValue(y, 1)
        else:
            d, s = vs
            v = getSum(y)
            anss[d] += s*v

    print('\n'.join(map(str, anss[1:])))


solve()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def solve():
    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def addValue(iA, A):
        iB = iA + 1
        while iB > 0:
            data[iB] += A
            iB -= iB & -iB
    def getValue(iA):
        iB = iA + 1
        ans = 0
        while iB <= numPow2:
            ans += data[iB]
            iB += iB & -iB
        return ans
    def addRangeValue(iFr, iTo, A):
        addValue(iTo, A)
        if iFr > 0:
            addValue(iFr-1, -A)

    N, M = map(int, input().split())
    LRss = [[] for _ in range(M+1)]
    for _ in range(N):
        L, R = map(int, input().split())
        LRss[R-L+1].append((L, R))

    data, numPow2 = makeBIT(M+1)

    anss = []
    numOK = N
    for d in range(1, M+1):
        ans = numOK
        for i in range(d, M+1, d):
            ans += getValue(i)
        anss.append(ans)
        numOK -= len(LRss[d])
        for L, R in LRss[d]:
            addRangeValue(L, R, 1)

    print('\n'.join(map(str, anss)))


solve()
### BUGGY CODE ###

from collections import defaultdict, deque

N = int(input())
E = [[] for _ in range(N+1)]
inp = []
for i in range(N-1):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
    inp.append((a, b))


# node: (id, parent_id)
root_node = (1, -1)
open_list = deque([root_node])
n2c = defaultdict(list)
ans = {}
colors = [-1]*(N-1)
while True:
    if len(open_list)==0:
        break
    cur_node = open_list.popleft()
    cur_id, parent_id = cur_node
    adj_id_list = E[cur_id]
    for child_id in adj_id_list:
        if child_id == parent_id:
            continue
        color = 1
        while True:
            if not color in n2c[cur_id]:
                n2c[cur_id].append(color)
                n2c[child_id].append(color)
                ans[(cur_id, child_id)] = color
                break
            color += 1
        open_list.append((child_id, cur_id))

print(max(list(map(lambda x:len(x), n2c.values()))))
for a, b in inp:
    if (a, b) in ans.keys():
        print(ans[(a, b)])
    else:
        print(ans[(b, a)])

### FIXED CODE ###

from collections import defaultdict, deque

N = int(input())
E = [[] for _ in range(N+1)]
edge_order = []
for i in range(N-1):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
    edge_order.append(b)


# node: (id, parent_id)
root_node = (1, -1)
open_list = deque([root_node])
ans = {}
colors = [-1]*(N+1)
while open_list:
    cur_node = open_list.popleft()
    cur_id, parent_id = cur_node
    adj_id_list = E[cur_id]
    c = 1
    for child_id in adj_id_list:
        if child_id == parent_id:
            continue
        if c == colors[cur_id]:
            c += 1
        colors[child_id] = c
        c += 1
        open_list.append((child_id, cur_id))

print(max(colors))
for i in edge_order:
    print(colors[i])
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

def main():
    n, m = map(int, sys.stdin.readline().split())
    lrds = ((map(int, line.split())) for line in sys.stdin.readlines())

    g = tuple([] for _ in range(n))
    x = [None] * n

    for l, r, d in lrds:
        l -= 1
        r -= 1
        g[l].append((r, d))
        g[r].append((l, -d))

    for i in range(n):
        if x[i]:
            continue
        stack = [i]
        x[i] = 0
        while len(stack) > 0:
            v = stack.pop()
            for u, d in g[v]:
                if not x[u]:
                    stack.append(u)
                    x[u] = x[v] + d

    for v in range(n):
        for u, d in g[v]:
            if x[v] + d != x[u]:
                print('No')
                sys.exit()

    print('Yes')

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

def main():
    n, m = map(int, sys.stdin.readline().split())
    lrds = ((map(int, line.split())) for line in sys.stdin.readlines())

    g = tuple([] for _ in range(n))
    x = [None] * n

    for l, r, d in lrds:
        l -= 1
        r -= 1
        g[l].append((r, d))
        g[r].append((l, -d))

    for i in range(n):
        if x[i] is not None:
            continue
        stack = [i]
        x[i] = 0
        while len(stack):
            v = stack.pop()
            for u, d in g[v]:
                if x[u] is None:
                    stack.append(u)
                    x[u] = x[v] + d

    for v in range(n):
        for u, d in g[v]:
            if x[v] + d != x[u]:
                print('No')
                sys.exit()

    print('Yes')

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

S = input()[::-1]
day_dream_word = ["dreamer", "dream", "eraser", "erase"]
day_dream_word = list(map(lambda s: s[::-1], day_dream_word))
T = ""
res = False
partial_res = True
while not res and partial_res:
  partial_res = False
  for add_word in day_dream_word:
    nextT = T
    nextT += add_word
    if S == nextT:
      res = True
      break
    if S[:len(nextT)] == nextT:
      partial_res = True
      break
  T = nextT

if res:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

S = input()[::-1]
day_dream_word = ["dreamer", "dream", "eraser", "erase"]
day_dream_word = list(map(lambda s: s[::-1], day_dream_word))
T = ""
Tindex = 0
res = False
partial_res = True
while not res and partial_res:
  partial_res = False
  for add_word in day_dream_word:
    nextTindex = Tindex + len(add_word)
    
    if S[Tindex:nextTindex] == add_word:
      if len(S) == nextTindex:
        res = True
        break
      else:
        partial_res = True
        break
  Tindex = nextTindex

if res:
  print('YES')
else:
  print('NO')
### BUGGY CODE ###

from collections import Counter
s = input()
n = len(s)
dp = [0]*(n+1)
mod = 2019
for i in range(n-1,-1,-1):
    dp[i] = (dp[i+1]+int(s[i])*(10**(n-i-1)))%mod
c = Counter(dp)
ans = 0
for i in c.values():
    ans += i*(i-1)//2
print(ans)

### FIXED CODE ###

from collections import Counter
s = input()
n = len(s)
dp = [0]*(n+1)
mod = 2019
for i in range(n-1,-1,-1):
    dp[i] = (dp[i+1]+int(s[i])*pow(10,n-i-1,mod))%mod
c = Counter(dp)
ans = 0
for i in c.values():
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
total = 0

for i in range(N-2):
    for j in range(i+1, N-1):
        if S[i] == 'R':
            if S[j] == 'R':
                continue
            elif S[j] == 'G':
                total += S[j+1:N].count('B')
                if 2*j-i < N:
                    if S[2*j-i] == 'B':
                        total -= 1
            elif S[j] == 'B':
                total += S[j+1:N].count('G')
                if 2*j-i < N:
                    if S[2*j-i] == 'G':
                        total -= 1
        elif S[i] == 'G':
            if S[j] == 'G':
                continue
            elif S[j] == 'R':
                total += S[j+1:N].count('B')
                if 2*j-i < N:
                    if S[2*j-i] == 'B':
                        total -= 1
            elif S[j] == 'B':
                total += S[j+1:N].count('R')
                if 2*j-i < N:
                    if S[2*j-i] == 'R':
                        total -= 1
        if S[i] == 'B':
            if S[j] == 'B':
                continue
            elif S[j] == 'G':
                total += S[j+1:N].count('R')
                if 2*j-i < N:
                    if S[2*j-i] == 'R':
                        total -= 1
            elif S[j] == 'R':
                total += S[j+1:N].count('G')
                if 2*j-i < N:
                    if S[2*j-i] == 'G':
                        total -= 1

print(total)


### FIXED CODE ###

N = int(input())
S = input()
total = 0

for i in range(N-2):
    if S[i] == "R":
        num_G = S[i+1:].count('G')
        num_B = S[i+1:].count('B')
        total += num_G * num_B
    elif S[i] == "G":
        num_B = S[i+1:].count('B')
        num_R = S[i+1:].count('R')
        total += num_B * num_R
    elif S[i] == "B":
        num_G = S[i+1:].count('G')
        num_R = S[i+1:].count('R')
        total += num_G * num_R

for i in range(N-2):
    for j in range(i+1, N-1):
        if 2*j-i >= N:
            continue
        if S[j] != S[i] and S[2*j-i] != S[j] and S[2*j-i] != S[i]:
            total -= 1

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

# a^n mod p
def beki_mod(a, n, p):
    ans = 1
    n = format(n, "b")
    for i in range(len(n)):
        ans = ans * ans % p
        if n[i] == "1":
            ans = ans * a % p
    return ans

# nCr = n * (n -1) * ... * (n - r + 1) / r!
# a^(-1) mod p = a^(p -2) mod p
def combi_mod(n, r, p):
    bunshi = 1
    bumbo_gyakugen = 1
    r = min(r, n - r)

    while r > 0:
        bunshi = bunshi * n % p
        bumbo_gyakugen = bumbo_gyakugen * beki_mod(r, p - 2, p) % p
        n -= 1
        r -= 1
    
    ans = bunshi * bumbo_gyakugen % p
    return ans


H, W, A, B = map(int, input().split())
mod = 10 ** 9 + 7

if B < W / 2:
    not_ans = 0
    total = combi_mod((H - 1) + (W - 1), H-1, mod)
    for i in range(B):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = combi_mod((sq1h -1) + (sq1w - 1), (sq1h -1), mod) * combi_mod((sq2h - 1) + (sq2w - 1), (sq2h - 1), mod) % mod
        not_ans += n
    ans = (total - not_ans) % mod
    print(ans)
        
else:
    ans = 0
    for i in range(B, W):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = combi_mod((sq1h - 1) + (sq1w - 1), (sq1h - 1), mod) * combi_mod((sq2h - 1) + (sq2w - 1), (sq2h - 1), mod)
        ans += n
    ans %= mod
    print(ans)


### FIXED CODE ###

mod = 10 ** 9 + 7
N = 10 ** 6
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, N + 1):
    fact.append(fact[-1] * i % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

def combi_mod(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p


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

if B < W / 2:
    not_ans = 0
    total = combi_mod((H - 1) + (W - 1), H-1, mod)
    for i in range(B):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = combi_mod((sq1h -1) + (sq1w - 1), (sq1h -1), mod) * combi_mod((sq2h - 1) + (sq2w - 1), (sq2h - 1), mod) % mod
        not_ans = (not_ans + n) % mod
    ans = (total - not_ans) % mod
    print(ans)
        
else:
    ans = 0
    for i in range(B, W):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = combi_mod((sq1h - 1) + (sq1w - 1), (sq1h - 1), mod) * combi_mod((sq2h - 1) + (sq2w - 1), (sq2h - 1), mod)
        ans = (ans + n) % mod
    ans %= mod
    print(ans)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
l.sort(reverse=True)
count = 0
for i in range(n-2):
    for j in range(n - i - 2):
        for k in range(n - i - j - 2):
            hen = []
            hen.append(l[i])
            hen.append(l[i+j+1])
            hen.append(l[i+j+k+2])
            if hen[0] < hen[1] + hen[2]:
                count += 1
print(count)


### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int,input().split()))
l.sort()
count = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        short_2hen = l[i] + l[j]
        bis = bisect.bisect_left(l, short_2hen)
        count += bis - j - 1
print(count)
### BUGGY CODE ###


n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
bit_one_count = [0 for i in range(60)]
bit_zero_count = [0 for i in range(60)]
for i in range(n):
    bits = '{0:060b}'.format(a[i])
    for j in range(60):
        if bits[-1 -j] == '1':
            bit_one_count[j] += 1
        else:
            bit_zero_count[j] += 1

ans = 0
for j in range(60):
    ans += bit_one_count[j] * bit_zero_count[j] * 2 ** j
    ans %= MOD

print(ans)


### FIXED CODE ###


n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
bit_one_count = [0 for i in range(60)]
bit_zero_count = [0 for i in range(60)]
for i in range(n):
    bits = '{0:060b}'.format(a[i])
    for j in range(60):
        if bits[-1 -j] == '1':
            bit_one_count[j] += 1
        else:
            bit_zero_count[j] += 1

ans = 0
for j in range(60):
    ans += bit_one_count[j] * bit_zero_count[j] * 2 ** j
    ans %= MOD

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

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

s = [0]*N

for i in range(N):
    s[i] += S[:i].count('W')
    s[i] += S[i+1:].count('E')

print(min(s))


### FIXED CODE ###

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

s = [0]*(N+1)
e = [0]*(N+1)
for i in range(1, N+1):
    k = 0
    if S[i-1] == "W":
        k = 1
    s[i] = s[i-1] + k

for i in reversed(range(0, N)):
    k = 0
    if S[i] == "E":
        k = 1
    e[i] = e[i+1] + k

ans = N
for i in range(1, N+1):
    ans = min(ans, s[i-1]+e[i])


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

n = int(input())
s = input()
ans = n
for i in range(1,n):
    a = s[:i-1]
    b = s[i:]
    ans = min(ans,a.count('W')+b.count('E'))
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = n
c = s[1:]
d = c.count('E')
ans = d
count = d
for i in range(1,n):
    a = s[i-1]
    b = s[i]
    if a == 'W' and b == 'W':
        count += 1
    elif a == 'E' and b == 'E':
        count -= 1
    ans = min(ans,count)
print(ans)
### BUGGY CODE ###

def sub_group(A):
    ret = []
    for i in range(1 << len(A)):
        output = []
        for j in range(len(A)):
            if ((i >> j) & 1) == 1:
                output.append(A[j])
        if output != []:
            ret.append(output)
    return ret

def f(X, validGroup):
    ret = 0
    pattern = sub_group(X)
    for candidate in pattern:
        if candidate in validGroup:
            ret += 1
    return ret

def main():
    MOD = 998244353
    n, s = map(int, input().split())
    a = [i for i in map(int, input().split())]
    
    validGroup = []
    sub_g = sub_group(a)
    for g in sub_g:
        if sum(g) == s:
            validGroup.append(g)

    ans = 0
    for g in sub_g:
        ans += f(g, validGroup)
    
    print(ans % MOD)


main()


### FIXED CODE ###

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

dp = [[0 for i in range(S + 1)] for j in range(N + 1)]

dp[0][0] = 1

for i in range(N):
    for j in range(S + 1):
        dp[i+1][j] += dp[i][j] * 2
        dp[i+1][j] %= MOD
        if j + A[i] <= S:
            dp[i + 1][j + A[i]] += dp[i][j]
            dp[i + 1][j + A[i]] %= MOD
print(dp[N][S])
### BUGGY CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))
def f(n):
    return (n+1)/2
p=[]
for i in P:
    p.append(f(i))
def S(n):
    return sum(p[n:n+K])
A=[]
for j in range(len(P)):
    A.append(S(j))
print(max(A))

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
ex = [0 for _ in range(n)]
for i in range(n):
    ex[i] = (p[i]+1)/2

sumex = sum(ex[:k])
tmp = sum(ex[:k])
for i in range(n-k):
    tmp = tmp + (ex[i+k] - ex[i])
    sumex = max(sumex, tmp)
print(sumex)
### BUGGY CODE ###

(n,),*e=[[*map(int,i.split())]for i in open(0)]
a=sorted(e)
b=sorted(e,key=lambda x: x[1])
ans=0
for i,j in a[:10]:
    for ii,jj in b[:10]:
        ans=max(ans,abs(i-ii)+abs(j-jj))
for i,j in a[:10]:
    for ii,jj in a[10:]:
        ans=max(ans,abs(i-ii)+abs(j-jj))
for i,j in a[10:]:
    for ii,jj in b[:10]:
        ans=max(ans,abs(i-ii)+abs(j-jj))
for i,j in b[10:]:
    for ii,jj in b[:10]:
        ans=max(ans,abs(i-ii)+abs(j-jj))
print(ans)

### FIXED CODE ###

a,b=[],[]
for _ in range(int(input())):
    x,y=map(int,input().split())
    a+=[x-y]
    b+=[x+y]
print(max(max(a)-min(a),max(b)-min(b)))
### BUGGY CODE ###

#Lower
N = int(input())
H = list(map(int, input().split()))
max = 0

for i in range(N):
    n = 0
    for j in range(i+1,N):
        if H[j-1] >= H[j]:
            n = n+1
        else :
            break
    if n > max:
        max = n

print(max)


### FIXED CODE ###

#Lower
N = int(input())
H = list(map(int, input().split()))
max = 0
n=0

for i in range(N-1):
    if H[i] >= H[i+1]:
        n = n+1
    else :
        n = 0
    if n > max:
        max = n

print(max)
### BUGGY CODE ###

H,W = list(map(int,input().split()))
A = [["*"]*(W+2)]

sum = 0
cnt = 0

for i in range(H):
    a = ["*"]
    a += input()
    a.append("*")
    sum += a.count("#")
    A.append(a)
A.append(["*"]*(W+2))

while True:
    if sum == H*W:
        break
    x = []
    for i in range(1,H+1):
        for j in range(1,W+1):
            if A[i][j] == ".":
                for k,l in [[-1,0],[0,-1],[0,1],[1,0]]:
                    if A[i+k][j+l] == "#":
                        x.append([i,j])
                        break

    for i,j in x:
        A[i][j] = "#"
        sum += 1

    cnt += 1

print(cnt)

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
q = deque()
A = []
for h in range(H):
    r = input()
    for w in range(W):
        if r[w] == "#":
            q.append([h, w])
    A.append([0 if s=="#" else -1 for s in r])

d = [[-1, 0], [0, -1], [0, 1], [1, 0]]
p = 0

while q:
    h, w = q.popleft()
    p = A[h][w]+1
    for dh, dw in d:
        nh = h+dh
        nw = w+dw
        if not (0 <= nh < H):
            continue
        if not (0 <= nw < W):
            continue
        if A[nh][nw] == -1:
            A[nh][nw] = p
            q.append([nh, nw])

print(p-1)