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

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

dp = [[-1] * N for _ in range(N)]
for i in range(N):
    dp[i][i] = 0
for i in range(N-1):
    if S[i] == S[N-1]:
        dp[i][N-1] = 1

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

for i in range(N-1, -1, -1):
    for j in range(N-1, i-1, -1):
        for di, dj in d:
            ni = i + di
            nj = j + dj
            if not(0 <= ni < nj < N):
                continue
            if (di, dj) == (-1, -1) and S[ni] == S[nj] and ni + dp[i][j] < nj:
                dp[ni][nj] = max(dp[ni][nj], dp[i][j] + 1)
            else:
                dp[ni][nj] = max(dp[ni][nj], dp[i][j])

ans = 0
for i in range(N):
    for j in range(i+1, N):
        ans = max(ans, dp[i][j])

print(ans)

### FIXED CODE ###

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

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

for i in range(N-2, -1, -1):
    for j in range(N-1, i, -1):
        if S[i] == S[j]:
            dp[i][j] = min(dp[i+1][j+1] + 1, j-i)
        else:
            dp[i][j] = 0

ans = 0
for i in range(N):
    for j in range(i+1, N):
        ans = max(ans, dp[i][j])

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

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

cnt = 0


for i in range(N):
    now = 0
    for j in A[i:]:
        now += j
        if now == 0:
            cnt += 1

print(cnt)

### FIXED CODE ###

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

cnt = 0

DP = [0] * (N + 1)

for i in range(N):
    DP[i + 1] = DP [i] + A[i]

dic = {}

for i in DP:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1

for i in dic.values():
    cnt += (i * (i - 1)) // 2

print(cnt)
### BUGGY CODE ###

import sys

def get_prime_list(max_num):
    res = range(2, max_num + 1)
    for i in range(2, max_num/2 + 1):
        res = filter(lambda x: not ((x % i == 0) and (x != i)), res)        
    return res

def is_include(array, num):
    right = len(array) - 1
    left = 0
    while right >= left:
        index = (right + left) / 2
        if array[index] == num:
            return True
        elif array[index] < num:
            left = index + 1
        elif array[index] > num:
            right = index - 1
    return False

if __name__ == "__main__":
    num = int(sys.stdin.readline().strip())
    num_list = [int(sys.stdin.readline().strip()) for i in xrange(0, num)]
    prime_list = sorted(get_prime_list(max(num_list)))
    print len(filter(lambda x: is_include(prime_list, x), num_list))

### FIXED CODE ###

n = int(input())

ans = 0
for x in (int(input()) for _ in range(n)):
    flg = True
    for y in range(2, int(x**0.5+1)):
        if x % y == 0:
            flg = False
            break
    if flg:
        ans += 1

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

n, m = map(int, input().split(' '))
dp = [float('inf')]*(2**n)
dp[0] = 0
for i in range(m):
    a, b = input().split(' ')
    a = int(a)
    b = int(b)
    M = 0
    for j in input().split(' '):
        M += 2**(int(j)-1)

    for j in range(2**n):
        dp[j|M] = min(dp[j]+a, dp[j|M])

print(dp[2**n-1] if dp[2**n-1] < float('inf') else -1)

### FIXED CODE ###

n,m = input().split(' ')
n = int(n)
m = int(m)
dp = [float('inf')]*2**n
dp[0] = 0
for i in range(m):
    a,b = input().split(' ')
    a = int(a)
    b = int(b)
    ngo = 0
    for j in input().split(' '):
        ngo += 2**(int(j)-1)
    for j in range(2**n):
        if dp[j|ngo] > dp[j]+a:
            dp[j|ngo] = dp[j]+a
    
if dp[2**n-1] == float('inf'):
    print(-1)
    exit(0)
print(dp[2**n-1])
### BUGGY CODE ###

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

dic = []

for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        dic.append(s[i:j])

dic = (list)(set(dic))
dic.sort()

print(dic[k-1])


### FIXED CODE ###

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

dic = []

for i in range(len(s)):
    for j in range(1, k+1):
        dic.append(s[i:i+j])

dic = (list)(set(dic))
dic.sort()


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

def main():
    K, S = map(int, input().split())
    count=0


    if(S<=3725):
        for x in range(0, K+1):
            for y in range(0, K+1):
                for z in range(0, K+1):
                    if(x+y+z==S):
                        count+=1
    else:
        for x in reversed(range(0, K+1)):
            for y in reversed(range(0, K+1)):
                for z in reversed(range(0, K+1)):
                    if(x+y+z==S):
                        count+=1
    print(count)

main()

### FIXED CODE ###

def main():
    K, S = map(int, input().split())
    count=0

    for x in range(0, K+1):
        for y in range(0, K+1):
            if(0<=S-x-y<=K):
                count+=1

    print(count)

main()
### BUGGY CODE ###

S=input()
T=S.split(" ")
a=int(T[0])
b=int(T[1])
x=int(T[2])
U=[i for i in range(a,b+1) if i%x==0]
print(len(U))

### FIXED CODE ###

T=input().split(" ")
a=int(T[0])
b=int(T[1])
x=int(T[2])
if a==0:
    print(b//x+1)
else:
    print((b//x)-((a-1)//x))
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in reversed(range(N)):
  for j in range(N):
    if (j + i) <= N and S.count(S[j:j+i]) == 2:
      ans = i
      print(ans)
      exit()

print(ans)

### FIXED CODE ###

N = int(input())
S = input()
i = j = ans = 0
while j < N:
  if S[i:j] in S[j:]:
    ans = max(ans, len(S[i:j]))
    j += 1
  else:
    i += 1

  if i == j:
    i += 1
    j += 2
print(ans)
### BUGGY CODE ###

def longest_match(left, right):
    table = [[0 for _ in range(1 + len(right))] for _ in range(1 + len(left))]
    for i in range(len(left)):
        for j in range(len(right)):
            if left[i] == right[j]:
                table[i+1][j+1] = table[i][j] + 1
            else:
                table[i+1][j+1] = max(table[i+1][j], table[i][j+1])
    return table[-1][-1]

def solve(N, S):
    longest = 0
    for i in range(1, N):
        left = S[:i]
        right = S[i:]
        longest = max(longest_match(left, right), longest)
    return longest

def main():
    N = int(input().strip())
    S = input().strip()
    result = solve(N, S)
    print(result)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import random
from collections import defaultdict


class RollingHash():

    def __init__(self, S, b=3491, m=999999937):
        """任意の基数と法でハッシュを生成する"""
        n = len(S)
        self.prefix = prefix = [0] * (n+1)
        self.power = power = [1] * (n+1)
        self.b = b
        self.m = m
        for i in range(n):
            c = ord(S[i])
            prefix[i+1] = (prefix[i] * b + c) % m
            power[i+1] = (power[i] * b) % m
    
    def get(self, l, r):
        """S[l, r) のハッシュを求める"""
        return (self.prefix[r] - self.power[r-l] * self.prefix[l]) % self.m
    
    def concat(self, h1, h2, l2):
        """S1+S2 のハッシュを、それぞれのハッシュから求める"""
        return (self.power[l2] * h1 + h2) % self.m
    
    def lcp(self, l1, r1, l2, r2):
        """S[l1, r1) とS[l2, r2) の最大共通接頭辞を求める"""
        low = 0
        high = min(r1-l1, r2-l2) + 1
        while high - low > 1:
            mid = (high + low) // 2
            if self.get(l1, l1 + mid) == self.get(l2, l2 + mid):
                low = mid
            else:
                high = mid
        return low


def read():
    N = int(input().strip())
    S = input().strip()
    return N, S


def solve(N, S):
    ans = []
    for m in [999999937, 10**9+7]:
        b = random.randint(10000, m-1)
        rh = RollingHash(S, b=b, m=m)
        low = 0
        high = (N+1) // 2 + 1
        dmax = defaultdict(int)
        dmin = defaultdict(int)
        while high - low > 1:
            dmax.clear()
            dmin.clear()
            mid = (high + low) // 2
            for i in range(0, N-mid+1):
                h = rh.get(i, i+mid)
                dmax[h] = max(dmax[h], i+1)
                dmin[h] = max(dmin[h], N+1-i)
            is_match = False
            for h in dmax.keys():
                if dmax[h] - (N+2 - dmin[h]) >= mid:
                    is_match = True
                    break
            if is_match:
                low = mid
            else:
                high = mid
        ans.append(low)
    return min(ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))
### BUGGY CODE ###

K = int(input())

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

dammy = [0]*(K*K*K)
i=0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            #dammy.append(gcd(a, b, c))
            dammy[i]=gcd(a, b, c)
            i+=1

print(sum(dammy))

### FIXED CODE ###

import fractions
K = int(input())

gcd = [[0]*K for i in range(K)]
L = [0]*K

for a in range(1,K+1):
    for b in range(1,K+1):
        A = fractions.gcd(a,b)
        gcd[a-1][b-1] = A
        L[A-1] +=1

sum=0
for c in range(1,K+1):
    for i in range(1,K+1):
        B = gcd[c-1][i-1]
        sum +=  B * L[i-1]

print(sum)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline

R, C, k = map(int, input().split())
field = [[0] * C for _ in range(R)]
for _ in range(k):
    r, c, v = map(int, input().split())
    r -= 1; c -= 1
    field[r][c] = v

# dp[taken 0 - 2][R][C]
dp = [[-1] * (C + 1) * (R + 1) for _ in range(4)]
dp0 = dp[0]; dp1 = dp[1]; dp2 = dp[2]; dp3 = dp[3]
dp[0][0] = 0
for j in range(C):
    for i in range(R):
        ij = i * C + j
        ij1 = ij + 1
        i1j = ij + C
        item = field[i][j]
        for k in range(4):
            # Use
            if item and k < 3:
                dp[k+1][ij1] = max(dp[k+1][ij1], dp[k][ij] + item) 
                dp0[i1j] = max(dp0[i1j], dp[k][ij] + item) 
            # No use down
            if dp[k][ij] > dp0[i1j]:
                dp0[i1j] = dp[k][ij]
            # No use right
            if dp[k][ij] > dp[k][ij1]:
                dp[k][ij1] = dp[k][ij]

ans = 0
for i in range(4):
    for j in range(R + 1):
        ans = max(ans, dp[i][j * C + C - 1])
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline

R, C, k = map(int, input().split())
field = [[0] * C for _ in range(R)]
for _ in range(k):
    r, c, v = map(int, input().split())
    r -= 1; c -= 1
    field[r][c] = v

# dp[taken 0 - 2][R][C]
dp = [[-1] * (C + 1) * (R + 1) for _ in range(4)]
dp0 = dp[0]; dp1 = dp[1]; dp2 = dp[2]; dp3 = dp[3]
dp[0][0] = 0
for j in range(C):
    for i in range(R):
        ij = i * C + j
        ij1 = ij + 1
        i1j = ij + C
        item = field[i][j]
        # Use
        if item:
            dp1[ij1] = max(dp1[ij1], dp0[ij] + item) 
            dp0[i1j] = max(dp0[i1j], dp0[ij] + item) 
        dp0[i1j] = max(dp0[i1j], dp0[ij]) 
        dp0[ij1] = max(dp0[ij1], dp0[ij]) 
        if item:
            dp2[ij1] = max(dp2[ij1], dp1[ij] + item) 
            dp0[i1j] = max(dp0[i1j], dp1[ij] + item) 
        dp0[i1j] = max(dp0[i1j], dp1[ij]) 
        dp1[ij1] = max(dp1[ij1], dp1[ij]) 
        if item:
            dp3[ij1] = max(dp3[ij1], dp2[ij] + item) 
            dp0[i1j] = max(dp0[i1j], dp2[ij] + item) 
        dp0[i1j] = max(dp0[i1j], dp2[ij]) 
        dp2[ij1] = max(dp2[ij1], dp2[ij]) 
        dp0[i1j] = max(dp0[i1j], dp3[ij]) 
        dp3[ij1] = max(dp3[ij1], dp3[ij]) 

ans = 0
for i in range(4):
    for j in range(R + 1):
        ans = max(ans, dp[i][j * C + C - 1])
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

a,b,c,d = map(int,input().split())

num = 0
for i in range(a,b+1):
    if i%c != 0 and i%d != 0:
        num += 1

print(str(num))

### FIXED CODE ###

# -*- coding: utf-8 -*-

a,b,c,d = map(int,input().split())

num = 0

import fractions
lcm = c*d//int(fractions.gcd(c, d))

num = b-b//c-b//d+b//lcm-((a-1)-(a-1)//c-(a-1)//d+(a-1)//lcm)





print(str(num))
### BUGGY CODE ###

from scipy.misc import comb

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

K = {}
for row in A:
    if row in K:
        K[row] += 1
    else:
        K[row] = 1

# 辞書Kに関して全探索
D = {}
for row in A:
    ans = 0
    if row not in D:
        for i in K:
            if i == row:
                ans += comb(K[i]-1, 2, exact=True)
            else:
                ans += comb(K[i], 2, exact=True)
        D[row] = int(ans)
        print(D[row])
    else:
        print(D[row])

### FIXED CODE ###

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

K = {}
for row in A:
  if row in K:
    K[row] += 1
  else:
    K[row] = 1
        
# 最大数を計算
max = 0
for i in K:
  max += int(K[i]*(K[i]-1)/2)

# 辞書Kに関して全探索
for i in A:
  print(max - int(K[i]*(K[i]-1)/2) + int((K[i]-1)*(K[i]-2)/2) )
### BUGGY CODE ###

a, b = input().split()
lis = []
for x in range(int(a)+1):
  for y in range(int(a)+1-x):
    for z in range(int(a)+1-x-y):
      if 1000 * x + 5000 * y + 10000 * z == int(b) and x + y + z == int(a):
        print("{} {} {}".format(z, y, x))
        exit()
if len(lis) == 0:
  print("-1 -1 -1")

### FIXED CODE ###

a, b = input().split()
lis = []
for x in range(int(a)+1):
  for y in range(int(a)+1-x):
    z = int(a) - x - y
    if 1000 * x + 5000 * y + 10000 * z == int(b) and x + y + z == int(a):
      lis.append("{} {} {}".format(z, y, x))
      print("{} {} {}".format(z, y, x))
      exit()
if len(lis) == 0:
  print("-1 -1 -1")
### BUGGY CODE ###


def solve():
    N = int(input())
    progression = list(map(int, input().split()))
    cuml = [0]*(N+1)
    for i in range(len(progression)):
        cuml[i+1] = cuml[i] + progression[i]
    ans = 0
    for i in range(1, N+1):
        if cuml[i] == 0:
            ans += 1
        for j in range(i+1, N+1):
            # print(cuml[i], cuml[j])
            if cuml[i] == cuml[j]:
                ans += 1
        # print()
    print(ans)

solve()

### FIXED CODE ###

from collections import defaultdict
def solve():
    N = int(input())
    progression = list(map(int, input().split()))
    cuml = [0]*(N+1)
    for i in range(len(progression)):
        cuml[i+1] = cuml[i] + progression[i]
    cuml_dic = defaultdict(list)
    for i, num in enumerate(cuml):
        cuml_dic[num].append(i)
    ans = 0
    for key, value in cuml_dic.items():
        n = len(value)-1
        ans += int((n+1)*n/2)

    print(ans)

solve()
### 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.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
E = []
for a in A:
    for b in B:
        E.append(a + b)
E.sort(reverse=True)
E = E[:K]
ans = []
for e in E:
    for c in C:
        ans.append(e + c)
ans.sort(reverse=True)
ans = ans[:K]
for x in ans:
    print(x)

### 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)
E = []
for a in A:
    for b in B:
        E.append(a + b)
E.sort(reverse=True)
E = E[:K]
ans = []
for e in E:
    for c in C:
        ans.append(e + c)
ans.sort(reverse=True)
ans = ans[:K]
for x in ans:
    print(x)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import sys
sys.setrecursionlimit(10**7)
def main(n,ab,px):
  g=[[]for _ in range(n)]
  for a,b in ab:
    g[a-1].append(b-1)
    g[b-1].append(a-1)
  ans=[0 for _ in range(n)]
  for p,x in px:
    ans[p-1]+=x  
  def dfs(seen,i):
    seen[i]=1
    l=g[i]
    for li in [li for li in l if seen[li]==0]:
        ans[li]+=ans[i]
        dfs(seen,li)
  seen=[0 for _ in range(n)]
  dfs(seen,0)
  print(' '.join(list(map(str,ans))))

if __name__=='__main__':
  n,q=map(int,input().split())
  ab=[list(map(int,input().split())) for _ in range(n-1)]
  px=[list(map(int,input().split())) for _ in range(q)]
  main(n,ab,px)
  

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
def main():
    n,q=map(int,input().split())
    graph=[[] for _ in range(n+1)]
    ab=[list(map(int,input().split())) for _ in range(n-1)]
    for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
    px=[list(map(int,input().split())) for _ in range(q)]
    seen=[0]*(n+1)
    ans=[0]*(n+1)
    for p,x in px:
        ans[p]+=x
    def dfs(i):
        seen[i]=1
        for li in graph[i]:
            if seen[li]==0:
                ans[li]+=ans[i]
                dfs(li)
    dfs(1)
    print(' '.join(map(str,ans[1:])))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def main(x, y):
    if x % y == 0:
        print(-1)
        return

    i = max(x, y) + 1

    while True:
        if (i % x) == 0 and (i % y) != 0:
            print(i)
            break

        i += 1


if __name__ == '__main__':
    x, y = map(int, input().split(' '))
    main(x, y)


### FIXED CODE ###

def main(x, y):
    if x % y == 0:
        print(-1)
    else:
        print(x)


if __name__ == '__main__':
    x, y = map(int, input().split(' '))

    main(x, y)
### BUGGY CODE ###

def resolve():
    import sys
    input = sys.stdin.readline
    from collections import deque
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    d=[[1,0],[-1,0],[0,1],[0,-1]]
    visit=[[False]*w for _ in range(h)]
    ans=0
    st=[]
    st=deque()
    st.append((ch,cw,0))
    while st:
      nx,ny,ncost=st.popleft()
      visit[nx][ny]=True
      if dh==nx and dw==ny:
        visit[dh][dw]=True
        ans=ncost
        break
      for dx,dy in d:
        x=nx+dx
        y=ny+dy
        if (0<=x<=h-1) and (0<=y<=w-1):
          if s[x][y]!='#' and visit[x][y]==False:
            st.appendleft((x,y,ncost))
      for i in range(-2,3):
        for j in range(-2,3):
          if (i,j)==(0,0) or (i,j)==(1,0) or (i,j)==(0,1) or (i,j)==(-1,0) or (i,j)==(0,-1):
            continue
          x,y=i+nx,j+ny
          if (0<=x<=h-1) and (0<=y<=w-1):
            if s[x][y]!='#' and visit[x][y]==False:
              st.append((x,y,ncost+1))
    if visit[dh][dw]==False:
      print(-1)
    else:
      print(ans)

if __name__ == '__main__':
    resolve()

### FIXED CODE ###

def solve(h,w,ch,cw,dh,hw,s):
    d=[[1,0],[-1,0],[0,1],[0,-1]]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + d]
    INF=10**12
    path=[[INF]*w for _ in range(h)]
    ans=0
    st=[]
    st=deque()
    st.append((ch,cw,0))
    wp=[]
    wp=deque()
    while st:
      nx,ny,ncost=st.popleft()
      wp.append((nx,ny,ncost))
      path[nx][ny]=ncost
      for dx,dy in d:
        x=nx+dx
        y=ny+dy
        if (0<=x<=h-1) and (0<=y<=w-1):
          if s[x][y]!='#' and path[x][y]>ncost:
            path[x][y]=ncost
            st.append((x,y,ncost))
      if len(st)==0:
        while wp:
          nx,ny,ncost=wp.popleft()
          for dx,dy in warp:
              x,y=nx+dx,ny+dy
              if (0<=x<=h-1) and (0<=y<=w-1):
                if s[x][y]!='#' and path[x][y]>ncost+1:
                  path[x][y]=ncost+1
                  st.append((x,y,ncost+1))
    if path[dh][dw]==INF:
      print(-1)
    else:
      print(path[dh][dw])

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline
    from collections import deque
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    solve(h,w,ch,cw,dh,dw,s)
### BUGGY CODE ###

#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_C&lang=jp
#??????
if __name__ == "__main__":
    n_line = int(input())
    input_list = [tuple(input().split()) for i in range(n_line)]
    dict_list = [s if c == "insert" else "" for c, s in input_list ]
    search_list = [(i,l[1]) for i,l in enumerate(input_list) if l[0] == "find"]
    ans_list = ["yes" if s in dict_list[:i] else "no" for i, s in search_list]
    print("\n".join(ans_list))

### FIXED CODE ###

#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_C&lang=jp
#??????
if __name__ == "__main__":
    n_line = int(input())
    input_list = [tuple(input().split()) for i in range(n_line)]
    l = set([])
    for c, s in input_list:
        if c == "insert":
            l.add(s)
        else:
            if s in l:
                print("yes")
            else:
                print("no")
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
for j in range(m):
  if len(a) != 1:
    if a[0] >= a[1]:
      a[0] //= 2
    else:
      a[1] //= 2
      a.sort(reverse=True)
  else:
    a[0] //= 2
print(sum(a))

### FIXED CODE ###

n, m = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort(reverse=True)

if n > 1:
    a.append(0)
    biggest = a[0]
    now = 0
    while m > 0:
        a[now] = a[now]//2
        m -= 1
        biggest = a[0]
        for i in range(n-1):
            if a[i+1] >= biggest and m > 0:
                a[i+1] = a[i+1]//2
                m -= 1
            else:
                a.sort(reverse=True)
                break
    else:
        quit

else:
  for j in range(m):
    a[0] //= 2

print(sum(a))
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]

#print(n)
#print(a)
answer = 0
for i in range(0,n):
    sum=0
    for j in range(i,n):
        sum = sum + a[j]
        if sum == 0:
            answer += 1

print(answer)



### FIXED CODE ###

import math
import numpy as np

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

#print(n)
#print(a)
answer = 0
b=[0]*(n+1)
for i in range(n):
    b[i+1] = b[i]+a[i]
c=np.sort(b)
#print(b)
#print(c)
renzoku = 0
for i in range(1,n+1):
    if c[i-1] == c[i]:
        renzoku += 1
    elif renzoku > 0:
        answer += renzoku*(renzoku+1)//2
#        print(i,renzoku)
        renzoku = 0
if renzoku > 0:
    answer += renzoku*(renzoku+1)//2  
#    print(i,renzoku)
print(answer)
### BUGGY CODE ###

import numpy as np

h, w = map(int, input().split(' '))
a = [input() for _ in range(h)]
d = [[float('inf') for _ in range(w)] for _ in range(h)]
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

que = []
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            d[i][j] = 0
            if (i + 1 < h and a[i+1][j] == '.') or (i - 1 >= 0 and a[i-1][j] == '.') or (j + 1 < w and a[i][j+1] == '.') or (j - 1 >= 0 and a[i][j-1] == '.'):
                que.append((i, j))


while len(que) > 0:
    y, x = que.pop(0)

    for dy, dx in move:
        ny = y + dy
        nx = x + dx

        if (ny >= 0 and ny < h) and (nx >= 0 and nx < w) and a[ny][nx] == '.' and d[ny][nx] == float('inf'):
            d[ny][nx] = d[y][x] + 1
            if (ny + 1 < h and a[ny + 1][nx] == '.') or (ny - 1 >= 0 and a[ny - 1][nx] == '.') or (nx + 1 < w and a[ny][nx + 1] == '.') or (nx - 1 >= 0 and a[ny][nx - 1] == '.'):
                que.append((ny, nx))

print(np.max(d))


### FIXED CODE ###

import numpy as np


def solve():
    h, w = map(int, input().split(' '))
    max_value = h + w
    values = []
    for i in range(h):
        values.append([0 if i == '#' else max_value for i in list(input())])
    values = np.array(values)

    for x in range(w - 1):
        values[:, x+1] = np.minimum(values[:, x] + 1, values[:, x+1])
    for x in range(w - 1, 0 , -1):
        values[:, x-1] = np.minimum(values[:, x-1], values[:, x] + 1)
    for x in range(h - 1):
        values[x+1, :] = np.minimum(values[x, :] + 1,values[x+1, :])
    for x in range(h - 1, 0, -1):
        values[x-1, :] = np.minimum(values[x, :] + 1, values[x-1, :])
    print(np.max(values))


solve()