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

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


#N,K=map(int,input().split())
N=int(input())
S=input()
Q=int(input())
Query=[input().split() for i in range(Q)]


def segfunc(x,y):
    return (x|y)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,b):
    k += num-1
    if seg[k]==set([b]):
        return ()
    seg[k] = set([b])
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p>>1
        q = (q-1)>>1
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele =set()

#num:n以上の最小の2のべき乗
n=N
num =2**(n-1).bit_length()
seg=[set() for i in range(2*num)]

for i in range(N):
    update(i,ord(S[i]))

for type,i,c in Query:

    if type=="1":
        update(int(i)-1,ord(c))
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)


### FIXED CODE ###

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


#N,K=map(int,input().split())
N=int(input())
S=input()
Q=int(input())
Query=[input().split() for i in range(Q)]

def segfunc(x,y):
    return (x|y)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=seg[2*i+1]|seg[2*i+2]

def update(k,b):
    k += num-1
    if seg[k]=={b}:
        return ()
    seg[k] = {b}
    while k:
        k = (k-1)>>1
        seg[k] = seg[k*2+1]|seg[k*2+2]

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=set()
    while q-p>1:
        if p&1 == 0:
            res = res|seg[p]
        if q&1 == 1:
            res = res|seg[q]
            q -= 1
        p = p>>1
        q = (q-1)>>1
    if p == q:
        res = res|seg[p]
    else:
        res = res|seg[p]|seg[q]
    return res

#num:n以上の最小の2のべき乗
n=N
num =2**(n-1).bit_length()
seg=[set()] * (2*num)

for i in range(N):
    seg[i+num-1]={ord(S[i])}
for k in range(num-2,-1,-1):
    seg[k] = seg[k*2+1]|seg[k*2+2]
for type, i, c in Query:
    if type=="1":
        update(int(i)-1,ord(c))
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)
### BUGGY CODE ###

a=int(input())
b=input()
r_num=0
w_num=0
for i in b :

  if i=='W' :
    w_num+=1
  else :
    r_num+=1
c=''
for i in range(r_num):
  c+='R'
for i in range(w_num) :
  c+='W'
count=0

for i in range(r_num) :
  if c[i]!=b[i] :
    count+=1
print(count)

### FIXED CODE ###

a=int(input())
b=input()
r_num=0
w_num=0
for i in b :

  if i=='W' :
    w_num+=1
  else :
    r_num+=1

count=0

for i in range(r_num) :
  if b[i]=='W' :
    count+=1


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

import sys,os,io
input = sys.stdin.readline
# input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = list(map(int, input().split()))
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
mod = 10**9+7
def comb_mod(n,r):
  ans = 1
  for i in range(r):
    ans *= (n-i)*pow(i+1,mod-2,mod)
    ans %= mod
  return ans
def combs_mod(n,k):
  #nC0からnCkまで
  ans = [1]*(k+1)
  for i in range(1,k+1):
    ans[i] = ans[i-1]*(n+1-i)*pow(i,mod-2,mod)%mod
  return ans

def dfs(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  while stack:
    v = stack[-1]
    marker = 0
    for u in edge[v]:
      if u==parent[v]:
        continue
      if parent[u]==N: #子へ降ろす
        marker = 1
        parent[u] = v
        stack.append(u)
      else: #子から吸い上げる
        part_num[v] += part_num[u]
        ans[v] *= comb_mod(part_num[v]-1, part_num[u])*ans[u]%mod
        ans[v] %= mod
    if marker==0:
      stack.pop()
  return

def dfs2(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  p_value = [0]*N
  combs = combs_mod(N-1,N-1)
  while stack:
    v = stack.pop()
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        continue
      parent[u]=v
      p_value[u] = ans[v]*pow(ans[u]*combs[part_num[u]],mod-2,mod)%mod
      ans[u] *= combs[part_num[u]-1]*p_value[u]
      ans[u] %= mod
      stack.append(u)
    ans[v] %= mod
  return

ans = [1]*N
part_num = [1]*N
dfs(0)
dfs2(0)
print(*ans, sep='\n')

### FIXED CODE ###

import sys,os,io
input = sys.stdin.readline
# input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = list(map(int, input().split()))
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
mod = 10**9+7

def fact(N):
  ans = [1]*(N+1)
  for i in range(1,N+1):
    ans[i] = ans[i-1]*i%mod
  return ans

def combs_mod(n,k):
  #nC0からnCkまで
  inv = [1]*(k+1)
  for i in range(1,k+1):
    inv[i] = pow(i,mod-2,mod)
  ans = [1]*(k+1)
  for i in range(1,k+1):
    ans[i] = ans[i-1]*(n+1-i)*inv[i]%mod
  return ans

def dfs(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  fac = fact(N)
  while stack:
    v = stack[-1]
    marker = 0
    for u in edge[v]:
      if u==parent[v]:
        continue
      if parent[u]==N: #子へ降ろす
        marker = 1
        parent[u] = v
        stack.append(u)
      else: #子から吸い上げる
        part_num[v] += part_num[u]
        ans[v] *= pow(fac[part_num[u]],mod-2,mod)*ans[u]%mod
        ans[v] %= mod
    if marker==0:
      stack.pop()
      ans[v] *= fac[part_num[v]-1]
      ans[v] %= mod
  return

def dfs2(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  p_value = [0]*N
  combs = combs_mod(N-1,N-1)
  while stack:
    v = stack.pop()
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        continue
      parent[u]=v
      p_value[u] = ans[v]*pow(ans[u]*combs[part_num[u]],mod-2,mod)%mod
      ans[u] *= combs[part_num[u]-1]*p_value[u]
      ans[u] %= mod
      stack.append(u)
  return

ans = [1]*N
part_num = [1]*N
dfs(0)
dfs2(0)
print(*ans, sep='\n')
### BUGGY CODE ###

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

def count_inversion(input_array):
    return sum(sum(m < n for m in input_array[i + 1:]) for i, n in enumerate(input_array))

b = list(reversed(sorted(set(a))))

m = n * (n + 1) // 4 + 1

for ans in b:
    s = [0 for _ in range(n)]
    s[0] = 0
    for i in range(1,n):
        if a[i] >= ans:
            s[i] = s[i - 1] + 1
        else:
            s[i] = s[i - 1] - 1
    if count_inversion(s) <= m:
        print(ans)
        break

### FIXED CODE ###

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

if n == 1:
    print(a[0])
    exit()

b = list(sorted(set(a)))

def count_inversion(ans):
    s = [0 for _ in range(2 * n + 2) ]

    def bit_add(i):
        x = i
        while x < 2 * n:
            s[x] += 1
            x += x & -x

    def bit_sum(i):
        x = i
        ret = 0
        while x > 0:
            ret += s[x]
            x -= x & -x
        return ret

    temp = [n for _ in range(n + 1)]
    temp[0] = n + 1
    for i in range(n):
        if a[i] >= b[ans]:
            temp[i + 1] = temp[i] + 1
        else:
            temp[i + 1] = temp[i] - 1
    res = 0
    for i in range(n + 1):
        x = temp[i]
        res += bit_sum(x)
        bit_add(x)
    return res

m = n * (n + 1) // 2

ans = 0

l = 0
r = len(b)
while 1:
    ans = (l + r) // 2
    if count_inversion(ans) * 2 >= m:
        l = ans
    else:
        r = ans
    if r - l <= 1:
        ans = l
        break

print(b[ans])
### BUGGY CODE ###

#coding utf-8
import numpy as np
_=input()
bars=[i for i in map(int,input().split())]
np_data=np.array(bars)
bars.sort(reverse=True)

stock=[]
len_stock=0
ret=0
_old=-1
for bar in bars:
    if bar==_old:
        continue
    _old=bar
    count=np.where(np_data==bar)[0].size
    if count>=4:
        if len_stock!=0 and  bar not in stock:
            #print("ret bar bar")
            ret=bar*stock[0]
        else:
            #print("ret bar bar")
            ret=bar*bar
        break
    elif count>=2:
        if bar in stock:
            continue
        stock.append(bar)
        len_stock+=1
        if len_stock==2 :
            #print("ret stock stock")
            ret=stock[0]*stock[1]
            break
print(ret)

### FIXED CODE ###

#coding utf-8
import collections
_=input()
bars=[i for i in map(int,input().split())]
data=sorted(collections.Counter(bars).items(),key= lambda x: -x[0] )
stock=0
ret=0
for bar ,count in data:
    if count>=4:
        if stock:
            ret=stock*bar
            break
        else:
            ret=bar*bar
            break
    elif count>=2:
        if stock:
            ret=stock*bar
            break
        else:
            stock=bar
print(ret)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
tu=0
td=0
for j in range(k):
  temp=[0]*n
  for i in range(n):
    td=max(i+1-a[i],1)
    temp[td-1]=temp[td-1]+1
    tu=min(i+1+a[i],n)
    if tu!=n:
      temp[tu]=temp[tu]-1
  a[0]=temp[0]
  for i in range(1,n):
    a[i]=a[i-1]+temp[i]
  if sum(a)==n**2:
    break
L=[str(t) for t in a]
L=" ".join(L)
print(L)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
tu=0
td=0
if k>=40:
  a=[n]*n
else:
  for j in range(k):
    temp=[0]*n
    for i in range(n):
      td=max(i+1-a[i],1)
      temp[td-1]=temp[td-1]+1
      tu=min(i+1+a[i],n)
      if tu!=n:
        temp[tu]=temp[tu]-1
    a[0]=temp[0]
    for i in range(1,n):
      a[i]=a[i-1]+temp[i]
L=[str(t) for t in a]
L=" ".join(L)
print(L)
### BUGGY CODE ###

S = input()
def del_01(char):
    char_1 = char.replace("01","").replace("10","")
    return char_1

char = S
last_len = 0
while len(char)!=last_len:
    last_len = len(char)
    char = del_01(char)
print(len(S)-len(char))

### FIXED CODE ###

from collections import Counter
C = Counter(list(input()))
print(C["0"]*2 if C["0"]<=C["1"] else C["1"]*2)
### BUGGY CODE ###

import numpy as np

def f(x,a):
  return np.array([ c^x for c in a],dtype=np.int64).sum()

def bitlength(x):
  i=0
  while x > 0:
    x //= 2
    i += 1
  return i

def bitlengthceil(x):
  l = bitlength(x)
  if x == 2**(l-1):
    return l
  else:
    return (l+1)

def bit2num(y):
  return np.array([ y[m]<<m for m in range(M)]).sum()

(N,K) = map(int,input().split())
A = np.array(list(map(int,input().split())),dtype=np.int64)
M=40

B = np.empty((M,N),dtype=np.int64)
Y = np.empty(M,dtype=np.int64)
D = np.empty(M,dtype=np.int64)

for n in range(N):
  for m in range(M):
    B[m,n] = (A[n] >> m) % 2

for m in range(M):
  s = B[m].sum()
  if 2*s < N:
    Y[m] = 1
    D[m] = (N-2*s)<<m
  else:
    Y[m] = 0
    D[m] = 0

Kb = np.array([ (K >> i) % 2 for i in range(M)],dtype=np.int64)

ans = f(0,A)
for m in range(M):
  if Kb[m] == 0:
    continue
  else:
    X = bit2num(np.concatenate((Y[:m],np.array([0],dtype=np.int64),Kb[m+1:])))
    ans = max(ans,f(X,A))

print(ans)

### FIXED CODE ###

inpl = lambda: list(map(int,input().split()))
N, K = inpl()
A = inpl()

L = K+1
M = len(bin(L))-2
MM = max(M, len(bin(max(A)))-2)
best = []
ones_num = []
zeros_num = []
for m in range(MM):
    ones = sum([ (A[i]>>m)&1 for i in range(N) ])
    zeros = N - ones
    ones_num.append(ones)
    zeros_num.append(zeros)
    if ones >= zeros:
        best.append(0)
    else:
        best.append(1)
cur = sum([ (N-ones_num[m] if (best[m] and m < M-1) else ones_num[m])<<m for m in range(MM)])
ans = cur
m = M - 1
while m > 0:
    cur += (zeros_num[m]-ones_num[m])<<m
    m -= 1
    while (L >> m)&1 == 0:
        if best[m] == 1:
            cur += (ones_num[m]-zeros_num[m])<<m
        m -= 1
        if m < 0:
            break
    else:
        if best[m] == 1:
            cur += (ones_num[m]-zeros_num[m])<<m
        if cur > ans:
            ans = cur
print(ans)
### BUGGY CODE ###

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

def is_prime(n):
    a = 0
    for k in range(1 + 1, int(math.sqrt(n)) + 1):
        if n % k == 0:
            a = 1
    if a == 1: return False
    else :return True

list = [1]
list.extend([i for i in range(1+1, min(A, B)+1) if A % i == 0 and B % i == 0 
and A % i != 2 and B % i != 2 
and A % i != 3 and B % i != 3 
and A % i != 5 and B % i != 5 
and A % i != 7 and B % i != 7 
and A % i != 11 and B % i != 11 
and A % i != 13 and B % i != 13 
and A % i != 17 and B % i != 17 
and A % i != 19 and B % i != 19 
and A % i != 23 and B % i != 23 
and A % i != 29 and B % i != 29 
and A % i != 31 and B % i != 31 
and A % i != 37 and B % i != 37 
and A % i != 41 and B % i != 41 
and A % i != 43 and B % i != 43 
and A % i != 47 and B % i != 47 
and A % i != 53 and B % i != 53 
and A % i != 59 and B % i != 59 
and A % i != 61 and B % i != 61 
and A % i != 67 and B % i != 67 
and A % i != 71 and B % i != 71 
and A % i != 73 and B % i != 73 
and A % i != 79 and B % i != 79 
and A % i != 83 and B % i != 83 
and A % i != 89 and B % i != 89 
and A % i != 97 and B % i != 97 
and A % i != 101 and B % i != 101 
and A % i != 103 and B % i != 103 
and A % i != 107 and B % i != 107 
and A % i != 109 and B % i != 109 
and A % i != 113 and B % i != 113 
and A % i != 127 and B % i != 127 
and A % i != 131 and B % i != 131 
and A % i != 137 and B % i != 137 
and A % i != 139 and B % i != 139 
and A % i != 149 and B % i != 149 
and A % i != 151 and B % i != 151 
and A % i != 157 and B % i != 157 
and A % i != 163 and B % i != 163 
and A % i != 167 and B % i != 167 
and A % i != 173 and B % i != 173 
and A % i != 179 and B % i != 179 
and A % i != 181 and B % i != 181 
and A % i != 191 and B % i != 191 
and A % i != 193 and B % i != 193 
and A % i != 197 and B % i != 197 
and A % i != 199 and B % i != 199 
and A % i != 211 and B % i != 211 
and A % i != 223 and B % i != 223 
and A % i != 227 and B % i != 227 
and A % i != 229 and B % i != 229 
and is_prime(i) == True])
print(len(list))

### FIXED CODE ###

A, B = map(int, input().split())
 
def gcd(a, b):  # a,bの最大公約数
    while b:
        a, b = b, a % b
    return a

def factorization(n):  # nを素因数分解
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1): 
        if temp % i == 0: # 割り切れるとき
            cnt = 0
            while temp % i == 0: # 割れる限りカウント
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1: # まだ因数があるとき
        arr.append([temp, 1])
    if arr == []: # ｎが1のとき
        arr.append([n, 1])
    return arr
 
g = gcd(A, B) 
ans = len(factorization(g))

if g != 1:
    ans += 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(m)]

pre = [[] for _ in range(n)]

for city in p:
    pre[city[0]-1].append(city[1])

for item in pre:
    item.sort()

for city in p:
    y = pre[city[0] - 1].index(city[1]) + 1
    print("{:0>6}{:0>6}".format(city[0],y))

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
p = [list(map(int, input().split()+[i])) for i in range(m)]

p.sort()
cnt = 0
pre = -1

for city in p:
    if city[0] == pre:
        cnt = cnt + 1
    else:
        pre = city[0]
        cnt = 1

    city.append("{:0>6}{:0>6}".format(city[0], cnt))

p.sort(key = lambda x: x[2])

for city in p:
    print(city[3])
### BUGGY CODE ###

def resolve():
    h, n = map(int, input().split())
    w = []
    v = []
    for i in range(n):
        a, b = map(int, input().split())
        w.append(a)
        v.append(b)
    dp = [[0 for i in range(h + 1)] for j in range(n + 1)]
    for i in range(1, h + 1):
        dp[0][i] = float("inf")
    for i in range(n):
        for j in range(h + 1):
            if j >= w[i]:
                dp[i + 1][j] = min(dp[i + 1][j - w[i]] + v[i], dp[i][j])
            else:
                dp[i + 1][j] = min(dp[i][j], v[i])
    print(dp[n][h])


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

def resolve():
    h, n = map(int, input().split())
    w = []
    v = []
    for i in range(n):
        a, b = map(int, input().split())
        w.append(a)
        v.append(b)
    dp = [[0 for i in range(h + 1)] for j in range(n + 1)]
    for i in range(1, h + 1):
        dp[0][i] = float("inf")
    for i in range(n):
        for j in range(h + 1):
            if j >= w[i]:
                dp[i + 1][j] = min(dp[i + 1][j - w[i]] + v[i], dp[i][j])
            else:
                dp[i + 1][j] = min(dp[i][j], v[i])
    # print(dp[n])
    print(dp[n][h])


if __name__ == '__main__':
    resolve()
### 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, Bで総当たり、上位K個をスタック
tmp = [a+b for a in A for b in B]
tmp.sort(reverse=True)
tmp = tmp[:K]

# 残りのc個に対しても総当たり
ans = [t+c for t in tmp for c in C]
ans.sort(reverse=True)
ans = ans[:K]

for s in ans:
    print(s)

### 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)

# まずA, Bで総当たり、上位K個をスタック
tmp = [a+b for a in A for b in B]
tmp.sort(reverse=True)
tmp = tmp[:K]

# 残りのc個に対しても総当たり
ans = [t+c for t in tmp for c in C]
ans.sort(reverse=True)
ans = ans[:K]
for s in ans:
    print(s)
### BUGGY CODE ###

s = input()
q = int(input())

u = []
for i in range(q):
    u.append(list(map(str,input().split())))

for i in range(q):
    if int(u[i][0]) == 1:
        s = s[::-1]
    else:
        if int(u[i][1]) == 1:
            s = u[i][2]+s
        else:
            s = s + u[i][2]

print(s)

### FIXED CODE ###

s = input()
q = int(input())

u = []
for i in range(q):
    u.append(list(map(str,input().split())))

from collections import deque
l = deque([])
r = deque([])

x = 1
for i in range(q):
    if int(u[i][0]) == 1:
        x = x*(-1)
    else:
        if int(u[i][1])*x == 1 or int(u[i][1])*x == -2:
            l.append(u[i][2])
        else:
            r.append(u[i][2])
if x == 1:
    print(''.join(l)[::-1]+s[::x]+''.join(r))
else:
    print(''.join(r)[::-1]+s[::x]+''.join(l))
### BUGGY CODE ###

X = int(input())
a = 1
flug = True
while flug:
    b = -119
    while b <= 118:
        if a ** 5 - b ** 5 == X:
            print(a, b)
            flug = False
            break
        else:
            b += 1


### FIXED CODE ###

X = int(input())
a = 1
flug = True
while flug:
    b = -119
    while b <= 118:
        if a ** 5 - b ** 5 == X:
            print(a, b)
            flug = False
            break
        else:
            b += 1
    a += 1
### BUGGY CODE ###

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

ANSWER = []
for i in range(N):
    A_ = A.copy()
    del A_[i]
    unique_i = list(set(A_))

    answer_i = 0
    for j in unique_i:
        answer_i += (A_.count(j) * (A_.count(j)-1)/2)
    
    ANSWER.append(int(answer_i))

for i in ANSWER:
    print(i)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
import numpy as np
 
N = int(readline())
A = np.array(read().split(), np.int64)
counter = np.bincount(A)
 
total = (counter * (counter - 1)).sum() // 2
answer = (total - (counter - 1))[A]
 
print('\n'.join(answer.astype(str)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
r, g, b, n = map(int, input().split())

result = 0
for i in range(n+1):
    r_sp = i*r
    if r_sp > n:
        break
    for j in range(n+1):
        g_sp = j*g
        if g_sp > n:
            break

        rg = r_sp + g_sp
        if rg > n:
            break

        if (n-rg) % b == 0:
            result += 1

print(result)


### FIXED CODE ###

# -*- coding: utf-8 -*-
r, g, b, n = map(int, input().split())

result = 0
for i in range(n+1):
    r_sp = i*r
    if r_sp > n:
        break
    for j in range(n+1):
        g_sp = j*g
        if g_sp > n:
            break

        rg = r_sp + g_sp
        if rg > n:
            break

        if (n-rg) % b == 0:
            result += 1

print(result)
### BUGGY CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
H, W = list(map(int, input().split()))
L = [True if j == "#" else False for i in range(H) for j in input()]
all_count = H * W
blacks = [i for i in range(all_count) if L[i]]
#print(blacks)
black_count = len(blacks)

cands_H = [-W, W]
cands_W = [-1, 1]
result = 0
while black_count < all_count:
  next_steps = set([black+cand for black in blacks for cand in cands_H]) | set([black+cand for black in blacks for cand in cands_W if black%W not in [0, W-1]])
  blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
  for i in blacks:
    L[i] = True
  black_count += len(blacks)
  #print(blacks)
  result += 1

print(result)


### FIXED CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．
from collections import deque
import copy

def main():
  H, W = list(map(int, input().split()))
  L = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
  cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  result = 0
  while True:
    nq = deque()
    while q:
      i, j = q.popleft()
      if i > 0 and not L[i-1][j]:
        L[i-1][j] = True
        nq.append((i-1, j))
      if j > 0 and not L[i][j-1]:
        L[i][j-1] = True
        nq.append((i, j-1))
      if i < H-1 and not L[i+1][j]:
        L[i+1][j] = True
        nq.append((i+1, j))
      if j < W-1 and not L[i][j+1]:
        L[i][j+1] = True
        nq.append((i, j+1))
    if nq:
      q = copy.copy(nq)
    else:
      break    
    result += 1
  print(result)

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

import sys
def rec(N,dp,i,j,k):
    if dp[i][j][k]>=0.0:return dp[i][j][k]
    if all([i==0,j==0,k==0]):return 0.0
    res=0.0
    if i>0:res+=rec(N,dp,i-1,j,k)*i
    if j>0:res+=rec(N,dp,i+1,j-1,k)*j
    if k>0:res+=rec(N,dp,i,j+1,k-1)*k
    res+=N
    res*=1.0/(i+j+k)
    dp[i][j][k]=res
    return dp[i][j][k]
def main():
    N=int(sys.stdin.readline())
    a=tuple(map(int,sys.stdin.readline().split()))
    n1,n2,n3=a.count(1),a.count(2),a.count(3)
    dp=[[[-1.0 for _ in range(n3+1)] for _ in range(n2+n3+1)] for _ in range(n1+n2+n3+1)]
    print(rec(N,dp,n1,n2,n3))
if __name__=='__main__':main()


### FIXED CODE ###

import sys
def rec(N,dp,i,j,k):
    if dp[i][j][k]>=0.0:return dp[i][j][k]
    if all([i==0,j==0,k==0]):return 0.0
    res=0.0
    if i>0:res+=rec(N,dp,i-1,j,k)*i
    if j>0:res+=rec(N,dp,i+1,j-1,k)*j
    if k>0:res+=rec(N,dp,i,j+1,k-1)*k
    res=(res+N)*1.0/(i+j+k)
    dp[i][j][k]=res
    return dp[i][j][k]
def main():
    N=int(sys.stdin.readline())
    a=tuple(map(int,sys.stdin.readline().split()))
    n1,n2,n3=a.count(1),a.count(2),a.count(3)
    dp=[[[-1.0 for _ in range(n3+1)] for _ in range(n2+n3+1)] for _ in range(n1+n2+n3+1)]
    print(rec(N,dp,n1,n2,n3))
if __name__=='__main__':main()