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

import sys
sys.setrecursionlimit(10 ** 9)
import numpy as np

h,w= map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

ans = 0
for i in range(h):
    maze[i] = input()

INF = 10000

def dfs(y,x,flg,cnt):
    if y == h-1 and x ==w-1:
        return cnt
    ans = [INF]
    for (ny, nx) in [(y+1, x), (y, x+1)]:
        if 0 <= nx < w and 0 <= ny < h:
            if maze[ny][nx] != maze[y][x]:
                if flg == 0: ans.append(dfs(ny,nx,1,cnt))
                else: ans.append(dfs(ny,nx,0,cnt+1))
            else:
                ans.append(dfs(ny,nx,flg,cnt))
    return(min(ans))

print(dfs(0,0,(0 if maze[0][0]=='.' else 1),(0 if maze[0][0]=='.' else 1)))


### FIXED CODE ###

from functools import lru_cache
h,w= map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

ans = 0
for i in range(h):
    maze[i] = input()

INF = 10000

@lru_cache(None)
def dfs(y,x,flg,cnt):
    if y == h-1 and x ==w-1:
        if flg ==1:
            cnt+=1
        return cnt
    ans = [INF]
    for (ny, nx) in [(y+1, x), (y, x+1)]:
        if 0 <= nx < w and 0 <= ny < h:
            if maze[ny][nx] != maze[y][x]:
                if flg == 0: ans.append(dfs(ny,nx,1,cnt))
                else: ans.append(dfs(ny,nx,0,cnt+1))
            else:
                ans.append(dfs(ny,nx,flg,cnt))
    return(min(ans))

print(dfs(0,0,(0 if maze[0][0]=='.' else 1),0))
### BUGGY CODE ###

import heapq
def main():
    N, M, S = map(int, input().split())
    money_max = 50*N
    S = min(S, money_max-1)
    dp = [[float("inf")]*(money_max) for _ in range(N)]
    dp[0][S] = 0
    G = [[] for _ in range(N)]
    exchange = [None]*N
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u, v = u-1, v-1
        G[u].append([v, a, b])
        G[v].append([u, a, b])
    for i in range(N):
        c, d = map(int, input().split())
        exchange[i] = [c, d]
    q = []
    heapq.heapify(q)
    heapq.heappush(q, [0, 0])
    time_min = [float("inf")]*N
    time_min[0] = 0
    while 0 < len(q):
        pre_time, p = heapq.heappop(q)
        if time_min[p] < pre_time:
            continue
        for i in range(money_max - exchange[p][0]):
            if dp[p][i] < float("inf"):
                dp[p][i+exchange[p][0]] = min(dp[p][i+exchange[p][0]], dp[p][i] + exchange[p][1])
        for to, money, time in G[p]:
            f = False
            for i in range(money, money_max):
                if dp[p][i] < float("inf") and dp[to][i-money] > dp[p][i] + time:
                    dp[to][i-money] = dp[p][i] + time
                    if dp[to][i-money] < time_min[to]:
                        time_min[to] = dp[to][i-money]
                    f = True
            if f:
                heapq.heappush(q, [time_min[to], to])
    for i in range(1, N):
        print(time_min[i])

if __name__ == "__main__":
    main()

### FIXED CODE ###

import heapq
def main():
    N, M, S = map(int, input().split())
    money_max = 50*N
    S = min(S, money_max)
    dp = [[float("inf")]*(money_max+1) for _ in range(N)]
    dp[0][S] = 0
    G = [[] for _ in range(N)]
    exchange = [None]*N
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u, v = u-1, v-1
        G[u].append([v, a, b])
        G[v].append([u, a, b])
    for i in range(N):
        c, d = map(int, input().split())
        exchange[i] = [c, d]
    q = []
    heapq.heapify(q)
    heapq.heappush(q, [0, 0, S])
    while 0 < len(q):
        pre_time, idx, s = heapq.heappop(q)
        if dp[idx][s] < pre_time:
            continue
        ex = min(s + exchange[idx][0], money_max)
        if dp[idx][s] + exchange[idx][1] < dp[idx][ex]:
            dp[idx][ex] = dp[idx][s] + exchange[idx][1]
            heapq.heappush(q, [dp[idx][ex], idx, ex])
        for to, money, time in G[idx]:
            if money <= s:
                if dp[idx][s] + time < dp[to][s-money]:
                    dp[to][s-money] = dp[idx][s] + time
                    heapq.heappush(q, [dp[to][s-money], to, s-money])
    for i in range(1, N):
        print(min(dp[i]))

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

import collections
N = int(input())
l = []
for _ in range(N):
    s = input()
    l.append(s)
c = collections.Counter(l)
i=0
j=0
ans=[]
while True:
    ans.append(c.most_common()[i][0])
    if i+1<len(c.most_common()):
        if c.most_common()[i+1][1] == c.most_common()[i][1]:
            i+=1
            continue
        else:
            break
    else:
        break
ans.sort()
for _ in range(len(ans)):
    print(ans[_])

### FIXED CODE ###

from collections import defaultdict
N = int(input())
touhyou = defaultdict(int)
for _ in range(N):
    s = input()
    touhyou[s] +=1
touhyou1=dict(sorted(touhyou.items(),key = lambda x: x[1],reverse = True))
maxn=max(touhyou1.values())
ans=[]
for key,val in zip(touhyou1.keys(),touhyou1.values()):
    if val == maxn:
        ans.append(key)

ans=sorted(ans)

for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n=n0()
a=n1()

from math import factorial
def comb(n):
    if n<=1:
        return 0
    if n==2:
        return 1
    return factorial(n)//(factorial(2)*factorial(n-2))

c=[a.count(i) for i in range(1,n+1)]
d=[comb(m) for m in c]
s=sum(d)

for i in range(n):
    print(s-d[a[i]-1]+comb(c[a[i]-1]-1))

### FIXED CODE ###

def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n=n0()
a=n1()

def comb(n):
    if n<=1:
        return 0
    if n==2:
        return 1
    return (n*(n-1))//2

from collections import Counter
c=Counter(a)
# print(c)
d={i:comb(j) for i,j in c.items()}
# print(d)
s=sum(d.values())
# print(s)

for i in a:
    print(s-d[i]+comb(c[i]-1))
### BUGGY CODE ###

N, A, B, C, D = map(int, input().split())
mod = 10 ** 9 + 7

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, N + 2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod - 2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


# n人いたときに、k人組を、x個つくる場合の数
def f(n, k, x):
    return nCr(n, k * x) * factorial[k * x] * pow(factorial[k] ** x, mod-2, mod) * pow(factorial[x], mod-2, mod) % mod


dp = [[0] * (N + 1) for i in range(N + 1)]
dp[0][0] = 1
for k in range(1, N + 1):  # k人からなるグループをこれから作りますよ
    for n in range(N + 1):  # すでにn人は使っちゃってますよ
        if A <= k <= B:  # グループの大きさの条件
            X = [0] + list(range(C, D + 1))
        else:
            X = [0]
        for x in X:
            if n - k * x < 0:  # はみ出る段階で打ち切りますよ
                break
            dp[k][n] += f(n, k, x) * dp[k - 1][n - k * x] % mod

print(dp[N][N])


### FIXED CODE ###

N, A, B, C, D = map(int, raw_input().split())
mod = 10 ** 9 + 7

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in xrange(1, N + 2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod - 2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


# n人いたときに、k人組を、x個つくる場合の数
def f(n, k, x):
    return nCr(n, k * x) * factorial[k * x] * pow(pow(factorial[k], x, mod), mod-2, mod) * inverse[x] % mod


dp = [0] * (N + 1)
dp[0] = 1

for k in xrange(A, B + 1):  # k人からなるグループをこれから作りますよ
    for n in range(1, N + 1)[::-1]:  # すでにn人は使っちゃってますよ
        X = xrange(C, D + 1)
        for x in X:
            if n - k * x < 0:  # はみ出る段階で打ち切りますよ
                break
            dp[n] += f(n, k, x) * dp[n - k * x] % mod

print(dp[N] % mod)
### BUGGY CODE ###

def main():
  def CalExVal(x):
    return (1/2*(x+1))
  N, K = map(int, input().split())
  A = list(map(int, input().split()))


  Ex = list((map(CalExVal, A)))
  temp = len(A)-K + 1
  adjlist = [0]*(temp)
  #adjlist = [sum(list(map(CalExVal, A))[i:(K+i)]) for i in range(temp)]
  res = 0
  for i in range(temp):
      adjlist[i] = sum(Ex[i:(K+i)])
      if res < adjlist[i]:
      	res = adjlist[i]
  print(res)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
  def CalExVal(x):
    return (1/2*(x+1))
  N, K = map(int, input().split())
  A = list(map(int, input().split()))


  Ex = list((map(CalExVal, A)))
  #temp = len(A)-K + 1
  #adjlist = [0]*(temp)
  #adjlist = [sum(list(map(CalExVal, A))[i:(K+i)]) for i in range(temp)]
  tem = sum(Ex[:K])
  res = tem
  for i in range(0,N-K):
      tem = tem - Ex[i] + Ex[i+K]
      if res < tem:
      	res = tem
  print(res)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from operator import mul
from functools import reduce

def C(n,r):
    if n < r: return 0    
    r = min(n-r,r)
    if r == 0: return 1
    nume = reduce(mul, range(n, n - r, -1))
    deno = reduce(mul, range(1,r + 1))
    return nume // deno


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

for i in range(n):
    if E.count(a[i]) == 0:
        E.append(a[i])

m = len(E)

num = [0] * m
comb = [0] * m

for i in range(m):
    num[i] = a.count(E[i])
    comb[i] = C(num[i], 2)

count = sum(comb)

for i in range(n):
    l = E.index(a[i])
    print(count - comb[l] + C(num[l]-1, 2))
    

### FIXED CODE ###


from collections import Counter

def C(n):
    if n < 2: return 0
    return n * (n-1) // 2    
    
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)

count = 0

for i, j in c.items():
    count += C(j)

for i in a:
    m = c[i]
    print(count - m + 1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import collections
N,K=map(int,input().split())
A=list(map(int,input().split()))
m=len(set(A))
#print(m,K)
ans=0
if K>=m:
    print(0)
else:
    c = collections.Counter(A)
    for i in range(m-K):
        ans+=c.most_common()[m-1-i][1]
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import collections
N,K=map(int,input().split())
A=list(map(int,input().split()))
m=len(set(A))
ans=0
if K>=m:
    print(0)
else:
    c = collections.Counter(A)
    c_=c.most_common()
    for i in range(m-K):
        ans+=c_[m-1-i][1]
    print(ans)
### BUGGY CODE ###

N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
    
edges = ABC[:]

 
# 無効グラフなので双方向にする
graph = {}
for a,b,c in edges:
    if not a in graph:
        graph[a] = {}
    if not b in graph:
        graph[b] = {}
    graph[a][b] = c
    graph[b][a] = c
 
 
from heapq import heappush, heappop
 
def dijkstra(graph, start):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))
 
    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]
 

#最短経路
shortest = [[0] * (N+1)]
for i in range(1, N+1):
    shortest.append(dijkstra(graph, i))
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import queue

rest = set(R_LIST[:])

import copy  
def dfs(cost,pre,rest):
    if len(rest) == 0:
        return cost
    
    ret = INT_MAX
    for r in rest:
        if pre == None:
            next_cost = 0
        else:
            next_cost = cost + shortest[pre][r]
        
        if next_cost >= ret:
            continue
            
        next_rest = copy.copy(rest)
        next_rest.remove(r)
        
        tmp_ret = dfs(next_cost, r, next_rest)
        ret = min(ret, tmp_ret)
        
    return ret


print(dfs(0, None, rest))
            
      
        
        



### FIXED CODE ###

N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
    
    
edges = ABC[:]


def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

# グラフ無効グラフ化
graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for x,y,z in edges:
    graph[x][y] = z
    graph[y][x] = z
for i in range(N+1):
    graph[i][i] = 0 #自身のところに行くコストは０

#最短経路
shortest =  warshall_floyd(graph, N+1)
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import queue

rest = set(R_LIST[:])

import copy  
def dfs(cost,pre,rest):
    if len(rest) == 0:
        return cost
    
    ret = INT_MAX
    for r in rest:
        if pre == None:
            next_cost = 0
        else:
            next_cost = cost + shortest[pre][r]
        next_rest = copy.copy(rest)
        next_rest.remove(r)
        
        tmp_ret = dfs(next_cost, r, next_rest)
        ret = min(ret, tmp_ret)
        
    return ret
        
    

print(dfs(0, None, rest))
### BUGGY CODE ###

N=int(input())
s=[sorted(list(input())) for i in range(N)]
s=sorted(s)
count=0
l=[]
for i in range(N-1):
    if s[i][0]==s[i+1][0]:
        l.append(i)
        l.append(i+1)
l.append(N-1)
s=[ s[i] for i in range(N) if i in l  ]
s_l=len(s)
if s_l==0 or s_l==1:
    print(0)
else:
    l=[]
    for i in range(s_l-1):
        if s[i][1] == s[i+1][1]:
            l.append(i)
            l.append(i+1)
    l.append(s_l-1)
    s=[ s[i] for i in range(N) if i in l  ]
    s_l=len(s)
    for i in range(s_l-1):
        for j in range(i+1,s_l):
            if s[i][0]==s[j][0]:
                if s[i]==s[j]:
                    count+=1
    print(count)

### FIXED CODE ###

N=int(input())
S = ["".join(sorted(input())) for _ in range(0, N)]
d={}
result=0
for s in S:
    if s in d.keys():
        result+=d[s]
        d[s]+=1
    else:
        d[s]=1
print(result)
### BUGGY CODE ###

import fractions

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

ans = 0
lst_l = [lst[0]]
lst_r = [lst[n-1]]

for i in range(n-1):
  lst_l.append(fractions.gcd(lst_l[-1], lst[i + 1]))
  lst_r.insert(0, fractions.gcd(lst_r[0], lst[n-2-i]))

for i in range(n-2):
  x = fractions.gcd(lst_l[i], lst_r[i+2])
  if ans < x:
    ans = x
print(max(ans,lst_r[1],lst_l[-2]))

### FIXED CODE ###

import fractions

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

ans = 0
left = [0]
right = [0] * (n+1)

for i in range(n):
  left.append(fractions.gcd(left[-1],lst[i]))
  right[n-1-i] = fractions.gcd(right[n-i],lst[n-1-i])

for i in range(n):
  x = fractions.gcd(left[i], right[i+1])
  if ans < x:
    ans = x
print(ans)
### BUGGY CODE ###

n = int(input())
nums = list(map(int,input().split()))
nums.sort()
unique = []
for i in range(len(nums)):
  flag = 0
  for j in range(len(nums)):
    if i==j:
      continue
    if nums[i]%nums[j] == 0:
      flag = 1
      break
  if flag ==0:
    unique.append(nums[i])
print(len(unique))


### FIXED CODE ###

n = int(input())
nums = list(map(int,input().split()))
nums.sort()
ans = 0
cnt = {}
flag = [0]*1000005
for i in nums:
  cnt[i] = cnt.get(i,0) + 1

for i in nums:
  if flag[i] == 0 and cnt[i] == 1:
    ans += 1
  if flag[i] == 1:
    continue
  for j in range(i,1000001,i):
    flag[j] = 1

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

S = int(input())
listS = list(str(S))
count = 0
for i in range(len(listS)-3):
    for j in range(len(listS)-3-i):
        if int("".join(map(str, listS[j:j+4+i]))) % 2019 == 0:
            count += 1
print(count)

### FIXED CODE ###

S = str(input())
l = len(S)
mod = [0] * 2019
dp = 0
pw = 1
for i in range(l):
    mod[dp % 2019] += 1
    dp = dp + pw * int(S[-1-i])
    pw = (pw * 10) % 2019
mod[dp % 2019] += 1
cnt = 0
for i in range(2019):
    cnt += (mod[i]*(mod[i]-1))//2
print(cnt)
### BUGGY CODE ###

N = int(input())
array = list(map(int,input().split()))
num_sum = 0
tmp_sum = 0

for i in range(N):
    for j in range(N-i-1):
        tmp_sum += array[i+1+j]
    num_sum += tmp_sum*array[i]
    tmp_sum = 0
print(num_sum%1000000007)

### FIXED CODE ###

N = int(input())
array = list(map(int,input().split()))
num_sum = 0
tmp_sum = 0

tmp_sum = sum(array)

for a in array:
    tmp_sum -= a
    num_sum += tmp_sum*a

print(num_sum%1000000007)
### BUGGY CODE ###

N,C = map(int,input().split())
S = []
U = [0]*200001
for i in range(N):
    S.append(list(map(int,input().split())))
for i in range(1,C+1):
    T = [0]*200001
    for j in range(N):
        s,t,r = S[j]
        if r == i:
            T[s*2-1] += 1
            T[t*2] -= 1
    for j in range(1,200001):
        T[j] += T[j-1]
    for j in range(200001):
        if T[j] > 0:
            U[j] += 1
print(max(U))



### FIXED CODE ###

N,C = map(int,input().split())
A = [[0 for _ in range(C)] for j in range(100001)]
for i in range(N):
    s,t,c = map(int,input().split())
    for j in range(s-1,t):
        A[j][c-1] = 1
R = 0
for i in range(100001):
    sumA = sum(A[i])
    if R < sumA:
        R = sumA
print(R)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
S=set(A)
F=[]
for a in S:
    if A.count(a)==1:
        F.append(a)
T=0
for a in F:
    c=0
    for l in S:
        if a%l==0 and a!=l:
            c=1
            break
    if c==0:
        T+=1
print(T)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort()
TF={a:True for a in A}
for i in range(N):
    if TF[A[i]]==True:
        if i > 0 and A[i - 1] == A[i]:
            TF[A[i]] = False
        m=A[N-1]//A[i]
        for j in range(2,m+1):
            s=A[i]*j
            if s in TF:
                TF[s]=False
print(len([1 for a in A if TF[a]==True]))
### BUGGY CODE ###

import itertools

N, M, R = map(int, input().split())
r = tuple(map(int, input().split()))

INF = 10**18

d = {}
for i in range(1, N+1):
    for j in range(1, N+1):
        d[(i, j)] = INF
    d[(i, i)] = 0

for _ in range(M):
    a, b, c = map(int, input().split())

    if d[(a, b)] > c:
        d[(a, b)] = c
        d[(b, a)] = c


for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            d[(i, j)] = min(d[(i, j)], d[(i, k)] + d[(k, j)])


ans = INF
for p in itertools.permutations(r):
    dist = 0
    for i in range(R-1):
        dist += d[(p[i], p[i+1])]

    ans = min(ans, dist)

print(ans)

### FIXED CODE ###

import itertools
from scipy.sparse.csgraph import floyd_warshall

N, M, R = map(int, input().split())
r = tuple(map(int, input().split()))

INF = 10**10

d = [[INF] * N for _ in range(N)]

for i in range(N):
    d[i][i] = 0

for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    if d[a][b] > c:
        d[a][b] = c
        d[b][a] = c

# for k in range(N):
#     for i in range(N):
#         for j in range(N):
#             d[i][j] = min(d[i][j], d[i][k] + d[k][j])

d = floyd_warshall(d)


ans = INF
for p in itertools.permutations(r):
    dist = 0
    for i in range(R-1):
        dist += d[p[i]-1][p[i+1]-1]

    ans = min(ans, dist)

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

import sys
from bisect import bisect_left
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

h, w = lmi()
s = [input() for i in range(h)]

a = [[] for i in range(h)]
#al = [[] for i in range(h)]
b = [[] for i in range(w)]
bl = [[] for i in range(w)]
for i in range(h):
    k = 0
    for j in range(w):
        if s[i][j] == '.':
            k += 1
            if j == w-1:
                a[i].append(k)
                #al[i].append(j)
        elif j != 0 and s[i][j-1] == '.':
            a[i].append(k)
            #al[i].append(j-1)
            k = 0

for i in range(w):
    k = 0
    for j in range(h):
        if s[j][i] == '.':
            k += 1
            if j == h-1:
                b[i].append(k)
                bl[i].append(j)
        elif j != 0 and s[j-1][i] == '.':
            b[i].append(k)
            bl[i].append(j-1)
            k = 0
'''
print(a)
print(al)
print(b)
print(bl)
'''

ans = 0
for i in range(h):
    k = 0
    c = -1
    for j in range(w):
        if s[i][j] == '.':
            c = a[i][k]
            d = b[j][bisect_left(bl[j], i)]
            #print(c,d)
            ans = max(ans, c+d-1)
        elif j != 0 and s[i][j-1] == '.' and c != -1:
                k += 1
print(ans)


### FIXED CODE ###

import sys
from bisect import bisect_left
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

h, w = lmi()
s = [input() for i in range(h)]

a = [[] for i in range(h)]
al = [[] for i in range(h)]
b = [[] for i in range(w)]
bl = [[] for i in range(w)]
for i in range(h):
    k = 0
    for j in range(w):
        if s[i][j] == '.':
            k += 1
            if j == w-1:
                a[i].append(k)
                al[i].append(j)
        elif j != 0 and s[i][j-1] == '.':
            a[i].append(k)
            al[i].append(j-1)
            k = 0

for i in range(w):
    k = 0
    for j in range(h):
        if s[j][i] == '.':
            k += 1
            if j == h-1:
                b[i].append(k)
                bl[i].append(j)
        elif j != 0 and s[j-1][i] == '.':
            b[i].append(k)
            bl[i].append(j-1)
            k = 0
'''
print(a)
print(al)
print(b)
print(bl)
'''

ans = 0
for i in range(h):
    k = 0
    c = -1
    for j in range(w):
        if s[i][j] == '.':
            c = a[i][k]
            d = b[j][bisect_left(bl[j], i)]
            #print(c,d)
            ans = max(ans, c+d-1)
        elif j != 0 and s[i][j-1] == '.' and c != -1:
                k += 1
print(ans)
### BUGGY CODE ###

import itertools
def count(string):
    sets = list(set(string))
    return {s: string.count(s) for s in sets}

def infer(match):
    match_num = 0
    for x, y in itertools.combinations(match, 2):
        if x == y:
            match_num += 1
    
    return match_num

N = int(input())
sents = [count(input()) for i in range(N)]
ans = infer(sents)
print(ans)

### FIXED CODE ###

N = int(input())
dicts = {}
for i in range(N):
    s = "".join(sorted(input()))
    dicts[s] = dicts[s] + 1 if s in dicts.keys() else 1

num = 0
for k, v in dicts.items():
  num += v * (v-1) // 2
print(num)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for _ in range(n-1)]
ki=[[] for _ in range(n)]
for i,x in enumerate(a):
  ki[x-1].append(i+1)

ans=0
import sys
sys.setrecursionlimit(10**7)
def marge(arg):
  ret=0
  while True:
    flg=True
    endflg=True
    for i in range(len(arg)):
      if arg[i]>1:
        arg[i]-=1
        endflg=False
      elif arg[i]==1 and flg:
        arg[i]-=1
        endflg=False
        flg=False
      else:
        pass
    if endflg:
      return ret
    ret+=1

def dfs(v):
  ret=[]
  if len(ki[v])==0:return 1
  for nv in ki[v]:
    ret.append(dfs(nv))
  return marge(ret)+1
print(dfs(0)-1)


### FIXED CODE ###

n=int(input())
a=[int(input()) for _ in range(n-1)]
ki=[[] for _ in range(n)]
for i,x in enumerate(a):
  ki[x-1].append(i+1)

ans=0
import sys
sys.setrecursionlimit(10**7)
from collections import Counter
def marge(arg):
  ret=0
  arg.sort(reverse=True)
  for i,x in enumerate(arg):
    ret=max(ret,i+1+x)
  return ret


def dfs(v):
  ret=[]
  if len(ki[v])==0:return 0
  for nv in ki[v]:
    ret.append(dfs(nv))
  return marge(ret)
print(dfs(0))