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

#! /usr/bin/env python3

import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
XYP = [list(map(int, readline().split())) for _ in range(N)]

x_cost = [[0 for _ in range(N)] for _ in range(1 << N)]
y_cost = [[0 for _ in range(N)] for _ in range(1 << N)]

for bit in range(1 << N):
    for i in range(N):
        x_cost[bit][i] = abs(XYP[i][0])
        y_cost[bit][i] = abs(XYP[i][1])

        for k in range(N):
            if bit & (1 << k):
                x_cost[bit][i] = min(x_cost[bit][i], abs(XYP[i][0] - XYP[k][0]))
                y_cost[bit][i] = min(y_cost[bit][i], abs(XYP[i][1] - XYP[k][1]))

ans = [sys.maxsize for _ in range(N + 1)]

for bit in range(1 << N):
    cnt = bin(bit).count('1')
    bit_ = bit
    while bit_ >= 0:
        bit_ &= bit
        cost = 0
        for k in range(N):
            cost += 1 * XYP[k][2] * min(x_cost[bit_][k], y_cost[bit - bit_][k])
        ans[cnt] = min(ans[cnt], cost)

        bit_ -= 1
for i in range(N + 1):
    print(ans[i])

### FIXED CODE ###

#! /usr/bin/env python3

import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
XYP = [list(map(int, readline().split())) for _ in range(N)]

costs = [sys.maxsize] * N
for i, (x, y, c) in enumerate(XYP):
    costs[i] = c * min(abs(x), abs(y))

x_cost = [sys.maxsize] * ((1 << N) * N)
y_cost = [sys.maxsize] * ((1 << N) * N)

for bit in range(1 << N):
    for i, (xi, yi, _) in enumerate(XYP):
        x_cost[bit * N + i] = min(costs[i], x_cost[bit * N + i])
        y_cost[bit * N + i] = min(costs[i], y_cost[bit * N + i])
        if not (bit & (1 << i)):
            continue
        for k, (xk, yk, c) in enumerate(XYP):
            x_cost[bit * N + k] = min(x_cost[bit * N + k], abs(xi - xk) * c)
            y_cost[bit * N + k] = min(y_cost[bit * N + k], abs(yi - yk) * c)

ans = [sys.maxsize] * (N + 1)

for bit in range(1 << N):
    cnt = bin(bit).count('1')
    bit_ = bit
    while bit_ >= 0:
        bit_ &= bit
        cost = 0
        y_bit = bit - bit_
        for k in range(N):
            cost += min(x_cost[bit_ * N + k], y_cost[(y_bit) * N + k])
        ans[cnt] = min(ans[cnt], cost)

        bit_ -= 1
for i in range(N + 1):
    print(ans[i])
### BUGGY CODE ###


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
#from functools import reduce,cmp_to_key,lru_cache
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys
# input = sys.stdin.readline



M = mod = 10**9 + 7 
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip().split()]
def st():return str(input().rstrip())[2:-1]
def val():return int(input().rstrip())
def li2():return [str(i)[2:-1] for i in input().rstrip().split()]
def li3():return [int(i) for i in st()]
 



sys.setrecursionlimit(10 ** 5 + 10)

g = 0
d = {}
def dp(i, par = -1, black = 0):
    global g
    ans = 1
    if (i, par, black) in d:return d[(i, par, black)]
    nokids = 1
    if black:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ans * dp(j, i, 0) % mod
    else:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ( ans * (dp(j, i, 0) + dp(j, i, 1)) ) % mod

    if nokids:ans = 1
    d[(i, par, black)] = ans
    return ans



n = val()
g = defaultdict(set)

l = []
for _ in range(n - 1):
    a, b = li()
    g[a].add(b)
    g[b].add(a)


root = 1    
ans = dp(root, -1, 0) + dp(root, -1, 1)

print(ans % mod)

### FIXED CODE ###

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 10 ** 9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
 



sys.setrecursionlimit(10 ** 6)

g = 0
@lru_cache(None)
def dp(i, par = -1, black = 0):
    global g
    ans = 1
    nokids = 1
    if black:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ans * dp(j, i, 0) % mod
    else:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ( ans * (dp(j, i, 0) + dp(j, i, 1)) ) % mod

    if nokids:ans = 1
    return ans



n = val()
g = [[] for i in range(n + 1)]

l = []
for _ in range(n - 1):
    a, b = li()
    g[a].append(b)
    g[b].append(a)


root = 1    
ans = dp(root, -1, 0) + dp(root, -1, 1)

print(ans % mod)
### BUGGY CODE ###

[N, M] = list(map(int,input().split()))
A = [0]*N
B = [0]*N
for i in range(N):
    [A_tmp, B_tmp] = list(map(int,input().split()))
    A[i] = A_tmp
    B[i] = B_tmp

tmp = M
ans = 0
while (tmp > 0):
        idx_tmp = A.index(min(A))
        # break condition
        if B[idx_tmp] >= tmp:
            ans += tmp*A[idx_tmp]
            tmp = 0
        else:
            ans += A[idx_tmp]*B[idx_tmp]
            tmp = tmp - B[idx_tmp]
            A.pop(idx_tmp)
            B.pop(idx_tmp)

print(ans)

### FIXED CODE ###

[N, M] = list(map(int,input().split()))
AB = [list(map(int, input().split())) for i in range(N)]

AB.sort(key=lambda x:x[0])
tmp = M
ans = 0

for i in range(N):
    #break
    if tmp <= AB[i][1]:
        ans += tmp * AB[i][0]
        break
    
    ans += AB[i][0] * AB[i][1]
    tmp = tmp - AB[i][1]


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

import math
#from functools import reduce

k = int(input())

lis = [(0)] * (250*250)
ans = 0
for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      x = math.gcd(b,c)
      lis[b + (250*c)] = (x)
      ans += lis[a + (250*x)]

print(ans)


### FIXED CODE ###

from math import gcd
#from functools import reduce

k = int(input())

ans = 0
for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      ans += gcd(gcd(b,c),a)

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

Q = int(input())
a = []
b = 0

for _ in range(Q):
    q = list(map(int, input().split()))
    if q[0] == 1:
        a.append(q[1])
        b += q[2]
    else:
        a.sort()
        idx = len(a) // 2
        if len(a) % 2 == 0:
            ans_x = a[idx-1]
        else:
            ans_x = a[idx]
        ans = b
        if len(a) == 0:
            print("0 0")
        else:
            for v in a:
                if v < ans_x:
                    ans += ans_x - v
                else:
                    ans += v - ans_x
            print("{0} {1}".format(ans_x, ans))


### FIXED CODE ###

import heapq

Q = int(input())
ans = 0

L = []
R = []

for _ in range(Q):
    q = list(map(int, input().split()))
    if q[0] == 1:
        l = heapq.heappushpop(L, -q[1])
        r = heapq.heappushpop(R, q[1])
        heapq.heappush(L, -r)
        heapq.heappush(R, -l)
        ans += abs(l + r) + q[2]
    else:
        print(-L[0], ans)
### BUGGY CODE ###

s = input()
q = int(input())
cnt = 0
for i in range(q):
    t_f_c = list(input().split())
    #反転する=先末逆転
    if t_f_c[0] == "1":
        cnt  += 1
    #反転しない
    elif t_f_c[0] == "2":
        if cnt % 2 == 0:
            if t_f_c[1] == "1":
                s = t_f_c[2] + s
            elif t_f_c[1] == "2":
                s = s + t_f_c[2]
        elif cnt % 2 == 1:
            if t_f_c[1] == "1":
                s = s + t_f_c[2]
            elif t_f_c[1] == "2":
                s = t_f_c[2] + s
if cnt % 2 == 0:
    print(s)
elif cnt % 2 == 1:
    print(s[::-1])

### FIXED CODE ###

from collections import deque
s = deque(input())
q = int(input())

cnt = 1
for i in range(q):
    t_f_c = list(input().split())
    if t_f_c[0] == "1":
        cnt *= -1
    elif t_f_c[0] == "2":
        if cnt == 1: #反転-
            if t_f_c[1] == "1":
                s.appendleft(t_f_c[2])
            elif t_f_c[1] == "2":
                s.append(t_f_c[2])
        elif cnt == -1:  #反転+
             if t_f_c[1] == "2":
                s.appendleft(t_f_c[2])
             elif t_f_c[1] == "1":
                s.append(t_f_c[2])
if cnt == 1:
    print("".join(s))
elif cnt == -1:
    s.reverse()
    print("".join(s))
### BUGGY CODE ###

H, W, M = map(int, input().split())
hw = []

h_cnt = [0] * H
w_cnt = [0] * W
hw = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(M)]
for h, w in hw:
    h_cnt[h] += 1
    w_cnt[w] += 1

max_h = max(h_cnt)
max_w = max(w_cnt)
hs = [i for i in range(H) if h_cnt[i]==max_h]
ws = [i for i in range(W) if w_cnt[i]==max_w]

cnt = 0
for h, w in hw:
    if h in hs and w in ws:
        cnt += 1
if cnt < len(hs)*len(ws):
    print(max_h+max_w)
else:
    print(max_h+max_w-1)



### FIXED CODE ###

H, W, M = map(int, input().split())

h_cnt = [0] * H
w_cnt = [0] * W
hw = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(M)]
for h, w in hw:
    h_cnt[h] += 1
    w_cnt[w] += 1

max_h = max(h_cnt)
max_w = max(w_cnt)
hs = [i for i in range(H) if h_cnt[i]==max_h]
ws = [i for i in range(W) if w_cnt[i]==max_w]

ans = max_h+max_w-1
hw = set(hw)
for h in hs:
    for w in ws:
        if (h, w) not in hw:
            print(max_h+max_w)
            exit()
print(max_h+max_w-1)
### BUGGY CODE ###

def main():
    n = int(input())
    a = tuple(map(int, input().split()))

    ans = 0
    for i in range(len(a)):
        if a.count(a[i]) > 1:
            continue
        divisors = set()
        for j in range(1, int(a[i] ** 0.5) + 1):
            if a[i] % j == 0:
                divisors.add(j)
                if j != a[i] // j:
                    divisors.add(a[i] // j)
        if len(set(a) & divisors) == 1:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a = tuple(map(int, input().split()))

    ans = 0
    mx = max(a) + 1
    dp = [0] * mx
    for i in a:
        for j in range(i, mx, i):
            dp[j] += 1
    for i in a:
        if dp[i] == 1:
            ans += 1

    print(ans)


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

import sys
input = sys.stdin.readline


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        self.rnk = [0] * (n + 1)

    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def size(self, x):
        return -self.root[self.find_root(x)]


# adj: [[weight, u, v] * num_edge], V: number of vertices
def kruskal(adj, V):
    adj.sort()
    uf = UnionFind(V)
    ans = 0
    for edge in adj:
        weight, u, v = edge
        if not uf.isSameGroup(u, v):
            ans += weight
            uf.unite(u, v)
    return ans


N = int(input())
x_list = [0] * N
y_list = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    x_list[i] = [x, i]
    y_list[i] = [y, i]

x_list.sort()
y_list.sort()
adj = [0] * (2 * (N-1))
for i in range(N-1):
    adj[2*i] = [x_list[i + 1][0] - x_list[i][0], x_list[i + 1][1], x_list[i][1]]
    adj[2*i+1] = [y_list[i + 1][0] - y_list[i][0], y_list[i + 1][1], y_list[i][1]]

print(kruskal(adj, 2 * (N - 1)))


### FIXED CODE ###

# 6199094

import array
import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]

    def size(self,x):
        return -self.parent[self.find(x)]

    def find(self,x):
        if(self.parent[x]<0):
            return x
        else:
            self.parent[x]=self.find(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

    def same(self,x,y):
        return self.find(x)==self.find(y)

def main():
    N = int(input())
    xli = []
    yli = []
    x_app = xli.append
    y_app = yli.append


    for i in range(N):
        x,y = (int(x) for x in input().split())
        x_app([x-1,i])
        y_app([y-1,i])
    xli.sort()
    yli.sort()

    edges = []
    edges_app = edges.append
    for i in range(N-1):
        edges_app((xli[i][1],xli[i+1][1],xli[i+1][0]-xli[i][0]))
        edges_app((yli[i][1],yli[i+1][1],yli[i+1][0]-yli[i][0]))


    edges.sort(key=lambda edge: edge[2])
    uf = UnionFind(N)
    weight = 0

    for edge in edges:
        if not uf.same(edge[0], edge[1]):
            uf.unite(edge[0], edge[1])
            weight+=edge[2]
    print(weight)

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

import re


S = input()
L = len(S)

while True:
    T = S[:]
    S = re.sub('(10)+', '', S)
    S = re.sub('(01)+', '', S)
    if S == T:
        break

print(L - len(S))


### FIXED CODE ###

S = input()

print(min(S.count('0'), S.count('1')) * 2)
### BUGGY CODE ###

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conditions = {}
for i in range(n):
  inputs = [int(x) for x in input().split()]
  if inputs[0] in conditions.keys():
    conditions[inputs[0]].append(inputs[1])
  else:
    conditions[inputs[0]] = [inputs[1]]

for day in conditions.keys():
  conditions[day].sort(reverse=True)

ans = 0
candidates = []
for reversed_day in range(1, m + 1):
  if reversed_day in conditions.keys():
    candidates.append(conditions[reversed_day])

  cand_len = len(candidates)
  if cand_len == 0:
    continue
  maxval, maxidx = 0, 0
  for i in range(cand_len):
    if candidates[i][0] > maxval:
      maxval = candidates[i][0]
      maxidx = i
  ans += candidates[maxidx].pop(0)
  if len(candidates[maxidx]) == 0:
    del candidates[maxidx]
print(ans)

### FIXED CODE ###


import collections
import heapq

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conditions = collections.deque([])
for i in range(n):
  conditions.append([int(x) for x in input().split()])

conditions = sorted(conditions)

cnt, ans = 0, 0
candidates = []
for reversed_day in range(1, m + 1):
  while cnt < len(conditions) and conditions[cnt][0] <= reversed_day:
    heapq.heappush(candidates, -conditions[cnt][1])
    cnt += 1

  if len(candidates) == 0:
    continue
  ans -= heapq.heappop(candidates)

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

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
from collections import deque

H,W = map(int,input().split())
INF = 10**18
q = deque()

d = [[0]*(W+2)] + [[0]+[INF]*W+[0] for _ in range(H)] + [[0]*(W+2)]# '#'からの距離

for i in range(1,H+1):
  for j,c in enumerate(input(),1):
    if c == '#':
      d[i][j] = 0
      q.append((0,i,j))

      
ans = 0
while q:
  dv,x,y = q.popleft()
  for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
    xx = x+dx
    yy = y+dy
    if d[xx][yy] == INF:
      d[xx][yy] = dv+1
      ans = dv+1
      q.append((dv+1,xx,yy))

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
  
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)]

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
l = [p[0]]
b =0
for i in range(1,n):
  l.append(min(p[0:i+1]))
for i in range(0,n):
  if p[i] == l[i]:
    b += 1
print(b)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
c = a[0]
for i in range(1, n):
  if min(c,a[i])== a[i]:
    c = a[i]
    ans += 1
print(ans)
### BUGGY CODE ###

import collections,math
s = input()
t = input()
#tを構成文字で、sにない文字があったらダメ。
#構成できるなら最大でもlen(t)個しかないから、10^100の連結は必要ない

#最も不足する文字を探す
ls = collections.Counter(s)
lt = collections.Counter(t)

time_dict ={}
tmp=0
max_time=0#一番少ないやつ
for t_key,t_val in lt.items():
    if t_key not in ls:#sの中にtの文字がない
        print(-1)
        exit()

#多分TLEするかも。。数えすぎか
cnt = 0
tt = list(t[::-1])
idx=0
ss = s
while tt!=[]:
    next_t = tt.pop()
    idx=ss.find(next_t)
    if idx == -1:
        cnt += len(ss)
        idx = s.find(next_t)
        ss = s[idx+1:]
        cnt += idx+1
    else:
        cnt += idx+1
        ss = ss[idx+1:]
print(cnt)


### FIXED CODE ###

import collections,math
s = input()
t = input()
#tを構成文字で、sにない文字があったらダメ。
#構成できるなら最大でもlen(t)個しかないから、10^100の連結は必要ない

#最も不足する文字を探す
ls = collections.Counter(s)
lt = collections.Counter(t)

time_dict ={}
tmp=0
max_time=0#一番少ないやつ
for t_key,t_val in lt.items():
    if t_key not in ls:#sの中にtの文字がない
        print(-1)
        exit()

#多分TLEするかも。。
cnt = 0
tt = list(t[::-1])
idx=0
ss = s
while tt!=[]:
    next_t = tt.pop()
    idx=ss.find(next_t)
    if idx == -1:
        cnt += len(ss)
        idx = s.find(next_t)
        ss = s[idx+1:]
        cnt += idx+1
    else:
        cnt += idx+1
        ss = ss[idx+1:]
print(cnt)
### BUGGY CODE ###

N = int(input())
S = input()
nR = S.count('R')
nG = S.count('G')
nB = S.count('B')
cnt = 0
for i in range(N-1):
  for j in range(i+1, N):
    k = j - i + j
    if k < N:
      L = [S[i], S[j], S[k]]
      if 'R' in L and 'G' in L and 'B' in L:
        cnt += 1
print(nR*nG*nB-cnt)

### FIXED CODE ###

N = int(input())
S = input()
nR = 0
nG = 0
nB = 0
cnt = 0
for i in range(N):
  if S[i] == 'R':
    nR += 1
  elif S[i] == 'G':
    nG += 1
  else:
    nB += 1
  for j in range(i+1, N):
    k = j - i + j
    if k < N:
      L = [S[i], S[j], S[k]]
      if 'R' in L and 'G' in L and 'B' in L:
        cnt += 1
    else:
      break
print(nR*nG*nB-cnt)
### BUGGY CODE ###

import networkx

n, m = map(int, input().split())
g = networkx.Graph()
g.add_nodes_from(list(range(n)))
for i in range(1, m + 1):
    a, b = map(int, input().split())
    g.add_edge(a, b)
#print(g.nodes())
#print(g.edges())
print("Yes")
for i in range(2, n + 1):
    print(networkx.shortest_path(g, 1, i)[-2])

### FIXED CODE ###

from networkx import Graph,predecessor

G = Graph() #無効グラフ生成
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
G.add_edges_from(ab) #辺リスト生成
preds = predecessor(G,source=1)  #sourceはstart node
print("Yes")
for i in range(2,n+1):
    print(preds[i][0])

#描画
#import matplotlib.pyplot as plt
#import networkx as nx
#nx.draw_networkx(G)
#plt.show()
### BUGGY CODE ###

import itertools
letters = ['M','A','R','C','H']
N = int(input())
a = []
com_s = []

for i in range(N):
    x = input()
    if x[0] in letters:
        a.append(x)

coms = list(itertools.combinations(a,3))
for com in coms:
    if com[0][0] != com[1][0] and com[1][0] != com[2][0] and com[2][0] != com[0][0]:
        com_s.append(com)

print(len(com_s))

### FIXED CODE ###

N = int(input())
_M = [] 
_A = [] 
_R = [] 
_C = [] 
_H = [] 

for i in range(N):
    x = input()
    if x[0] == 'M':
        _M.append(x)
    elif x[0] == 'A':
        _A.append(x)
    elif x[0] == 'R':
        _R.append(x)
    elif x[0] == 'C':
        _C.append(x)
    elif x[0] == 'H':
        _H.append(x)

m = len(_M)
a = len(_A)
r = len(_R)
c = len(_C)
h = len(_H)

x = m*a*r + m*a*c + m*a*h + m*r*c + m*r*h + m*c*h + a*r*c + a*r*h + a*c*h + r*c*h

print(x)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
def i():
    return int(raw_input())
def s():
    return raw_input()
 
#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper
 
Q=10**9+7
@memoize
def dp(n,i):
    if n<i:return 0
    elif n==1:return 1
    if i==0:return (dp(n-1,1)*2+dp(n-1,0))%Q
    else:return (dp(n-1,i-1)+dp(n-1,i+1)*2)%Q
n=i()
s=s()
print dp(n,len(s))


### FIXED CODE ###

mod=1000000007
n=int(raw_input())
l=len(raw_input())
dp=[[0 for i in range(n+2)] for j in range(n+1)]
for i in range(n+1):
    for j in range(i+1):
        if i==0:dp[i][j]=1
        elif j==0:dp[i][j]=(dp[i-1][1]*2+dp[i-1][0])%mod
        else:dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1]*2)%mod
print dp[n][l]
### BUGGY CODE ###

k, s = map(int, input().split())
c = 0

for x in range(k + 1):
  for y in range(k + 1):
    for z in range(k + 1):
      if x + y + z == s:
        c += 1
print(c)


### FIXED CODE ###

k, s = map(int, input().split())
c = 0

for x in range(k + 1):
  for y in range(k + 1):
    if 0 <= s - (x + y) <= k:
      c += 1
print(c)
### BUGGY CODE ###

H, W = map(int, input().split())
a = []
INF = 10 ** 9
for i in range(H):
    a.append(input())

# 黒マスの位置を記録
black_stack = []
for i in range(H):
    for j in range(W):
        if a[i][j] == "#":
            black_stack.append([i, j])
black_map = black_stack[::]
cnt = 0
while len(black_map) != H*W:
    next_stack = []
    cnt += 1
    for pos in black_stack:
        for i in [[-1,0], [1, 0], [0, -1], [0, 1]]:
            if 0 <= pos[0] + i[0] <= H-1 and 0 <= pos[1] + i[1] <= W-1:
                    next_stack.append([pos[0] + i[0], pos[1] + i[1]])
                    if [pos[0] + i[0], pos[1] + i[1]] not in black_map:
                        black_map.append([pos[0] + i[0], pos[1] + i[1]])
    black_stack = next_stack[::]
print(cnt)

### FIXED CODE ###

from collections import deque
h,w = list(map(int,input().split()))
f = []
q = deque()
for i in range(h):
    a = list(input())
    for j in range(w):
        if a[j] == '#':
            q.append([0,i,j])
    f.append(a)
 
ans =0
dxy = [0,1,0,-1,0]
while(len(q)):
    c,y,x = q.popleft()
    for i in range(4):
        ny = y+dxy[i]
        nx = x+dxy[i+1]
        if nx >= w or ny >= h or nx <0 or ny <0:
            continue
        if f[ny][nx] == '.':
            f[ny][nx] = c+1
            q.append([c+1,ny,nx])
            ans = max(ans,c+1)
        elif f[ny][nx] != '#' and f[ny][nx] > c+1:
            f[ny][nx] = c+1
            q.append([c+1,ny,nx])
            ans = max(ans,c+1)
 
print(ans)