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

import bisect
from itertools import permutations
A, B, Q = map(int, input().split())
S = []
for _ in range(A):
    S.append(int(input()))
T = []
for _ in range(B):
    T.append(int(input()))

for _ in range(Q):
    x = int(input())
    sr = bisect.bisect_right(S, x)
    tr = bisect.bisect_right(T, x)
    c = []
    if sr == A:
        c.append([S[A-1], 0])
    elif sr == 0:
        c.append([S[sr], 0])
    else:
        c.append([S[sr], 0])
        c.append([S[sr-1], 0])
    if tr == B:
        c.append([T[B-1], 1])
    elif tr == 0:
        c.append([T[tr], 1])
    else:
        c.append([T[tr], 1])
        c.append([T[tr-1], 1])
    ans = 10**16
    for elem in permutations(c):
        tmp = 0
        flag = [False, False]
        now_pos = x
        flag_calc = True
        for pos, kind in elem:
            if flag[kind]:
                flag_calc = False
                break
            tmp += abs(pos-now_pos)
            now_pos = pos
            flag[kind] = True
            if flag[0] and flag[1]:
                break
        if flag_calc:
            ans = min(ans, tmp)
    print(ans)


### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
S = []
for _ in range(A):
    S.append(int(input()))
T = []
for _ in range(B):
    T.append(int(input()))

for _ in range(Q):
    x = int(input())
    sr = bisect.bisect_right(S, x)
    tr = bisect.bisect_right(T, x)
    tmpS = []
    tmpT = []
    if sr == A:
        tmpS.append(S[A-1])
    elif sr == 0:
        tmpS.append(S[sr])
    else:
        tmpS.append(S[sr])
        tmpS.append(S[sr-1])
    if tr == B:
        tmpT.append(T[B-1])
    elif tr == 0:
        tmpT.append(T[tr])
    else:
        tmpT.append(T[tr])
        tmpT.append(T[tr-1])
    ans = 10**16
    for s in tmpS:
        tmp = abs(x-s)
        tmp1 = 10**16
        for elemT in tmpT:
            tmp1 = min(tmp1, abs(elemT-s))
        ans = min(ans, tmp+tmp1)
    for t in tmpT:
        tmp = abs(x-t)
        tmp1 = 10**16
        for elemS in tmpS:
            tmp1 = min(tmp1, abs(elemS-t))
        ans = min(ans, tmp+tmp1)
    print(ans)
### BUGGY CODE ###

def BFS(x):
  cnt=0
  v=deque([x])
  zu=[ -1 for _ in range(N)] #訪問済みリスト
  k=0
  zu[x]=k
  
  while len(v)>0:
    a=v.popleft()
    for i in fr[a]:
      if zu[i]==-1:
        zu[i]=zu[a]+1
        v.append(i)
        if zu[i]>1 and (i not in bl[x]):
          cnt +=1            
  return cnt

##############################

from collections import deque
N,M,K=map(int,input().split())
A=[0]*M
B=[0]*M
C=[0]*K
D=[0]*K
fr=[ [] for _ in range(N)]
bl=[ set() for _ in range(N)]

for i in range(M):
  A[i],B[i]= map(int,input().split())
  fr[A[i]-1].append(B[i]-1)
  fr[B[i]-1].append(A[i]-1)
for k in range(K):
  C[k],D[k]= map(int,input().split())
  bl[C[k]-1].add(D[k]-1)
  bl[D[k]-1].add(C[k]-1)

ans=[]  
for i in range(N):
  ans.append(BFS(i))
print(*ans)

### FIXED CODE ###

def BFS(x):
  cnt=1
  v=deque([x])
  k=0
  zu[x]=k
  lis=[x]
  roots[x]=x
  
  while len(v)>0:
    a=v.popleft()
    roots[a]=x
    for i in fr[a]:
      if zu[i]==-1:
        zu[i]=zu[a]+1
        v.append(i)
        cnt += 1
        lis.append(i)

          
  return lis

##############################

from collections import deque
N,M,K=map(int,input().split())
A=[0]*M
B=[0]*M
C=[0]*K
D=[0]*K
fr=[ [] for _ in range(N)]
bl=[ set() for _ in range(N)]
zu=[ -1 for _ in range(N)] #訪問済みリスト
roots= [ -1 for _ in range(N)]

for i in range(M):
  A[i],B[i]= map(int,input().split())
  fr[A[i]-1].append(B[i]-1)
  fr[B[i]-1].append(A[i]-1)
for k in range(K):
  C[k],D[k]= map(int,input().split())
  bl[C[k]-1].add(D[k]-1)
  bl[D[k]-1].add(C[k]-1)
fr_set= [set(fr[i]) for i in range(N)]
    
size=[0]*N
pena=[0]*N
for i in range(N):
  if zu[i]==-1:
    kumi=BFS(i) #リスト
    for k in range(len(kumi)):
      size[kumi[k]]=len(kumi)
      
      
ans=[0 for _ in range(N)]      
for i in range(N):
  ans[i]= size[i]-1 - len(fr[i])
  for j in bl[i]:
    if roots[j]==roots[i]:
      ans[i] -= 1      
      
print(*ans)
### BUGGY CODE ###

from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft

def nxt(x):
    i = 0
    cnt = 0
    while x >= 1<<i:
        if x & (1<<i):
            cnt += 1
        i += 1
    return x % cnt


def count(x):
    s = 0
    while x != 0:
        s += 1
        x = nxt(x)
    return s

def main():
    n = int(input())
    x = input()
    x = int(x, 2)
    for i in range(n):
        y = x ^ (1<<(n-i-1))
        s = count(y)
        print(s)


main()


### FIXED CODE ###

from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


memo = {}

def countbit(x):
    i = 0
    cnt = 0
    while x >= 1<<i:
        if x & (1<<i):
            cnt += 1
        i += 1
    return cnt


def count(x):
    # if c == 0:
    #     return 0
    # s = 1
    # x = x % c
    s = 0
    while x != 0:
        s += 1
        x = x % countbit(x)
    return s

def main():
    n = int(input())
    xs = list(input())
    c = len([i for i in xs if i == '1'])
    dp = {}
    dps = {}
    for i in range(-1, 2):
        cc = c + i
        if cc == 0:
            continue
        dp[cc] = [-1] * n
        base = 1 % cc
        dpstmp = 0
        for i in range(n):
            dp[cc][i] = base
            if xs[-i-1] == '1':
                dpstmp += base
            base = base * 2 % cc
        dps[cc] = dpstmp % cc

    for i in range(n):
        cc = c
        if xs[i] == '1':
            cc -= 1
        else:
            cc += 1
        if cc == 0:
            print(0)
            continue
        res = dps[cc]
        if xs[i] == '1':
            res = (res - dp[cc][-i-1]) % cc
        else:
            res = (res + dp[cc][-i-1]) % cc
        s = count(res) + 1
        print(s)


main()
### BUGGY CODE ###

def C_pushpush(x):
    n = int(x[0])
    a = x[1:]
    b = []
    n_parity = n & 1
    for i in range(n):
        if n_parity == (i + 1) & 1:
            # n,iのパリティが一致
            b.insert(0, a[i])
        else:
            b.append(a[i])
    print(' '.join(b))

n = input()
l = [i for i in input().split()]
x = [n]+l
C_pushpush(x)

### FIXED CODE ###

def C_pushpush(x):
    from collections import deque
    # insertをリストの先頭に行うと、リストの要素の再配置に時間がかかる
    n = int(x[0])
    a = deque(x[1:])
    b = deque([])
    n_parity = n & 1
    for i in range(n):
        if n_parity == (i + 1) & 1:
            # n,iのパリティが一致
            b.appendleft(a[i])
        else:
            b.append(a[i])
    print(' '.join(b))

n = input()
l = [i for i in input().split()]
x = [n]+l
C_pushpush(x)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# input
n = int(input())
a_list = list(map(int, input().split()))

a_count_list = []

a_dic = {}

for i in range(len(a_list)):
    key = a_list[i]
    if key in a_dic:
        a_dic[key] += 1
    else:
        a_dic[key] = 1


for k, ak in enumerate(a_list):
    sum_select = 0
    for key in a_dic:
        if ak == key:
            temp_a_num = a_dic[ak] - 1
            sum_select += int(temp_a_num * (temp_a_num-1) / 2)
        else:
            sum_select += int(a_dic[key] * (a_dic[key]-1) / 2)

    print(sum_select)


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# input
n = int(input())
a_list = []
a_dic = {}
for ai in input().split():
    int_ai = int(ai)
    a_list.append(int_ai)
    if int_ai in a_dic:
        a_dic[int_ai] += 1
    else:
        a_dic[int_ai] = 1

a_solution_dic = {}
all_sum_select = 0
for key in list(a_dic.keys()):
    all_sum_select += int(a_dic[key] * (a_dic[key]-1) / 2)
    #a_solution_dic_at_k[key] = int((a_dic[key]-1) * (a_dic[key]-2) / 2)

for k, ak in enumerate(a_list):
    sum_select_at_k = all_sum_select + int((a_dic[ak]-1) * (a_dic[ak]-2) / 2) \
                       - int(a_dic[ak] * (a_dic[ak]-1) / 2)


    print(sum_select_at_k)
### BUGGY CODE ###

from sys import stdin

import numpy as np

U = 10 ** 6 + 10


def main():
    _, primes = prime_table(U)
    readline = stdin.readline
    N = int(readline())
    a = list(map(int, readline().split()))
    mat = np.zeros(U + 1, np.int64)
    ret = 0
    for x in a:
        mat[x] += 1
    for p in primes:
        for i in range(U // p + 1):
            mat[p * i] += mat[i]
    for x in a:
        ret += mat[x] == 1
    print(ret)
    '''
    N = int(readline())
    a = list(map(int, readline().split()))
    a = np.sort(a)
    count = 0
    idxes = np.arange(len(a))
    while len(idxes):
        idx = idxes[0]
        idxes = np.delete(idxes, 0)
        var = a[idx]
        if len(np.where(a[idxes] == var)[0]) == 0:
            count += 1
        idxes = idxes[np.where(a[idxes] % var != 0)[0]]
    print(count)
    '''


def prime_table(N):
    is_prime = np.zeros(N, np.int64)
    is_prime[2] = 1
    is_prime[3::2] = 1
    for p in range(3, N, 2):
        if p * p >= N:
            break
        if is_prime[p]:
            is_prime[p * p::p + p] = 0
    return is_prime, np.where(is_prime)[0]


main()


### FIXED CODE ###

from sys import stdin

import numpy as np

U = 10 ** 6 + 10


def main():
    readline = stdin.readline
    N = int(readline())
    a = list(map(int, readline().split()))
    ret = 0
    exist_counts = [0] * U
    for x in a:
        if exist_counts[x]:
            exist_counts[x] = 2
            continue
        idx = x
        while idx < U:
            exist_counts[idx] += 1
            idx += x
    for x in a:
        ret += exist_counts[x] == 1
    print(ret)
main()
### BUGGY CODE ###

n,w = map(int,input().split())
dp = [[0 for x in range(w+1)] for x in range(n+1)]
array = [[int(x) for x in input().split()] for x in range(n)]
for i in range(1,w+1):
    for j in range(1,n+1):
        if(array[j-1][0] > i):
            dp[j][i] = dp[j-1][i]
        else:
            if(dp[j-1][i] < dp[j-1][i-array[j-1][0]] + array[j-1][1]):
                dp[j][i] = dp[j-1][i-array[j-1][0]] + array[j-1][1]
            else:
                dp[j][i] = dp[j-1][i]
print(dp[-1][-1])


### FIXED CODE ###

n,w = map(int,input().split())
dp = [[0 for x in range(w+1)] for x in range(n+1)]
array = [[int(x) for x in input().split()] for x in range(n)]
for i in range(1,w+1):
    for j in range(1,n+1):
        if(array[j-1][0] > i):
            dp[j][i] = dp[j-1][i]
        else:
            if(dp[j-1][i] < dp[j-1][i-array[j-1][0]] + array[j-1][1]):
                dp[j][i] = dp[j-1][i-array[j-1][0]] + array[j-1][1]
            else:
                dp[j][i] = dp[j-1][i]
print(dp[-1][-1])
### BUGGY CODE ###

n = int(input())
boss = list(map(str, input().split()))
for i in range(1, n + 1):
    print(boss.count(str(i)))

### FIXED CODE ###

n = int(input())
boss = list(map(str, input().split()))
ans = [0] * n
for b in boss:
    ans[int(b) - 1] += 1
for a in ans:
    print(a)
### BUGGY CODE ###

S=list(input())
mod=2019
S=list(reversed(S))
N=len(S)
A=[0]*(N)
p=1
for i in range(N):
    p=(10**i)%mod
    now=(int(S[i])*p)%mod
    A[i]=now
    #print(now)
rui=[0]*(N+1)
for i in range(1,N+1):
    rui[i]=(rui[i-1]+A[i-1])%mod
total=[0]*2019
for r in rui:
    total[r]+=1
ans=0
for t in total:
    ans+=t*(t-1)//2
print(ans)


### FIXED CODE ###

S=input()
N=len(S)
R=[0]*(N+1)
mul=1
for i in range(1,N+1):
    R[-(i+1)]=(((int(S[-i])*mul))%(2019)+R[-i])%2019
    mul*=10
    mul%=2019
#print(R)
L=[0]*2019
for r in R:
    L[r]+=1
ans=0
for l in L:
    if l>=2:
        ans+=l*(l-1)//2
print(ans)
### BUGGY CODE ###

import numpy as np
import math
N,a,b = np.array(input().split()).astype(int)
S = 0
for i in range(1,N+1):
  if((i!=a)&(i!=b)):
    S += math.factorial(N)//(math.factorial(i)*math.factorial(N-i))
print(S%(10**9+7))

### FIXED CODE ###

import numpy as np
N,a,b = np.array(input().split()).astype(int)
mod = 10**9+7
def power(x, n):
    ans = 1
    while(n > 0):
        if(bin(n & 1) == bin(1)):
            ans = ans*x%mod
        x = (x*x)%mod
        n = n >> 1 #ビットシフト
    return ans
def fact(m, n):
    val = 1
    for i in range(m, n+1):
        val = val*i % mod
    return val
    
def cmb1(N, r):
    A = fact(N-r+1, N)%mod
    B = fact(1, r)%mod
    return A, B, (A*power(B, mod-2))%mod
def cmb2(a, b, A, B):
    A = fact(N-a+1, N-b)*A%mod
    B = fact(b+1, a)*B%mod
    return (A*power(B, mod-2))%mod
if(a>N//2):
    a = N-a
if(b>N//2):
    b = N-b
tmp = max(a,b)
b = min(a,b)
a = tmp
A, B, K1 = cmb1(N, b)
K2 = cmb2(a, b, A, B)
print((power(2, N)-1-K1-K2)%mod)
### BUGGY CODE ###

n, k = map(int, input().split())
H = sorted([int(input()) for _ in range(n)])

ans = 10e10
for i in range(n - k + 1):
    select = H[i: i + k]
    ans = min(ans, select[-1] - select[0])

print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
H = sorted([int(input()) for _ in range(n)])
ans = 10e10
for i in range(n - k + 1):
    ans = min(ans, H[i + k - 1] - H[i])

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
for m in range(M):
    B, C = map(int, input().split())
    NA = A + [C for i in range(B)]
    NA.sort()
    NA = NA[B:]
    A = NA
print(sum(A))


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
p = [(A[i], 1) for i in range(N)]
for m in range(M):
    B, C = map(int, input().split())
    p.append((C, B))

p.sort()
p.reverse()

ans = 0
for v, n in p:
    use = min(N, n)
    ans += use * v
    N -= use
    if N == 0:
        break
print(ans)
### BUGGY CODE ###

import sys
import math
N, H = map(int, input().split())

a = []
b = []
num_attack = 0

for _ in range(N):
	a_i, b_i = map(int, input().split())
	a.append(a_i)
	b.append(b_i)
max_a = max(a)
Strong_b = [b_i for b_i in b if b_i > max_a]

if sum(Strong_b) >= H:

	while H > 0:

		H -= max(Strong_b)
		max_index = Strong_b.index(max(Strong_b))
		Strong_b[max_index] = 0
		num_attack += 1	
		
	print(num_attack)
	sys.exit()

H -= sum(Strong_b)
num_attack = len(Strong_b) + math.ceil(H/max_a)
print(num_attack)


### FIXED CODE ###

import sys
import math
N, H = map(int, input().split())

a = []
b = []
num_attack = 0

for _ in range(N):
	a_i, b_i = map(int, input().split())
	a.append(a_i)
	b.append(b_i)
max_a = max(a)
Strong_b = [b_i for b_i in b if b_i > max_a]

if sum(Strong_b) >= H:
	Strong_b = sorted(Strong_b, reverse = True)
	for i in range(N):
		H -= Strong_b[i]
		if H <= 0:
			print(i+1)
			sys.exit()

H -= sum(Strong_b)
num_attack = len(Strong_b) + math.ceil(H/max_a)
print(num_attack)
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import *
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    def dfs(x):
        if dp[x] is not None: return dp[x]
        dx = d[x]
        for e in edg[x]:
            dx.append(dfs(e))
        if dx == []:
            dp[x] = 0
            return 0
        dp[x] = max(1 + i + v for i, v in enumerate(sorted(dx, reverse=1)))
        return dp[x]
    
    n = II()
    edg = [[] for _ in range(n)]
    dp = [None] * n
    d = [[] for _ in range(n)]
    for i in range(n - 1):
        a = II() - 1
        edg[a].append(i + 1)
    print(dfs(0))
    return


#main
if __name__ == '__main__':
    solve()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import *
from bisect import bisect_left, bisect_right
import sys
sys.setrecursionlimit(2147483647)
input = sys.stdin.readline
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10
input=lambda:sys.stdin.readline().rstrip()
#solve
def solve():

    n = int(input())
    edg = [[] for _ in range(n)]
    dp = [None] * n
    for i in range(1,n):
        u = int(input()) - 1
        edg[u].append(i)
        edg[i].append(u)

    def dfs(v,p=-1)->int:
        if (dp[v] is not None): return dp[v]
        if (edg[v] == [p]):
            dp[v] = 0
            return 0
        tmp = []
        for nv in edg[v]:
            if (nv == p): continue
            tmp.append(dfs(nv,v))
        dp[v] = max(1 + i + x for i, x in enumerate(sorted(tmp, reverse=1)))
        return dp[v]
    
    print(dfs(0))
    return


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

def solve(c, sushis):
    clockwise = solve_one_direction(c, sushis, True)
    counter = solve_one_direction(c, sushis[::-1], False)
    return max(clockwise, counter)

def solve_one_direction(c, sushis, clockwise=True, already_turn=False):
    total_v = 0
    max_v = 0
    for i, sushi in enumerate(sushis):
        total_v += sushi[1]
        x = sushi[0] if clockwise else c - sushi[0]
        v = total_v - x
        if max_v < v:
            max_v = v
        if not already_turn and x <= c / 2:
            rev = v - x + solve_one_direction(c, sushis[i + 1::][::-1], not clockwise, True)
            if max_v < rev:
                max_v = rev

    return max_v


n, c = map(int, input().split())
sushis = []
for _ in range(n):
    sushis.append([int(x) for x in input().split()])
print(solve(c, sushis))


### FIXED CODE ###

def solve(c, sushis):
    cw_maxs, cw_rets = create_accs(sushis, c, True)
    ccw_maxs, ccw_rets = create_accs(reversed(sushis), c, False)
    cw_max = cw_maxs[-1]
    ccw_max = ccw_maxs[-1]
    cw_ccw_max = turn_max(cw_rets, ccw_maxs)
    ccw_cw_max = turn_max(ccw_rets, cw_maxs)
    return max(cw_max, ccw_max, cw_ccw_max, ccw_cw_max)


def turn_max(rets, maxs):
    m = 0
    for i, r in enumerate(rets):
        ind = len(maxs) - 2 - i
        add = maxs[ind] if ind >= 0 else 0
        v = r + add
        if m < v:
            m = v
    return m


def create_accs(sushis, c, cw):
    maxs, vs_ret = [], []
    v_sum, v_max = 0, 0
    for d, v in sushis:
        v_sum += v
        dist = d if cw else c - d
        v_cur = v_sum - dist
        if v_max < v_cur:
            v_max = v_cur
        maxs.append(v_max)
        vs_ret.append(v_sum - dist*2)
    return maxs, vs_ret


n, c = map(int, input().split())
sushis = []
for _ in range(n):
    sushis.append([int(x) for x in input().split()])
print(solve(c, sushis))
### BUGGY CODE ###

H, W = map(int, input().split())
A = tuple(tuple(input()) for _ in range(H))
next_q = [(i, j) for i in range(H) for j in range(W) if A[i][j] == '#']
L = [[0] * W for _ in range(H)]

res = 0
while len(next_q) != 0:
    q, next_q = next_q[:], []
    while len(q) != 0:
        y, x = q.pop(0)
        if y > 0 and L[y - 1][x] == 0:
            L[y - 1][x] = 1
            next_q.append((y - 1, x))
        if y < H - 1 and L[y + 1][x] == 0:
            L[y + 1][x] = 1
            next_q.append((y + 1, x))
        if x > 0 and L[y][x - 1] == 0:
            L[y][x - 1] = 1
            next_q.append((y, x - 1))
        if x < W - 1 and L[y][x + 1] == 0:
            L[y][x + 1] = 1
            next_q.append((y, x + 1))
    if len(next_q) == 0: break
    res += 1
print(res)


### FIXED CODE ###

from collections import deque
import copy
H, W = map(int, input().split())
A = tuple(tuple(input()) for _ in range(H))
L=[[0]*W for _ in range(H)]
next_q=deque()

for i in range(H):
    for j in range(W):
        if A[i][j]=='#':
            L[i][j]=1
            next_q.append((i,j))

q=deque()

res = 0
while len(next_q) != 0:
    q=copy.copy(next_q)
    next_q.clear()
    while q:
        y, x = q.popleft()
        if y > 0 and L[y - 1][x] == 0:
            L[y - 1][x] = 1
            next_q.append((y - 1, x))
        if y < H - 1 and L[y + 1][x] == 0:
            L[y + 1][x] = 1
            next_q.append((y + 1, x))
        if x > 0 and L[y][x - 1] == 0:
            L[y][x - 1] = 1
            next_q.append((y, x - 1))
        if x < W - 1 and L[y][x + 1] == 0:
            L[y][x + 1] = 1
            next_q.append((y, x + 1))
    if len(next_q)==0: break
    res += 1
print(res)
### BUGGY CODE ###

mod = 10**9+7
n,m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))
a.append(0)
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1) :
    dp[i] = (dp[i-1] + dp[i-2])%mod
    if a[0] == i :
        dp[i] = 0
        a.pop(0)
print(dp[-1])

### FIXED CODE ###

mod = 10**9+7
n,m = map(int,input().split())
a = set()
for i in range(m):
    a.add(int(input()))
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1) :
    dp[i] = (dp[i-1] + dp[i-2]) % mod
    if i in a :
        dp[i] = 0
print(dp[n])
### BUGGY CODE ###

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

ans = 1

for a in A:
    ans *= a

if ans > 10**18:
    print("-1")
else:
    print(ans)

### FIXED CODE ###

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

ans = 1

for a in A:
    ans *= a
    if ans > 10**18:
        ans = -1
        break

if 0 in A:
    ans = 0

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

K,S=map(int, input().split())
n=0
for x in range(K+1):
    for y in range (K+1):
        for z in range(K+1):
            if x+y+z==S:
                n+=1
print(n)

### FIXED CODE ###

K,S=map(int, input().split())
n=0
for x in range(K+1):
    for y in range (K+1):
        if 0<=S-x-y<=K:
                n+=1
print(n)
### BUGGY CODE ###

while 1:
    try:
        y = 4.9 * (float(input()) / 9.8) ** 2
        N = 1
        while N * 5 - 5 < y:
            N += 1
        print(N)
    except:
        pass

### FIXED CODE ###

try:
    while 1:
        y = 4.9 * (float(input()) / 9.8) ** 2
        N = 1
        while N * 5 - 5 < y:
            N += 1
        print(N)
except:
    pass
### BUGGY CODE ###

N,M = map(int, raw_input().split())
A = list(map(int,raw_input().split()))	
ans = 0
for i in range(0,M):
  max_A_index = A.index(max(A))
  A[max_A_index] = A[max_A_index]/2
print sum(A)

### FIXED CODE ###

import heapq

N,M = map(int, raw_input().split())
A = list(map(lambda x: int(x)*(-1), raw_input().split()))

heapq.heapify(A)

for i in range(0,M):
  max_A = heapq.heappop(A)*(-1) / 2*(-1)
  heapq.heappush(A,max_A)

print sum(A)*(-1)