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

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


def ncr(n):
    return n*(n-1) // 2

dmemo = {}
for a in A:
    dmemo.setdefault(a, 0)
    dmemo[a] += 1

cmemo = {}

for a in A:
    ans = 0
    for dk, dv in dmemo.items():
        if dk == a:
            dv -= 1
        
        if dv not in cmemo:
            val = ncr(dv)
            cmemo[dv] = val
        ans += cmemo[dv]
    print(ans)


### FIXED CODE ###

from sys import stdin

N = int(input())
readline = stdin.readline
A = list(readline().split())

def ncr(n):
    return n*(n-1) // 2

dmemo = {}
for a in A:
    dmemo.setdefault(a, 0)
    dmemo[a] += 1

max_num = 0
cmemo = {}
for dk, dv in dmemo.items():
    if dv not in cmemo:
        val = ncr(dv)
        cmemo[dv] = val
    max_num += cmemo[dv]

for a in A:
    val = dmemo[a]
    a1 = ncr(val)
    a2 = ncr(val-1)
    ans = max_num - a1 + a2
    print(ans)
### BUGGY CODE ###

s=input()
t=input()
ls=len(s)
lt=len(t)
dp=[[""]*(lt+1) for i in range(ls+1)]
for i in range(ls):
  for j in range(lt):
    if len(dp[i+1][j])==max(len(dp[i][j+1]),len(dp[i+1][j]),len(dp[i][j])+(s[i]==t[j])):
      dp[i+1][j+1]=dp[i+1][j]
    elif len(dp[i][j+1])==max(len(dp[i][j+1]),len(dp[i+1][j]),len(dp[i][j])+(s[i]==t[j])):
      dp[i+1][j+1]=dp[i][j+1]
    elif len(dp[i][j])+(s[i]==t[j])==max(len(dp[i][j+1]),len(dp[i+1][j]),len(dp[i][j])+(s[i]==t[j])):
      a=list(dp[i][j])
      a.append(s[i])
      dp[i+1][j+1]="".join(a)
print(dp[ls][lt])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
s=input()
t=input()
ls=len(s)
lt=len(t)
dp=[[0]*(lt+1) for i in range(ls+1)]
for i in range(ls):
  for j in range(lt):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+1
    else:
      dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
                                                                                                    
ans=""
def rec(i,j):
  if i==0 or j==0:
    return 
  global ans
  if s[i-1]==t[j-1]:
    ans+=s[i-1]
    rec(i-1,j-1)
  elif dp[i-1][j]>=dp[i][j-1]:
    rec(i-1,j)
  else:
    rec(i,j-1)
rec(ls,lt)
print(ans[::-1])
### BUGGY CODE ###

N,P=map(int,input().split())
for x in range(int(pow(P,1/N))+1,0,-1):
  if P%(x**N)==0:
    print(x)
    exit()

### FIXED CODE ###

def primes(n):
  ps = {}
  while n%2==0:
    n//=2
    if 2 not in ps:
      ps[2] = 1
    else:
      ps[2] += 1
  
  for i in range(3,int(n**.5)+1,2):
    while n%i==0:
      n//=i
      if i not in ps:
        ps[i] = 1
      else:
        ps[i] += 1
  
  if n!=1:
    ps[n] = 1
  
  return ps
  
N,P = map(int,input().split())
if N==1:
  print(P)
  exit()
ps = primes(P)
ans = 1
for p, num in ps.items():
  if num>=N:
    ans *= p**(num//N)
print(ans)
### BUGGY CODE ###

N,Q = map(int, input().split())
answer = (N-2)**2

q1 = [(N,N-2)]
q2 = [(N,N-2)]

def binary_search(q,n):
  left = 0
  right = len(q)-1
  while right-left>0:
    index = (left+right)//2
    if q[index][0] < n:
      left = index+1
    else:
      right = index
  return left

for _ in range(Q):
  n,x = map(int, input().split())
  if n == 1:
    index = binary_search(q1[::-1],x)
    q = q1[-index-1]
    answer -= q[1]
    if index == 0:
      q1.append((x,q[1]))
      q2_last = q2[-1]
      q2[-1] = (q2_last[0],x-2)
  if n == 2:
    index = binary_search(q2[::-1],x)
    q = q2[-index-1]
    answer -= q[1]
    if index == 0:
      q2.append((x,q[1]))
      q1_last = q1[-1]
      q1[-1] = (q1_last[0],x-2)
      
print(answer)

### FIXED CODE ###

N,Q = map(int, input().split())
answer = (N-2)**2

q1 = [(N,N-2)]
q2 = [(N,N-2)]

def binary_search(q,n):
  left = 0
  right = len(q) - 1
  while right > left:
    index = (left + right) // 2
    if q[index+1][0] > n:
      left = index + 1
    else:
      right = index
  return left

for _ in range(Q):
  n,x = map(int, input().split())
  if n == 1:
    index = binary_search(q1,x)
    q = q1[index]
    answer -= q[1]
    if index == len(q1)-1:
      q1.append((x,q[1]))
      q2_last = q2[-1]
      q2[-1] = (q2_last[0],x-2)
  if n == 2:
    index = binary_search(q2,x)
    q = q2[index]
    answer -= q[1]
    if index == len(q2)-1:
      q2.append((x,q[1]))
      q1_last = q1[-1]
      q1[-1] = (q1_last[0],x-2)
      
print(answer)
### BUGGY CODE ###

S = input()
N = len(S)
ans = 0
for i in range(0, N - 3):
    j = i + 4
    while j <= N:
        if int(S[i: j]) % 2019 == 0:
            ans += 1
            break
        else:
           j += 1
print(ans)

### FIXED CODE ###

import collections
S = input()[::-1]
N = len(S)
mod = 2019

ans = 0
x = [0] * N
x[0] = int(S[0]) % mod
ruijo = 10

for i in range(1, N):
    x[i] = (ruijo * int(S[i]) + x[i - 1]) % mod
    if x[i] % mod == 0:
        ans += 1
    ruijo *= 10
    ruijo %= mod
    
d = collections.Counter(x)

for i in d.values():
    ans += i * (i - 1) // 2
    
print(ans)
### BUGGY CODE ###

from itertools import combinations
n = int(input())

march = ("M","A","R","C","H")
d = []
for _ in range(n):
  pre = input()[0]
  if pre in march: d.append(pre)

if len(d) < 3:
  print(0)
  exit()

ans = 0
for i in combinations(d,3):
  if len(set(i)) == 3:
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())

march = ("M","A","R","C","H")
prefix = []
d = {}
for _ in range(n):
  pre = input()[0]
  if pre in march:
    if pre not in prefix:
      prefix.append(pre)
      d[pre] = 1
    else:
      d[pre] += 1
      
t = len(prefix)
if t < 3:
  print(0)
  exit()

ans = 0
for i in range(t-2):
  for j in range(i+1, t-1):
    for k in range(j+1,t):
      ans += d[prefix[i]]*d[prefix[j]]*d[prefix[k]]
print(ans)
### BUGGY CODE ###

def f(n, a):
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 2, -1, -1):
        s = a[i]
        dpi=dp[i]
        for j in range(i + 1, n):
            k = []
            s += a[j]
            for d in range(i, j):
                k += [dpi[d] + dp[d + 1][j]]
            dp[i][j] = min(k) + s
    return dp[0][-1]


n = int(input())
a = tuple(map(int, input().split()))
print(f(n, a))


### FIXED CODE ###

def f(n, a):
    inf = float("inf")
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 2, -1, -1):
        s = a[i]
        dpi = dp[i]
        for j in range(i + 1, n):
            mn = inf
            s += a[j]
            for d in range(i, j):
                k = dpi[d] + dp[d + 1][j]
                if k < mn:
                    mn = k
            dpi[j] = mn + s
    return dp[0][-1]


n = int(input())
a = tuple(map(int, input().split()))
print(f(n, a))
### BUGGY CODE ###

H, W = [int(i) for i in input().split(" ")]
S = []
for i in range(H):
  S.append(input())
  
import numpy as np

r_lens = []
for s in S:
  counts = [len(block) for block in s.split("#")]
  
  r_len = []
  for c in counts:
    r_len+=[c]*c
    r_len+=[0]
  r_len.pop()
  r_lens.append(r_len)
r_lens = np.array(r_lens)

S2 = [""]*W
for h in range(H):
  for w in range(W):
    S2[w] += S[h][w]
    
c_lens = []
for s in S2:
  counts = [len(block) for block in s.split("#")]
  
  c_len = []
  for c in counts:
    c_len+=[c]*c
    c_len+=[0]
  c_len.pop()
  c_lens.append(c_len)
c_lens = np.array(c_lens)

print((r_lens+c_lens.T-1).max())

### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
S = []
for h in range(H):
  S.append(list(map(lambda s:0 if s=='#' else 1, input())))
S = np.array(S)
 
l,r,u,d = [np.zeros([H,W], dtype=int) for _ in range(4)]

for w in range(W):
  l[:,w] = (l[:,w-1]+1)*S[:,w]
  r[:,-w-1] = (r[:,-w]+1)*S[:,-w-1]

for h in range(H):
  u[h] = (u[h-1]+1)*S[h]
  d[-h-1] = (d[-h]+1)*S[-h-1]
  
ans = np.max((l+r+u+d-3)*S)

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

n, m = map(int, input().split())
mod = pow(10, 9)+7
ans = 0
a = 1
b = 1
c = 1
for i in range(m-n+1, m+1):
  b *= i
  b %= mod
for i in range(n+1):
  k = -1 if i%2 else 1
  ans += k*a*b**2*c
  ans %= mod
  a *= m-i
  a %= mod
  b *= pow(m-i, mod-2, mod)
  b %= mod
  c *= n-i
  c *= pow(i+1, mod-2, mod)
  c %= mod
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
mod = pow(10, 9)+7
ans = 0
a = 1
b = 1
c = 1
for i in range(m-n+1, m+1):
  b *= i
  b %= mod
for i in range(n+1):
  k = -1 if i%2 else 1
  ans += k*a*b**2*c
  ans %= mod
  a *= m-i
  a %= mod
  b *= pow(m-i, mod-2, mod)
  b %= mod
  c *= n-i
  c *= pow(i+1, mod-2, mod)
  c %= mod
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,*p = map(int,read().split())
N = n*n

dist = [0]*N

for a in range(n):
    for b in range(n):
        dist[a*n+b] = min(a,n-1-a,b,n-1-b)

#print(dist)


#ans = [0]*N
ans = 0
iru = [1]*N

for pi in p:
    pi -= 1

    ans += dist[pi]
    iru[pi] = 0

    q = [pi]
    #更新
    
    while q:
        #print(q)
        v = q.pop()
        for i in [-n,-1,1,n]:
            if i==1 and v%n==n-1: continue
            if i==-1 and v%n==0: continue
            nv = v+i
            if 0 <= nv < N and dist[nv] > dist[v] + iru[v]:
                q.append(nv)
                dist[nv] = dist[v] + iru[v]
        
                    
    #print(dist)        

print(ans)









### FIXED CODE ###

# coding: utf-8
# Your code here!

import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,*p = map(int,read().split())
N = n*n

dist = [0]*N

for a in range(n):
    for b in range(n):
        dist[a*n+b] = min(a,n-1-a,b,n-1-b)

#print(dist)


#ans = [0]*N
ans = 0
iru = [1]*N

for pi in p:
    pi -= 1

    ans += dist[pi]
    iru[pi] = 0

    q = [pi]
    #更新
    
    while q:
        #print(q)
        v = q.pop()
        for i in [-n,-1,1,n]:
            if i==1 and v%n==n-1: continue
            if i==-1 and v%n==0: continue
            nv = v+i
            if 0 <= nv < N and dist[nv] > dist[v] + iru[v]:
                q.append(nv)
                dist[nv] = dist[v] + iru[v]
        
                    
    #print(dist)        

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

N = int(input())
List = list(map(int, input().split()))
res = 0
New_List = sorted(List)
Flag = [1]*N
for i in range(N):
  if Flag[i] ==1:
    for j in range(i+1,N):
      if New_List[i] == New_List[j]:
        Flag[i] = 0
        Flag[j] = 0
      elif New_List[j] % New_List[i] ==0:
        Flag[j] = 0
      else:
        pass
  else:
    pass
res = Flag.count(1)
print(res)

### FIXED CODE ###

N = int(input())
List = list(map(int, input().split()))
res = 0
List.sort()
K = List[N-1]+1
Flag = [1]*K
for i in range(N):
  if Flag[List[i]] ==1:
    res +=1
    for j in range(List[i],K,List[i]):
      Flag[j] = 0
    if i != N-1 and List[i] == List[i+1]:
      res += -1
print(res)
### BUGGY CODE ###

N,K = map(int, input().split())
l = list(map(int,input().split()))

m = 0
for i in range(len(l)-(K-1)):
    if m < sum(l[i:i+K]):
        m = sum(l[i:i+K])
        t = l[i:i+K]
        
def E(n):
    return sum(range(1,n+1)) / n

l2 = list(map(E, t))

print(sum(l2))

### FIXED CODE ###

N,K = map(int, input().split())
l = list(map(int,input().split()))
 
def E(n):
  return (1 + n) / 2
 
j = sum(l[0:0+K])
m = 0
if N == 1:
  l2 = list(map(E, l))
  print(sum(l2))
elif N == K:
  l2 = list(map(E, l))  
  print(sum(l2))
else:
  for i in range(1,len(l)-(K-1)):
      j = j - l[i-1] + l[i+K-1]
      if l[i] < l[i-1]:
          continue
      elif m < j:
          m = j
          t = l[i:i+K]

  l2 = list(map(E, t))
 
  print(sum(l2))
### BUGGY CODE ###

n,k=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(2*n):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
ans=comb(2*n-1,n-1)
for i in range(n-1,k,-1):ans=(ans-comb(n,n-i)*comb(n-1,i))%mod
print(ans)

### FIXED CODE ###

mod=10**9+7
f=[1]
for i in range(10**6):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod

n,k=map(int,input().split())
ans=comb(n*2-1,n-1)
if k>=n-1:print(ans);exit()
for i in range(n-1,k,-1):
  #ansからi回の操作では不可能な組み合わせを引く
  #0*i + any*(n-i)
  #つまり((n-i)個の部屋にn人が入る組み合わせ)*nC(n-i)
  #各部屋には必ず1人は入る
  #つまり(n-1)Ci
  anss=comb(n-1,i)*comb(n,n-i)%mod
  ans=ans+(mod-anss)
  ans%=mod
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

d={}

def c(s):
	a = [0] * 10
	for i in s:
		a[int(i)] += 1
	if a[3] != 0 and a[5] != 0 and a[7] != 0:
		return True
	else:
		return False

def r(m, s):
	global d
	if s == "":
		pass
	elif m < int(s) or (s in d):
		return 0
	ret = 0
	if c(s):
		ret += 1
		d[s] = 1
	ret += r(m,s+"3")
	ret += r(m,s+"5")
	ret += r(m,s+"7")
	ret += r(m,"3"+s)
	ret += r(m,"5"+s)
	ret += r(m,"7"+s)
	return ret

def main():
	n = int(input())
	print(r(n,""))
	return
main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

d={}

def c(s):
	a = [0] * 10
	for i in s:
		a[int(i)] += 1
	if a[3] != 0 and a[5] != 0 and a[7] != 0:
		return True
	else:
		return False

def r(m, s):
	global d
	if s == "":
		pass
	elif m < int(s) or (s in d):
		return 0
	ret = 0
	if c(s):
		ret += 1
	d[s] = 1
	ret += r(m,s+"3")
	ret += r(m,s+"5")
	ret += r(m,s+"7")
	ret += r(m,"3"+s)
	ret += r(m,"5"+s)
	ret += r(m,"7"+s)
	return ret

def main():
	n = int(input())
	print(r(n,""))
	return
main()
### BUGGY CODE ###

#abc093 b
a,b,k=map(int,input().split())
ans=[]
for i in range(a,b+1):
    if i<=a+k-1 or b-k+1<=i:
        print(i)
    else:
        continue


### FIXED CODE ###

#abc093 b
a,b,k=map(int,input().split())
l1=[i for i in range(a,min(a+k,b+1))]
l2=[i for i in range(max(a,b-k+1),b+1)]
ans=set(l1+l2)
for i in sorted(ans):
    print(i)
### BUGGY CODE ###

S = list(map(str,input()))

counter = 0

for i in range(len(S)):
    for j in range(i+3,len(S)):
        s = int("".join(S[i:j+1]))
        if s % 2019 == 0:
            counter += 1

print(counter)


### FIXED CODE ###

S = list(map(int,input()))[::-1] #逆順

counter = 0
amari = [0]*2019
amari[0] = 1

s,d = 0,1

for i in S:
    s += i *d
    amari[s%2019] += 1
    d *= 10
    d %= 2019


for i in range(2019):
    counter += amari[i] * (amari[i]-1) / 2


print(int(counter))
### BUGGY CODE ###

n = int(input())
vs = list(map(int, input().split()))
cs = list(map(int, input().split()))

ret = - float('inf')
for i in range((2 ** n)):
    total_cost = 0
    total_value = 0
    j = 0
    while i > 0:
        if i & 1:
            total_cost += cs[j]
            total_value += vs[j]
        i >>= 1
        j += 1
    ret = max(ret, total_value - total_cost)
print(ret)


### FIXED CODE ###

n = int(input())
vs = list(map(int, input().split()))
cs = list(map(int, input().split()))

# ret = - float('inf')
# for i in range((2 ** n)):
#     total_cost = 0
#     total_value = 0
#     j = 0
#     while i > 0:
#         if i & 1:
#             total_cost += cs[j]
#             total_value += vs[j]
#         i >>= 1
#         j += 1
#     ret = max(ret, total_value - total_cost)
# print(ret)

x = 0
y = 0
for i in range(n):
    if vs[i] > cs[i]:
        x += vs[i]
        y += cs[i]
print(x - y)
### BUGGY CODE ###

import sys


def isprime(x):
    # 素数判定
    if x == 2:
        return True
    if x < 2 or x % 2 == 0:
        return False
    i = 3
    while i <= x ** 0.5:
        if x % i == 0:
            return False
        i += 2
    return True


def solve(l, r, primelist, primelist2):
    res = 0
    for i in range(l, r + 1, 2):
        if primelist[i] and primelist2[i]:
            res += 1
    return res


input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    primelist = [False] * (10 ** 5 + 10)
    primelist2 = [False] * (10 ** 5 + 10)
    primelist[2] = True
    for i in range(1, 10 ** 5 + 1, 2):
        if isprime(i):
            primelist[i] = True
    for i in range(1, 10 ** 5 + 1, 2):
        if primelist[(i + 1) // 2]:
            primelist2[i] = True
    # print(primelist[:20])
    Q = int(input())
    for i in range(Q):
        l, r = map(int, input().split())
        print(solve(l, r, primelist, primelist2))


if __name__ == "__main__":
    main()


### FIXED CODE ###

MAX = 10 ** 5 + 1
f = [True] * (MAX)
c = [0] * (MAX + 1)
for i in range(2, MAX):
    if f[i]:
        for j in range(i + i, MAX, i):
            f[j] = False
for i in range(3, MAX, 2):
    if f[i] and f[(i + 1) // 2]:
        c[i] += 1
for i in range(3, MAX):
    c[i] += c[i - 1]

Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(c[r] - c[l - 1])
### BUGGY CODE ###

import itertools

n = int(input())
# s = [set(input()) for _ in range(n)]
s = sorted([sorted(input()) for _ in range(n)])

# print(s)

ans = 0
cnt = 0
for i in range(n-1):
    if i == n-2 and s[i] == s[i+1]:
        cnt += 1
        ans += len(list(itertools.combinations(range(cnt+1), 2)))
    if s[i] == s[i+1]:
        cnt += 1
    else:
        ans += len(list(itertools.combinations(range(cnt+1), 2)))
        cnt = 0
print(ans)


### FIXED CODE ###

def nCr(n, r):
    r = min(r, n-r)

    numerator = 1
    for i in range(n, n-r, -1):
        numerator *= i

    denominator = 1
    for i in range(r, 1, -1):
        denominator *= i

    return numerator // denominator


n = int(input())
s = sorted([sorted(input()) for _ in range(n)])


ans = 0
cnt = 0
for i in range(n-1):
    if i == n-2 and s[i] == s[i+1]:
        cnt += 1
        ans += nCr(cnt+1, 2)
        print(ans)
        exit()
    if s[i] == s[i+1]:
        cnt += 1
    else:
        if cnt > 0:
            ans += nCr(cnt+1, 2)
            cnt = 0
print(ans)
### BUGGY CODE ###

def f(p):
    ans=0
    if p<=5: return ans
    for n in range(1,int(p/2)+1):
        if p%n==0:ans+=n
    return ans

while 1:
    n=int(input())
    if n==0:break
    m=f(n)
    if n==m:print('perfect number')
    else: print('deficient number' if n>m else 'abundant number')

### FIXED CODE ###

def f(p):
    ans=1
    if p<=5: return 0
    for n in range(2,int(p**0.5)+1):
        if p%n==0:
            if n!=p//n:ans+=n+p//n
            else:ans+=n
    return ans

while 1:
    n=int(input())
    if n==0:break
    m=f(n)
    if n==m:print('perfect number')
    else: print('deficient number' if n>m else 'abundant number')
### BUGGY CODE ###

from bisect import bisect_left
import sys

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

if N == 1:
    for i in range(M):
        A[0] = A[0] // 2
    print(sum(A))
    sys.exit()

A.sort(reverse=True)
for i in range(M):
    A[0] = (A[0]) // (2)
    if A[0] < A[1]:
        A.sort(reverse=True)

print(sum(A))

### FIXED CODE ###

import heapq
import sys

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

if N == 1:
    for i in range(M):
        A[0] = A[0] // 2
    print(sum(A))
    sys.exit()
h = []
for i in range(N):
    heapq.heappush(h, -A[i])

for i in range(M):
    tmp = heapq.heappop(h)
    tmp = -(-tmp // 2)
    heapq.heappush(h, tmp)


print(-sum(h))
### BUGGY CODE ###

import numpy as np
from sys import stdin
H, W = [int(_) for _ in stdin.readline().rstrip().split()]
S = [stdin.readline().rstrip() for _ in range(H)]

left = np.zeros((H,W), dtype=int)
right = np.zeros((H,W), dtype=int)
up = np.zeros((H,W), dtype=int)
down = np.zeros((H,W), dtype=int)

for i in range(H):
    p = 0
    for j in range(W):
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        left[i][j] = p
for i in range(H):
    p = 0
    for j in range(W)[::-1]:
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        right[i][j] = p
for j in range(W):
    p = 0
    for i in range(H):
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        up[i][j] = p
for j in range(W):
    p = 0
    for i in range(H)[::-1]:
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        down[i][j] = p

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        ans = max(ans, left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3) 

print(ans)

### FIXED CODE ###

from sys import stdin
H, W = [int(_) for _ in stdin.readline().rstrip().split()]
S = [stdin.readline().rstrip() for _ in range(H)]

left = [[0]*W for i in range(H)]
right = [[0]*W for i in range(H)]
up = [[0]*W for i in range(H)]
down = [[0]*W for i in range(H)]

for i in range(H):
    p = 0
    for j in range(W):
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        left[i][j] = p
for i in range(H):
    p = 0
    for j in range(W)[::-1]:
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        right[i][j] = p
for j in range(W):
    p = 0
    for i in range(H):
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        up[i][j] = p
for j in range(W):
    p = 0
    for i in range(H)[::-1]:
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        down[i][j] = p

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        ans = max(ans, left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3) 

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

import sys
n, m = map(int, input().split())
if m==0:
    print("Yes")
    sys.exit()

tree = [[] for _i in range(n+1)]
for _i in range(m):
    l, r, d = map(int, input().split())
    tree[l].append([r, d])
    tree[r].append([l, -d])

from collections import deque
INF = "INF"
visit = [INF for _i in range(n+1)]
for i in range(1, n+1):
    if visit[i]==INF:
        visit[i] = 0
    else:
        continue
    q = deque([i])
    while q:
        p = q.popleft()
        if visit[p]==INF:
            visit[p] = 0
        for i, j in tree[p]:
            if i==p:
                continue
            elif visit[i] == INF:
                visit[i] = visit[p]+j
                q.append(i)
            elif visit[i] == visit[p]+j:
                continue
            else:
                print("No")
                sys.exit()

print("Yes")

### FIXED CODE ###

import sys
n, m = map(int, input().split())
if m==0:
    print("Yes")
    sys.exit()

tree = [[] for _i in range(n+1)]
for _i in range(m):
    l, r, d = map(int, input().split())
    tree[l].append([r, d])
    tree[r].append([l, -d])

from collections import deque
INF = "INF"
visit = [INF for _i in range(n+1)]
for i in range(1, n+1):
    if visit[i]==INF:
        visit[i] = 0
    else:
        continue
    q = deque([i])
    while q:
        p = q.popleft()
        if visit[p]==INF:
            visit[p] = 0
        for i, j in tree[p]:
            if i==p:
                continue
            elif visit[i] == INF:
                visit[i] = visit[p]+j
                q.append(i)
            elif visit[i] == visit[p]+j:
                continue
            else:
                print("No")
                sys.exit()

print("Yes")
### BUGGY CODE ###

s = input()
s_base = int(s.replace('?', '0'))
digit = reversed(list(s))
sumd = 0
s10 = 4 # Before 1
hatena = []
for i, x in enumerate(digit):
    s10 = (10 * s10) % 13
    if x == '?':
        hatena.append(s10)
    else:
        sumd += int(x) * s10
        sumd %= 13

# sum( hatena[i] * x ) を満たすxの組み合わせを求める
mod = 10**9 + 7

dp = [[0] * 13 for _ in range(len(hatena) + 2)]
# dp[i][x] hatena[:i]の和を13で割った余りがxである整数の数
dp[0][0] = 1

for i in range(len(hatena)):
    for x in range(13):
        for num in range(10):
            j = (x + num*hatena[i]) % 13
            dp[i+1][j] += dp[i][x]
            dp[i+1][j] %= mod

print(dp[len(hatena)][(5-sumd)%13])
"""
print(hatena)
print(sumd)
print(dp)
"""


### FIXED CODE ###

s = input()
s_base = int(s.replace('?', '0'))
digit = reversed(list(s))
sumd = 0
s10 = 4 # Before 1
hatena = []
for i, x in enumerate(digit):
    s10 = (10 * s10) % 13
    if x == '?':
        hatena.append(s10)
    else:
        sumd += int(x) * s10
        sumd %= 13

# sum( hatena[i] * x ) を満たすxの組み合わせを求める
mod = 10**9 + 7

dp = [[0] * 13 for _ in range(len(hatena) + 2)]
# dp[i][x] hatena[:i]の和を13で割った余りがxである整数の数
dp[0][0] = 1

for i in range(len(hatena)):
    for x in range(13):
        for num in range(10):
            j = (x + num*hatena[i]) % 13
            dp[i+1][j] += dp[i][x]
            dp[i+1][j] %= mod

print(dp[len(hatena)][(5-sumd)%13])
"""
print(hatena)
print(sumd)
print(dp)
"""