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

def divisors(M):#Mの約数列 O(n^(0.5+e))
    import math
    d=[]
    i=1
    while math.sqrt(M)>=i:
        if M%i==0:
            d.append(i)
            if i**2!=M:
                d.append(M//i)
        i=i+1
    d.sort()
    return d

N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
A=[a[i]^a[i-1] for i in range(0,N)]
B=[b[i]^b[i-1] for i in range(0,N)]
d=divisors(N)
perioda=N
for i in range(0,len(d)):
    test=[A[(j+d[i])%N] for j in range(0,N)]
    if test==A:
        perioda=min(perioda,d[i])

periodb=N
for i in range(0,len(d)):
    test=[B[(j+d[i])%N] for j in range(0,N)]
    if test==B:
        periodb=min(periodb,d[i])

if perioda==periodb:
    A=A[:perioda]
    B=B[:periodb]
    kouho=[]
    for i in range(0,len(B)):
        if A[i]==B[0]:
            kouho.append(i)
    ans=-1
    for i in range(0,len(kouho)):
        test=[A[(j+kouho[i])%perioda] for j in range(0,perioda)]
        if test==B:
            ans=kouho[i]
            break
    if ans!=-1:
        for i in range(0,N//perioda):
            print(ans+perioda*i,a[ans+perioda*i]^b[0])

### FIXED CODE ###

def divisors(M):#Mの約数列 O(n^(0.5+e))
    import math
    d=[]
    i=1
    while math.sqrt(M)>=i:
        if M%i==0:
            d.append(i)
            if i**2!=M:
                d.append(M//i)
        i=i+1
    d.sort()
    return d

import numpy as np
N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
A=np.array([a[i]^a[i-1] for i in range(0,N)])
B=np.array([b[i]^b[i-1] for i in range(0,N)])
d=divisors(N)
perioda=N
for i in range(0,len(d)):
    test=np.roll(A,-d[i])
    if all(test==A):
        perioda=min(perioda,d[i])

periodb=N
for i in range(0,len(d)):
    test=np.roll(B,-d[i])
    if all(test==B):
        periodb=min(periodb,d[i])

if perioda==periodb:
    A=A[:perioda]
    B=B[:periodb]
    kouho=[]
    for i in range(0,len(B)):
        if A[i]==B[0]:
            kouho.append(i)
    ans=-1
    for i in range(0,len(kouho)):
        test=np.roll(A,-kouho[i])
        if all(test==B):
            ans=kouho[i]
            break
    if ans!=-1:
        for i in range(0,N//perioda):
            print(ans+perioda*i,a[ans+perioda*i]^b[0])
### BUGGY CODE ###

s = input()
k = int(input())
def ss(s,k):
    M=len(s)
    sss=set()
    for i in range(M):
        for j in range(i+1,M+1):
            tmp = s[i:j]
            sss.add(tmp)
    l = list(sss)
    l.sort()
    #print(l)
    ret = l[k-1]
    return(ret)
 
res=ss(s,k)
print(res)

### FIXED CODE ###

s = input()
k = int(input())

M=len(s)
sss=set()
for i in range(M):
    for j in range(i+1,i+k+1):
        tmp = s[i:j]
        sss.add(tmp)
l = list(sss)
l.sort()
print(l[k-1])
### BUGGY CODE ###

n,k = map(int,input().split())
arr = [int(i) for i in input().split()]
dp = [0 for j in range(n)]
for i in range(1,n):
    mins = float("inf")
    for j in range(1,k+1):
        val = (abs(arr[i]-arr[i-j]) + dp[i-j]) if i-j >=0  else float("inf")
        mins = min(mins,val)
    dp[i] = mins
print(dp[n-1])


### FIXED CODE ###

n,k = map(int,input().split())
arr = [int(i) for i in input().split()]
dp = [float("inf")] * n
dp[0] = 0
for i in range(n):
    for j in range(i+1,i+k+1):
        if j < n:
            dp[j] = min(dp[j],abs(arr[i]-arr[j]) + dp[i])
print(dp[n-1])
### BUGGY CODE ###

k = int(input())
lunlun = list(range(1, 10))

for i in range(k-1):
    a = lunlun.pop(0)
    if a % 10 != 0:
        lunlun.append(a * 10 + a % 10 - 1)
    lunlun.append(a * 10 + a % 10)
    if a % 10 != 9:
        lunlun.append(a * 10 + a % 10 + 1)

print(lunlun.pop(0))

### FIXED CODE ###

k = int(input())
lunlun = list(range(1, 10))

for i in range(k-1):
    a = lunlun[i]
    b = a * 10 +  a % 10 
    if a % 10 != 0:
        lunlun.append(b - 1)
    lunlun.append(b)
    if a % 10 != 9:
        lunlun.append(b + 1)

print(lunlun[k-1])
### BUGGY CODE ###

from scipy.misc import comb
n = int(input())
h = list(map(int, input().split()))
def triangle(n,h):
    x = comb(n, 3, exact = True)
    for i in range(0,n-2):
        for j in range(i+1,n-1):
            for k in range(j+1, n):
                if h[i] >= h[j] + h[k] or h[j] >= h[i] + h[k] or h[k] >= h[j] + h[i]:
                    x = x - 1
    return x
print(triangle(n,h))

### FIXED CODE ###

import bisect
N = int(input())
#ソートしておく
L = sorted(list(map(int, input().split())))
ans = 0
 
#短い2辺を総当たりで選択
for i in range(N - 2):
  for j in range(i + 1, N - 1):
    #小さい順に並べた時の成立条件
    # l1 + l2 > l3
    l12 = L[i] + L[j]
    #l2の隣から　l12以下のところまで全部が対象、成立しない場合
    #ans += max(bisect.bisect_left(L, l12) - j - 1, 0)
    ans += bisect.bisect_left(L, l12) - j - 1
print(ans)
### BUGGY CODE ###

from collections import deque

d = deque()

d.extend(list(input()))

q = int(input())

headflag = 0

for i in range(q):
    s = input()
    if len(s) == 1:
        if headflag == 0:
            headflag = 1
        else:
            headflag = 0
    else:
        l = list(s)
        if headflag == 0:
            if l[2] == '1':
                d.appendleft(l[4])
            else:
                d.append(l[4])
        else:
            if l[2] == '2':
                d.appendleft(l[4])
            else:
                d.append(l[4])

dl = len(d)

if headflag == 0:
    for i in range(len(d)):
        print(d[i], end='')
else:
    for i in range(len(d)):
        print(d[dl-1-i], end='')

print()


### FIXED CODE ###

from collections import deque

d = deque(input())

q = int(input())

headflag = 0

for i in range(q):
    s = input()
    if len(s) == 1:
        if headflag == 0:
            headflag = 1
        else:
            headflag = 0
    else:
        l = list(s)
        if headflag == 0:
            if l[2] == '1':
                d.appendleft(l[4])
            else:
                d.append(l[4])
        else:
            if l[2] == '2':
                d.appendleft(l[4])
            else:
                d.append(l[4])

result = ''.join(d)

if headflag == 0:
    print(result)
else:
    result = result[::-1]
    print(result)

print()
### BUGGY CODE ###

from collections import Counter

N = int(input())
D = list(map(int, input().split()))
M = int(input())
T = list(map(int, input().split()))

Dnew = [elem for elem in D if elem in T]

c1 = Counter(Dnew)
c2 = Counter(T)

flag = True
for key in c2:
    if c2[key] > c1[key]:
        flag = False
        break

if flag:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

from collections import Counter, defaultdict

N = int(input())
D = list(map(int, input().split()))
M = int(input())
T = list(map(int, input().split()))

memo = defaultdict(int)
for d in D:
    memo[d] += 1

for i in range(M):
    ti = T[i]
    if ti not in memo:
        print("NO")
        exit()
    if memo[ti] == 0:
        print("NO")
        exit()
    memo[ti] -= 1

print("YES")
### BUGGY CODE ###

#python3

def main():
    h, w = map(int, input().split())
    ss = []
    for _ in range(h):
        s = input()
        ss.append(s)

    sumh = [[0 for _ in range(w)] for _ in range(h)]
    #横方向について連続で何マス続くかを求める
    for i in range(h):
        for j in range(w):
            #i,jはぞれぞれ縦と横のマスの位置を表すインデックス
            #doneは連続何マス続くかをすでに求めたかどうかを保持するリスト　
            done = [0 for _ in range(w)]
            if ss[i][j] == '#':
                continue
            if done[j] == 1:
                continue
            #seqは横に何マス続くかを記録する変数
            seq = 0
            while j + seq < w:
                if ss[i][j+seq] == '#':
                    break
                seq = seq + 1
            #ss[i][j]からss[i][j+seq]までのマスは連続してseqマスである
            for k in range(seq):
                if sumh[i][j+k] != 0:
                    continue
                sumh[i][j+k] += seq
                #連続するマスが求め終わったマスを記録する
                done[j+k] = 1
    
    #縦方向について同様に
    sumv = [[0 for _ in range(w)] for _ in range(h)]
    for j in range(w):
            for i in range(h):
                done = [0 for _ in range(h)]
                if ss[i][j] == '#':
                    continue
                if done[i] == 1:
                    continue
                seq = 0
                while i + seq < h:
                    if ss[i+seq][j] == '#':
                        break
                    seq = seq + 1
                for k in range(seq):
                    if sumv[i+k][j] != 0:
                        continue
                    sumv[i+k][j] += seq
                    done[i+k] = 1

    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, sumh[i][j]+sumv[i][j]-1)            
    print(ans)
main()




### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np 
import itertools as it
def main():
    H, W = map(int, readline().split())
    G = np.zeros((H+2, W+2), np.int16)
    G[1:-1, 1:] = (np.frombuffer(read(H*(W+1)), dtype='B') == ord('.')).reshape((H, W+1))
    def solve(G):
        left = np.zeros(G.shape, np.int16)
        for i in range(G.shape[0]):
            left[i, ] = np.arange(G.shape[1])
        left[G>0] = 0
        np.maximum.accumulate(left, out=left, axis=1)

        rG = G[..., ::-1]
        right = np.zeros(G.shape, np.int16)
        for i in range(G.shape[0]): 
            right[i, ] = np.arange(G.shape[1])
        right[rG>0] = 0
        np.maximum.accumulate(right, out=right, axis=1)

        right = G.shape[1] - right[..., ::-1]-1
        scoreres = (right-left-1) 
        scoreres[G==0] = 0
        return scoreres

    print((solve(G)+solve(G.T).T-1).max())
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import math


def main():
    N = int(input())

    for n in range(1, N + 1):
        count = 0

        for x in range(1, int(math.sqrt(2 * n)) + 1):
            for y in range(1, int(math.sqrt(2 * n)) + 1):
                for z in range(1, int(math.sqrt(2 * n)) + 1):
                    if (x + y) ** 2 + (y + z) ** 2 + (z + x) ** 2 == 2 * n:
                        count += 1
                        break

        print(count)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main_v2():
    N = int(input())
    f_list = [0 for _ in range(N)]

    for x in range(1, 101):
        for y in range(1, 101):
            for z in range(1, 101):
                ans = x*x + y*y + z*z + x*y + y*z + z*x
                if ans <= N:
                    f_list[ans - 1] += 1

    for i in range(N):
        print(f_list[i])


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

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse = True)
cnt = 0
for i in a:
    flag = True
    for j in a[a.index(i) + 1:]:
        if i % j == 0:
            flag = False
    if flag:
        cnt += 1
print(cnt)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
m = 10 ** 6 + 1
cnt = [0] * m
for x in a:
    if cnt[x] != 0:
        cnt[x] = 2
        continue
    for i in range(x, m, x):
        cnt[i] += 1
ans = 0
for x in a:
    if cnt[x] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split())) + ["a"]
t = len(a)
cnt = 0
cur = 0
while t > 2:
  l,r = 0,1
  while a[r] != "a" and a[r] == a[l]:
    r += 1
  if a[r] == "a":
    print(cnt+1)
    exit()
  d = a[r]-a[l]
  while a[r+1] != "a" and (a[r+1]-a[r])*d>=0:
    r += 1
  cnt += 1
  d = 0
  a = a[r+1:]
  t -= r+1
if a[0] != "a":
  cnt += 1
print(cnt)
  

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
cnt,st,d = 0,-1,0
for i in range(n):
  if st < 0:
    st = i
    continue
  elif d == 0:
    if a[i]-a[st] != 0:
      r = i
      d = a[r]-a[st]
    continue
  else:
    if (a[i]-a[i-1])*d < 0:
      cnt += 1
      st,d = i,0
if st != -1:
  cnt += 1
print(cnt)
### BUGGY CODE ###

card_count, rewrite_count = map(int, input().split(" "))
cards = list(map(int, input().split(" ")))
cards.sort()

for _ in range(rewrite_count):
    stock_count, rewrite_number = map(int, input().split(" "))
    for index in range(stock_count):
        if rewrite_number <= cards[index]:
            break
        cards[index] = rewrite_number
    cards.sort()

print(sum(cards))

### FIXED CODE ###

import bisect

card_count, rewrite_count = map(int, input().split(" "))

cards = {}
for card in list(map(int, input().split(" "))):
    count = cards.get(card, 0)
    cards[card] = count + 1

for _ in range(rewrite_count):
    stock_count, rewrite_number = map(int, input().split(" "))
    count = cards.get(rewrite_number, 0)
    cards[rewrite_number] = count + stock_count

number_list = list(cards.keys())
number_list.sort(reverse=True)

total = 0
for number in number_list:
    if cards[number] < card_count:
        total += number * cards[number]
    else:
        total += number * card_count
        break
    card_count -= cards[number]

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

import sys
from bisect import bisect_left


def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    F = [int(f) for f in input().split()]
    A.sort(reverse = True)
    F.sort()
    low, high = -1, 10 ** 12 + 1
    while high - low > 1:
        mid = (low + high) // 2
        count = 0
        for i in range(N):
            if A[i] * F[i] > mid: count += A[i] - (mid // F[i])
        if count > K: low = mid
        else: high = mid
    print(high)

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    F = [int(f) for f in input().split()]
    A.sort(reverse = True)
    F.sort()
    low, high = -1, 10 ** 12 + 1
    while high - low > 1:
        mid = (low + high) // 2
        count = 0
        for i in range(N):
            if A[i] * F[i] > mid: count += A[i] - (mid // F[i])
        if count > K: low = mid
        else: high = mid
    print(high)

    return 0

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

import heapq

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

ans = 0

if N != 1:
    heapq.heapify(C)
    for i in range(N):
        c = heapq.heappop(C)
        ans += c * (N + 1 - i) * (2 ** (N - 2))
        ans %= 10 ** 9 + 7
    ans *= 2 ** N
else:
    ans = C[0] * 2

ans %= 10 ** 9 + 7

print(ans)

### FIXED CODE ###

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

C.sort()

ans = 0

mod = 10 ** 9 + 7

pattern = (2 ** (N - 2)) % mod

if N != 1:
    for i in range(N):
        c = C[i]
        ans += c * (N + 1 - i) * pattern
        ans %= mod
    ans *= 2 ** N
else:
    ans = C[0] * 2

ans %= mod

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

import sys
def S(): return sys.stdin.readline().rstrip()

if __name__=='__main__':
    sl = list(S())
    flag = True
    c = 0
    while flag:
        flag = False
        for i in range(0,len(sl)-1):
            if sl[i]=='B' and sl[i+1]=='W':
                sl[i],sl[i+1] = 'W','B'
                c += 1
                flag = True

    print(c)
    exit()

### FIXED CODE ###

import sys
def S(): return sys.stdin.readline().rstrip()

if __name__=='__main__':
    sl = list(S())
    ans = 0
    c = 0
    for i,item in enumerate(sl):
        if item=='W':
            ans += c
        else:
            c += 1

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

MOD=998244353
N=int(input())
A=[int(input()) for _ in range(N)]

TOTAL=pow(3,N,MOD)
ASum=sum(A)

dp=[0 for _ in range(ASum+1)]
dp[0] = 1

for n in range(N):
	for e in range(ASum,A[n]-1,-1):
		dp[e] = dp[e] + dp[e-A[n]]*2
		dp[e] %= MOD

sumEnd=0
plus = 0
sumEnd=ASum//2+1

if ASum % 2 == 0:
	# 合計が偶数
	dpOther=[0 for _ in range(ASum+1)]
	dpOther[0] = 1
	for n in range(N):
		for e in range(ASum,A[n]-1,-1):
			dpOther[e] = dpOther[e] + dpOther[e-A[n]]
			dpOther[e] %= MOD
	plus = (dpOther[ASum//2]*3) % MOD

exceptCnt=0
for s in range(0,sumEnd):
	exceptCnt = (exceptCnt + dp[s]*3) % MOD

exceptCnt -= plus
print((TOTAL - exceptCnt) % MOD )



### FIXED CODE ###

import numpy as np

MOD=998244353
N=int(input())
A=np.array([int(input()) for _ in range(N)])
TOTAL=pow(3,N,MOD)
ASum=sum(A)
sumEnd=0
sumEnd=ASum//2+1

dp=np.array([0 for _ in range(sumEnd)],dtype=np.int64)
dp[0] = 1

for n in range(N):
	dp[A[n]:] += dp[:-A[n]]*2 % MOD

plus = 0
if ASum % 2 == 0:
	# 合計が偶数
	dpOther=np.array([0 for _ in range(sumEnd+1)],dtype=np.int64)
	dpOther[0] = 1
	for n in range(N):
		dpOther[A[n]:] += dpOther[:-A[n]] % MOD
	plus = (dpOther[ASum//2]*3) % MOD

exceptCnt=0
for s in range(0,sumEnd):
	exceptCnt = (exceptCnt + dp[s]*3) % MOD

exceptCnt -= plus
print((TOTAL - exceptCnt) % MOD )
### BUGGY CODE ###

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

for i in range(N-1):
    for j in range(i+1, N):
        ans += (A[i] * A[j]) % (1e9 + 7) 
        ans = ans % (1e9 + 7)

print(int(ans))

### FIXED CODE ###

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

ans = 0
mod = int(1e9 + 7)
s = sum(A) % mod

for a in A:
    s -= a
    ans += (a * s) % mod
    ans %= mod

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

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

a.sort(reverse=True)
ans = [i for i in range(m + 1)]

for j in a:
    n_ans = []
    for i in ans:
        if ((i / j - 0.5) % 1 == 0):
            n_ans.append(i)
    ans = n_ans[:]

print(len(ans))


### FIXED CODE ###

from fractions import gcd
import sys

n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [i // 2 for i in a]

cnt = 1
min_a = min(a)
while min_a % 2 == 0:
    cnt *= 2
    min_a = min_a // 2

ans = 1
for i in a:
    if (i // cnt) % 2 == 0:
        print(0)
        sys.exit()
    ans = (ans * i) // gcd(ans, i)

print((m//ans+1)//2)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    S = list(input())
    T = list(input())

    LCS = [[0 for _ in range(len(T) + 1)] for _ in range(len(S) + 1)]
    for i in range(1, len(S) + 1):
        for j in range(1, len(T) + 1):
            x = 1 if S[i - 1] == T[j - 1] else 0
            LCS[i][j] = max(LCS[i - 1][j - 1] + x, LCS[i - 1][j], LCS[i][j - 1])

    res = ""
    i, j = len(S), len(T)
    while i > 0 and j > 0:
        if LCS[i][j] == LCS[i - 1][j]:
            i -= 1
        elif LCS[i][j] == LCS[i][j - 1]:
            j -= 1
        else:
            res += S[i - 1]
            i -= 1
            j -= 1

    print(res[::-1])


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    S = list(input())
    T = list(input())

    LCS = [[0 for _ in range(len(T) + 1)] for _ in range(len(S) + 1)]
    for i in range(1, len(S) + 1):
        for j in range(1, len(T) + 1):
            x = 1 if S[i - 1] == T[j - 1] else 0
            LCS[i][j] = max(LCS[i - 1][j - 1] + x, LCS[i - 1][j], LCS[i][j - 1])

    res = []
    i, j = len(S), len(T)
    while i > 0 and j > 0:
        if LCS[i][j] == LCS[i - 1][j]:
            i -= 1
        elif LCS[i][j] == LCS[i][j - 1]:
            j -= 1
        else:
            res.append(S[i - 1])
            i -= 1
            j -= 1

    print("".join(res[::-1]))


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

S = input()
Q = int(input())
P = [input().split() for i in range(Q)]

for query in P:
    if query[0]=="1":
        S = S[::-1]
    else:
        if query[1]=="1":
            S=query[2]+S
        else:
            S=S+query[2]

print(S)

### FIXED CODE ###

S = input()
Q = int(input())
P = [input().split() for i in range(Q)]

count = 0
left = ""
right = ""
for query in P:
    if query[0]=="1":
        count+=1
    else:
        if query[1]=="1":
            if count%2==0:
                left+=query[2]
            else:
                right+=query[2]
        else:
            if count%2==0:
                right+=query[2]
            else:
                left+=query[2]
                
S = left[::-1]+S+right
if count%2==1:
    S=S[::-1]
    
print(S)
### BUGGY CODE ###

import collections
N = int(input())
List = list(map(str, input().split()))
Q = int(input())
x = [0] * Q
y = [0] * Q
for i in range(Q):
    x[i], y[i] = map(str, input().split())
    y[i]=int(y[i])

wa=0
for i in List:
    wa+=int(i)

for i in range(Q):
    c = collections.Counter(List)
    num=c['{}'.format(x[i])]
    wa+=num*(y[i]-int(x[i]))
    List=[s.replace('{}'.format(x[i]), '{}'.format(str(y[i]))) for s in List]
    print(wa)

### FIXED CODE ###

from collections import Counter
N = int(input())
List = list(map(str, input().split()))
Q = int(input())
x = [0] * Q
y = [0] * Q
for i in range(Q):
    x[i], y[i] = map(str, input().split())
    y[i]=int(y[i])

wa=0
for i in List:
    wa+=int(i)
c =Counter(List)
for i in range(Q):
    num=c['{}'.format(x[i])]
    wa+=num*(y[i]-int(x[i]))
    c['{}'.format(x[i])]=0
    c['{}'.format(str(y[i]))]+=num
    print(wa)
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse=True)
for i in range(K):
  A[0] = int(A[0]/2)
  A.sort(reverse=True)

print(sum(A))

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
import heapq
a = list(map(lambda x: x*(-1), A))  # 各要素を-1倍

heapq.heapify(a)
for i in range(K):
  num = heapq.heappop(a)*(-1)
  heapq.heappush(a, -1*(int(num/2)))
  #print(num,a)
  if num == 0:
    break
print(-sum(a))
### BUGGY CODE ###

import sys
from collections import deque



readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

def bfs(start):
    tansaku = deque(start)
    visited = {i:set() for i in range(h)}
    res = 0
    black = len(start)
    while black != h*w:
        for _ in range(len(tansaku)):
            pre_y,pre_x = tansaku.popleft()
            if pre_x in visited[pre_y]:
                continue
            for i in range(pre_x-1,pre_x+2,2):
                if 0 <= i <= w-1 and tizu[pre_y][i] == '.':
                    tansaku.append([pre_y,i])
                    tizu[pre_y][i] = '#'
            for j in range(pre_y-1,pre_y+2,2):
                if 0 <= j <= h-1 and tizu[j][pre_x] == '.':
                    tansaku.append([j,pre_x])
                    tizu[j][pre_x] = '#'
            visited[pre_y].add(pre_x)
        black += len(tansaku)
        res += 1
    return res

h,w = nm()
tizu = []
sharp = []
for i in range(h):
    temp = list(input())
    s_temp = [[i,j] for j in range(w)  if temp[j] == '#' ]
    tizu.append(temp)
    sharp += s_temp
ans = bfs(sharp)
print(ans)

### FIXED CODE ###

import sys
from collections import deque



readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

def bfs(start):
    tansaku = deque(start)
    visited = {i:set() for i in range(h)}
    res = 0
    black = len(start)
    while black != h*w:
        for _ in range(len(tansaku)):
            pre_y,pre_x = tansaku.popleft()
            if pre_x in visited[pre_y]:
                continue
            for i in range(pre_x-1,pre_x+2,2):
                if 0 <= i <= w-1 and tizu[pre_y][i] == '.':
                    tansaku.append([pre_y,i])
                    tizu[pre_y][i] = '#'
            for j in range(pre_y-1,pre_y+2,2):
                if 0 <= j <= h-1 and tizu[j][pre_x] == '.':
                    tansaku.append([j,pre_x])
                    tizu[j][pre_x] = '#'
            visited[pre_y].add(pre_x)
        black += len(tansaku)
        res += 1
    return res

h,w = nm()
tizu = []
sharp = []
for i in range(h):
    temp = list(input())
    s_temp = [[i,j] for j in range(w)  if temp[j] == '#' ]
    tizu.append(temp)
    sharp += s_temp
ans = bfs(sharp)
print(ans)