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

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n = int(input())
A = list(map(int, input().split()))
all_pattern = n * (n+1) // 2
check = all_pattern // 2 + bool(all_pattern % 2)
X = sorted(A)

left = 0
right = n

while left + 1 < right:
    idx = (left+right) // 2
    x = X[idx]
    up_or_down = [1 if num >= x else -1 for num in A]
    cumsum = [n]
    total = n
    for point in up_or_down:
        total += point
        cumsum.append(total)

    tree = Bit(2*n+1)
    pattern = 0
    for p in cumsum:
        pattern += tree.sum(p)
        tree.add(p, 1)

    if pattern >= check:
        left = idx
    else:
        right = idx

print(X[left])


### FIXED CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n = int(input())
A = list(map(int, input().split()))
all_pattern = n * (n+1) // 2
check = all_pattern // 2 + bool(all_pattern % 2)
X = sorted(A)

left = 0
right = n

while left + 1 < right:
    idx = (left+right) // 2
    x = X[idx]
    up_or_down = [1 if num >= x else -1 for num in A]
    cumsum = [n]
    total = n
    for point in up_or_down:
        total += point
        cumsum.append(total)

    tree = Bit(2*n+1)
    pattern = 0
    for p in cumsum:
        pattern += tree.sum(p)
        tree.add(p, 1)

    if pattern >= check:
        left = idx
    else:
        right = idx

print(X[left])
### BUGGY CODE ###

S = list(input())

DIVIDER = 13

mod_digit = [i % DIVIDER for i in range(10)]
mod_level = []
tmp = 1
for _ in range(len(S)):
    mod_level.append(tmp % DIVIDER)
    tmp *= 10
mod_level = mod_level[::-1]

memo = [[0] * DIVIDER for _ in range(len(S) + 1)]
# def dp(pos, mod_tmp):
for idx in range(len(S) + 1):
    # if pos < 0:
    #     if mod_tmp == 5:
    #         return 1
    #     else:
    #         return 0
    # elif memo[pos][mod_tmp] != None: return memo[pos][mod_tmp]
    if idx == 0:
        for mod_tmp in range(DIVIDER):
            if mod_tmp == 5:
                memo[0][mod_tmp] = 1
            else:
                memo[0][mod_tmp] = 0
    else:
        pos = idx - 1
        for mod_tmp in range(DIVIDER):
            ret = 0
            if S[pos] == '?':
                for d in range(10):
                    mod_nxt = (mod_tmp + mod_digit[d] * mod_level[pos]) % DIVIDER
                    ret += memo[idx - 1][mod_nxt]
            else:
                d = int(S[pos])
                mod_nxt = (mod_tmp + mod_digit[d] * mod_level[pos]) % DIVIDER
                ret += memo[idx - 1][mod_nxt]
            #
            memo[idx][mod_tmp] = ret % 1000000007

print(memo[len(S)][0])

### FIXED CODE ###

inf = 10 ** 18
P = 10 ** 9 + 7

S = input()
N = len(S)

tmp = 1
modrow = [1] * 6
for i in range(5):
    tmp = (tmp * 10) % 13
    modrow[1 + i] = tmp

modtab = [[None] * 10 for i in range(6)]
for i in range(6):
    for j in range(10):
        modtab[i][j] = (modrow[i] * j) % 13

# for modcol in modtab:
#     print("#", sorted(modcol))

# X + question === 5 (mod 13)
X = 0
q_idx = []
for i, Si in enumerate(S[::-1]):
    if Si == '?':
        q_idx.append(i)
    else:
        X = (X + modtab[i % 6][int(Si)]) % 13


M = len(q_idx)
ans_tab = [[0] * 13 for _ in range(M + 1)]

ans_tab[0][0] = 1
for i, idx in enumerate(q_idx):
    for src in range(13):
        for coeff in range(10):
            dst = (src + modtab[idx % 6][coeff]) % 13
            ans_tab[1 + i][dst] = (ans_tab[1 + i][dst] + ans_tab[i][src]) % P
        
# print("#", ans_tab[-1])
idx_ans = (5 - X) % 13
print(ans_tab[-1][idx_ans])
### BUGGY CODE ###

n,m,q = map(int,input().split())
a = [0] * q
b = [0] * q
c = [0] * q
d = [0] * q
for i in range(q):
    a[i], b[i], c[i], d[i]= map(int, input().split())

s = [1] * n
#st[b[i]] - st[a[i]]  = c[i]
num = n-1
ans1 = [0] * 100000000
ans = 0
t = 0

while(s[0] != m):

    for i in range(q):
        if s[b[i]-1] - s[a[i]-1]  == c[i]:
            ans += d[i]
    #print(s)
    #print(ans)

    ans1[t] = ans
    t += 1

    ans = 0

    if s[num] < m:
        s[num] += 1
    elif num > 0 :
        num -= 1
        temp = s[num]+1
        if temp < m:
            for i in range(num,n):
                s[i] = temp
        else:
            while(s[num] == m):
                num -= 1
            temp = s[num]+1
            for i in range(num,n):
                s[i] = temp

        num = n-1






print(max(ans1))


### FIXED CODE ###

n,m,q = map(int,input().split())
a = [0] * q
b = [0] * q
c = [0] * q
d = [0] * q
for i in range(q):
    a[i], b[i], c[i], d[i]= map(int, input().split())

s = [1] * n
#st[b[i]] - st[a[i]]  = c[i]
num = n-1
#ans1 = [0] * 10000000
ans = 0
pre_ans = 0
t = 0

while(s[0] != m ):

    for i in range(q):
        if s[b[i]-1] - s[a[i]-1]  == c[i]:
            ans += d[i]
    #print(s)
    #print(ans)
    ans = max(pre_ans,ans)
    pre_ans = ans
    #t += 1

    ans = 0

    if s[num] < m:
        s[num] += 1
    elif num > 0 :
        num -= 1
        temp = s[num]+1
        if temp < m:
            for i in range(num,n):
                s[i] = temp
        else:
            while(s[num] == m):
                num -= 1
            temp = s[num]+1
            for i in range(num,n):
                s[i] = temp

        num = n-1

for i in range(q):
    if s[b[i]-1] - s[a[i]-1]  == c[i]:
        ans += d[i]

ans = max(pre_ans,ans)

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

from bisect import bisect_left

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

change=[tuple(map(int,input().split())) for _ in range(M)]
change=sorted(change,key=lambda x: x[1])

for i in range(M):
  b,c=change[i]
  idx = bisect_left(A,c)
  
  if idx-b>=0:
    A = A[b:idx]+[c]*b+A[idx:]
  else:
    A = [c]*idx+A[idx:]

print(sum(A))

### FIXED CODE ###

from bisect import bisect_left

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

change=[tuple(map(int,input().split())) for _ in range(M)]
change=sorted(change,key=lambda x: x[1],reverse=True)
change2=[]
count=0
for i in range(M):
  b,c=change[i]
  change2.extend([c]*b)
  count += b
  if count >= N:break

A.extend(change2)
A = sorted(A)
print(sum(A[len(A)-N:]))
### BUGGY CODE ###

import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
count = 0
for i in range(N-1):
    while A[i] > A[i+1]:
        A[i + 1] = A[i + 1] + 1
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
count = 0
for i in range(1,N):
    if A[i-1] > A[i]:
        count += A[i-1] - A[i]
        A[i] = A[i - 1]
print(count)
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
cnt = 0
for n in range(N):
    if n == 0:
        cnt += 1
    else:
        L = P[:n]
        L.sort()
        if P[n] <= L[0]:
            cnt += 1
print(cnt)


### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
cnt = 0
res = float('Inf')
for n in range(N):
    if P[n] < res:
        res = P[n]
        cnt += 1
print(cnt)
### BUGGY CODE ###

import fractions
import math
#gcd = math.gcd
gcd = fractions.gcd
n, m = [int(_) for _ in input().split()]
a = sorted([int(_) // 2 for _ in input().split()])
lcm = a[0]
for i in range(1, n):
    lcm = lcm * a[i] // gcd(lcm, a[i])
for b in a:
    if (lcm // b) % 2 == 0:
        print(0)
        exit()
ans = m // lcm
if ans % 2 == 0:
    ans -= 1
print(ans // 2 + 1)


### FIXED CODE ###

import fractions
import math
#gcd = math.gcd
gcd = fractions.gcd
n, m = [int(_) for _ in input().split()]
a = sorted([int(_) // 2 for _ in input().split()])
lcm = a[0]
for i in range(1, n):
    lcm = lcm * a[i] // gcd(lcm, a[i])
    if lcm > 10**10:
        print(0)
        exit()
for b in a:
    if (lcm // b) % 2 == 0:
        print(0)
        exit()
ans = m // lcm
if ans % 2 == 0:
    ans -= 1
if ans < 0:
    print(0)
    exit()
print(ans // 2 + 1)
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
s=0
for num in range(N):
  count = 0
  for i in range(s, N-1):
    if A[i] == num+1:
      count += 1
    else:
      continue
  s+=count
  print(count)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
s=0
for num in range(1, N+1):
  count = 0
  for i in range(s, N-1):
    if A[i] == num:
      count += 1
    else:
      break
  s+=count
  print(count)
### BUGGY CODE ###

N = int(input())
Alist = list(map(int,input().split()))
Blist = list(map(int,input().split()))
Clist = list(map(int,input().split()))
Alist.sort()
Clist.sort()
Clist.reverse()
retnum = 0 
for i in Blist:
    Anum = 0 
    Cnum = 0 
    for i2 in Alist:
        if i2 >= i:
            break
        Anum +=1 
    for i2 in Clist:
        if i2 <= i:
            break
        Cnum +=1 
    retnum +=(Anum * Cnum)
print(retnum)


### FIXED CODE ###

import bisect
N = int(input())
Alist = list(map(int,input().split()))
Blist = list(map(int,input().split()))
Clist = list(map(int,input().split()))
Alist.sort()
Clist.sort()
retnum = 0 
for i in Blist:
    Anum = bisect.bisect_left(Alist,i)
    Cnum =  N - bisect.bisect_right(Clist,i)
    retnum +=(Anum * Cnum)
print(retnum)
### BUGGY CODE ###

R, C, K = map(int, input().split())
D = dict()
for _ in range(K):
    r, c, v = map(int, input().split())
    D[(r, c)] = v

dp = [[[0] * 4 for _ in range(C + 1)] for _ in range(R + 1)]
for r in range(1, R + 1):
    for c in range(1, C + 1):
        m=max(dp[r-1][c])
        for n in range(4):
            dp[r][c][n] = max(m,
                              dp[r][c - 1][n])
        if (r, c) in D:
            for n in range(3):
                dp[r][c][n + 1] = max(dp[r][c][n + 1],
                                      m + D[(r, c)],
                                      dp[r][c - 1][n] + D[(r, c)])
print(max(dp[-1][-1]))


### FIXED CODE ###

import sys

input = sys.stdin.readline

R, C, K = map(int, input().split())
D = dict()
for _ in range(K):
    r, c, v = map(int, input().split())
    D[(r, c)] = v

dp0 = [[0] * (C + 1) for _ in range(R + 1)]
dp1 = [[0] * (C + 1) for _ in range(R + 1)]
dp2 = [[0] * (C + 1) for _ in range(R + 1)]
dp3 = [[0] * (C + 1) for _ in range(R + 1)]

for r in range(1, R + 1):
    for c in range(1, C + 1):
        m = max(dp0[r - 1][c], dp1[r - 1][c], dp2[r - 1][c], dp3[r - 1][c])
        dp0[r][c] = max(m, dp0[r][c - 1])
        dp1[r][c] = max(m, dp1[r][c - 1])
        dp2[r][c] = max(m, dp2[r][c - 1])
        dp3[r][c] = max(m, dp3[r][c - 1])
        if (r, c) in D:
            dp1[r][c] = max(dp1[r][c], m + D[(r, c)], dp0[r][c - 1] + D[(r, c)])
            dp2[r][c] = max(dp2[r][c], m + D[(r, c)], dp1[r][c - 1] + D[(r, c)])
            dp3[r][c] = max(dp3[r][c], m + D[(r, c)], dp2[r][c - 1] + D[(r, c)])
print(max(dp0[-1][-1], dp1[-1][-1], dp2[-1][-1], dp3[-1][-1]))
### BUGGY CODE ###

n=int(input())
A=[]
for i in range(n):
    a=int(input())
    if a in A:
        del A[A.index(a)]
    else:
        A.append(a)
print(len(A))

### FIXED CODE ###

n=int(input())
A=[int(input()) for _ in range(n)]
B={}
for i in A:
    if i in B:
        B[i]=(1+B[i])%2
    else:
        B[i]=1
print(sum(B.values()))
### BUGGY CODE ###

import numpy as np
N,X,Y=map(int,input().split())
b=[0]*(N)
for i in range(N):
  for j in range(i+1,N):
    b[min(j-i,np.abs(X-1-i)+1+np.abs(Y-1-j))]+=1
for i in range(1,N):
  print(b[i])

### FIXED CODE ###


N,X,Y=map(int,input().split())
b=[0]*(N)
for i in range(N):
  for j in range(i+1,N):
    p=max(X-1-i,1+i-X)
    q=max(Y-1-j,1+j-Y)
    b[min(j-i,p+1+q)]+=1
for i in range(1,N):
  print(b[i])
### BUGGY CODE ###

while True:
    n = input()
    if n == "0000":
        break

    if n.count(n[0]) == 4:
        print("NA")
        continue

    cnt = 0
    while n != "6174":
        L, S = list(n), list(n)
        L.sort(reverse=True)
        S.sort()
        n = str(int("".join(L)) - int("".join(S)))
        cnt += 1

    print(cnt)

### FIXED CODE ###

while True:
    n = input()
    if n == "0000":
        break

    if n.count(n[0]) == 4:
        print("NA")
        continue

    cnt = 0
    while n != "6174":
        L, S = list(n), list(n)
        L.sort(reverse=True)
        S.sort()
        n = str(int("".join(L)) - int("".join(S))).zfill(4)
        cnt += 1

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

import numpy as np
import collections

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

# N = 5
# A = [1, 1, 2, 1, 2]

for i in range(N):
    # i = 2
    A_sub = A.copy()
    A_sub.pop(i)

    A_sub = np.array(A_sub)

    ans = 0
    # u, counts = np.unique(A_sub, return_counts=True)
    c = collections.Counter(A_sub)
    for j in c:
        # val = uni_vals[0]
        n = c[j]
        ans += (n*(n-1))/2
    # dic = {}
    # for val in A_sub:
    #     if val in dic.keys():
    #         dic[val] += 1
    #     else:
    #         dic[val] = 1
    # ans = 0
    # for val in dic.values():
    #     ans += (val*(val-1)/2)

    print(int(ans))


### FIXED CODE ###

from collections import defaultdict, Counter

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

d = defaultdict(int)
for a in A:
    d[a] += 1

all = 0
for val in d.values():
    all += val * (val - 1) / 2

all = int(all)
val_cnt = Counter(A)
for a in A:
    print(all - (val_cnt[a] - 1))
### BUGGY CODE ###

n=int(input())
d=[]
for i in range(n):
  d.append(int(input()))
x=sorted(d)
for j in range(n):
  if d[j]==max(d):
    print(x[n-2])
  else:
    print(max(d))

### FIXED CODE ###

n=int(input())
d=[]
for i in range(n):
  d.append(int(input()))
x=sorted(d)
for j in range(n):
  if d[j]==x[-1]:
    print(x[-2])
  else:
    print(x[-1])
### BUGGY CODE ###

from itertools import product

N, W = map(int, input().split())
wv = [[0, 0]] + [[int(_) for _ in input().split()] for _ in range(N)]
dp = [[0]*(2*W) for _ in range(2*N)]

for i, tot in product(range(1, N+1), range(1, W+1)):
    if tot >= wv[i][0]:
        dp[i][tot] = max(dp[i-1][tot], dp[i-1][tot-wv[i][0]]+wv[i][1])
    else:
        dp[i][tot] = dp[i-1][tot]

print(dp[N][W])

### FIXED CODE ###

import numpy as np


N, W = map(int, input().split())
w_v = [[int(_) for _ in input().split()] for _ in range(N)]
dp = np.zeros([N, W+1], dtype=int)
dp[0][w_v[0][0]:] = w_v[0][1]

for i in range(1, N):
    key = w_v[i][0]
    dp[i][:key] = dp[i-1][:key]
    dp[i][key:] = np.maximum(dp[i-1][key:], dp[i-1][:-key] + w_v[i][1])

print(dp[-1][-1])
### BUGGY CODE ###

from collections import defaultdict as dd
N = int(input())
S = []
for i in range(N):
    s = input()
    s = sorted(s)
    s = ''.join(s)
    S.append(s)

SS = set(S)
SN = []
for ss in SS:
    SN.append(S.count(ss))

res = 0
for sn in SN:
    res += sn * (sn - 1) // 2

print(res)

### FIXED CODE ###

def main():
    N = int(input())
    S = []
    for i in range(N):
        s = input()
        s = sorted(s)
        s = ''.join(s)
        S.append(s)
    S.sort()
    SS = sorted(list(set(S)))
    SN = []
    M = len(SS)
    l = 0
    r = len(S)
    for i in range(M):
        for j in range(l, r):
            if S[j] != SS[i]:
                r = j
                break
        SN.append(r - l)
        l = r
        r = len(S)        

    res = 0
    for sn in SN:
        res += sn * (sn - 1) // 2

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

n, k = map(int, input().split())
ans = 0
mod = 10 ** 9 + 7

for i in range((n+1)-(k-1)):
    mini = sum(range(0, i+k))
    maxi = sum(range(n, n-k-i, -1))
    ans += maxi - mini +1
print(ans%mod)

### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
ans = 0
mod = 10 ** 9 + 7
arr = np.arange(n+1)
a = np.cumsum(arr)
b = np.cumsum(arr[::-1])

for i in range(k, n+1+1):
    ans += b[i-1] - a[i-1] + 1
print(ans%mod)
### BUGGY CODE ###

# APC001C - Vacant Seat
def main():
    # if no vacant seat in [0, i)
    # -> seat[0] == seat[i] if i % 2 else seat[0] != seat[i]
    N = int(input())
    print(0, flush=1)
    seat_zero = input().rstrip()
    if seat_zero == "Vacant":
        return
    left, right = 0, N
    for _ in range(19):
        mid = (left + right) // 2
        print(mid, flush=1)
        this_seat = input().rstrip()
        if this_seat = "Vacant":
            return
        if mid % 2 == (seat_zero != this_seat):
            left = mid
        else:
            right = mid


if __name__ == "__main__":
    main()

### FIXED CODE ###

# APC001C - Vacant Seat
def main():
    # if no vacant seat in [0, i)
    # -> seat[0] == seat[i] if i % 2 else seat[0] != seat[i]
    N = int(input())
    print(0, flush=1)
    seat_zero = input().rstrip()
    if seat_zero == "Vacant":
        return
    left, right = 0, N
    for _ in range(19):
        mid = (left + right) // 2
        print(mid, flush=1)
        this_seat = input().rstrip()
        if this_seat == "Vacant":
            return
        if mid % 2 == (seat_zero != this_seat):
            left = mid
        else:
            right = mid


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

def search(a):
    x=0
    a="".join(["0"*(3-len(a)),a])
    for i in range(n):
        if a[x]==s[i]:
            x+=1
            if x==3:
                return True
    return False
n=int(input())
s=input()
ans=0
k=[False]*1000
for i in range(1000):
    k[i]=search(str(i))
for i in k:
    if i:
        ans+=1
print(ans)

### FIXED CODE ###

def search(a):
    x=0
    a="".join(["0"*(3-len(a)),a])
    for i in range(n):
        if a[x]==s[i]:
            x+=1
            if x==3:
                return True
    return False
n=int(input())
s=input()
ans=0
k=[False]*1000
for i in range(1000):
    k[i]=search(str(i))
for i in k:
    if i:
        ans+=1
print(ans)
### BUGGY CODE ###

n=int(input())
s=0
for i in range(1,n+1):
    t=0
    for j in range(1,int((i+1)**(1/2))+1):
        if i%j==0:
            t+=1
    t=t*2
    if i==(int((i+1)**(1/2)))**2:
        t+=-1
    s+=i*t
print(s)

### FIXED CODE ###

n=int(input())
s=0
a=[1]
for i in range(n-1):
    a.append(a[i]+(i+2))
for i in range(1,n+1):
    s+=i*a[(n//i)-1]
print(s)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

b = []
for i in range(n):
    if i % 2 == 0: b.append(a[i])
    else: b.insert(0, a[i])
if (n - 1) % 2 == 0: b = list(reversed(b))

for elem in b: print(elem, end=' ')

### FIXED CODE ###

import sys
input = sys.stdin.readline


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

b = [None] * n
for i in range(n):
    if i % 2 == 0: b[n // 2 + i // 2] = a[i]
    else: b[n // 2 - (-(-i // 2))] = a[i]
if (n - 1) % 2 == 0: b = list(reversed(b))

for elem in b: print(elem, end=' ')
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
for i in range(1, n):
    print(a.count(i))
print(0)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0] * n
for i in range(n - 1):
    b[a[i] - 1] += 1
for i in range(n):
    print(b[i])
### BUGGY CODE ###

k = int(input())

class GCD:
    def __init__(self):
        self.cache = {}
    def gcd2(self, a, b):
        if (a in self.cache and b in self.cache[a]):
            return self.cache[a][b]
        if (a % b == 0):
            if (a not in self.cache):
                self.cache[a] = {}
            self.cache[a][b] = b
            return b
        return self.gcd2(b, a % b)
    def gcd3(self, a, b, c):
        return self.gcd2(self.gcd2(a, b), c)

a = 1
b = 1
c = 1
result = 0
client = GCD()
while (a <= k):
    b = 1
    while (b <= k):
        c = 1
        while (c <= k):
            result += client.gcd3(a, b, c)
            c += 1
        b += 1
    a += 1
print(result)


### FIXED CODE ###

k = int(input())
#k = 200

class GCD:
    def __init__(self):
        self.cache = {}
        self.cache3 = {}
    def gcd2(self, a, b):
        a, b = sorted([a, b], reverse=True)
        if (a in self.cache and b in self.cache[a]):
            return self.cache[a][b]
        if (a % b == 0):
            if (a not in self.cache):
                self.cache[a] = {}
            self.cache[a][b] = b
            return b
        return self.gcd2(b, a % b)
    def gcd3(self, a, b, c):
        a, b, c = sorted([a, b, c], reverse=True)
        if (a in self.cache3 and b in self.cache3[a] and c in self.cache3[a][b]):
            return self.cache3[a][b][c]
        if (a not in self.cache3):
            self.cache3[a] = {}
        if (b not in self.cache3[a]):
            self.cache3[a][b] = {}
        result = self.gcd2(self.gcd2(a, c), b)
        self.cache3[a][b][c] = result
        return result

a = 1
b = 1
c = 1
result = 0
client = GCD()
while (a <= k):
    b = a
    while (b <= k):
        interval = client.gcd2(a, b)
        c = b
        while (c <= k):
            if (a == b and b == c):
                result += client.gcd2(interval, c)
            elif(a != b and b != c and a != c):
                result += client.gcd2(interval, c) * 6
            else:
                result += client.gcd2(interval, c) * 3
            c += 1
        b += 1
    a += 1
print(result)
### BUGGY CODE ###

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

# def print_map(mp):
#     for r in mp:
#         print(['{:2d}'.format(n) for n in r])

H, W = map(int, input().split())
mp = [[] for h in range(H)]
mp_row = [[0 for w in range(W)] for h in range(H)]
mp_col = [[0 for w in range(W)] for h in range(H)]

# True = なし、 False = 障害物
for h in range(H):
    mp[h] = [True if c == "." else False for c in input()]

# 全探索はO(HWHW)となって爆発。
# 縦横でまずカウントするのがよさげ。
# このプログラムはO(HW)だがTLE

## 横のパネル数
for h in range(H):
    st = 0
    cnt = 0
    for w in range(W):
        if mp[h][w] is False:
            for i in range(st, w):
                mp_row[h][i] = cnt
            cnt = 0
            st = w+1
        elif w == W-1:
            cnt += 1
            for i in range(st, W):
                mp_row[h][i] = cnt
        else:
            cnt += 1

## 縦のパネル数
for w in range(W):
    st = 0
    cnt = 0
    for h in range(H):
        if mp[h][w] is False:
            for i in range(st, h):
                mp_col[i][w] = cnt
            cnt = 0
            st = h+1
        elif h == H-1:
            cnt += 1
            for i in range(st, H):
                mp_col[i][w] = cnt
        else:
            cnt += 1

#print_map(mp_row)
#print()
#print_map(mp_col)

mx = 0
for h in range(H):
    for w in range(W):
        # 重なっている中央を引くのを忘れずに
        mx = max(mx, mp_row[h][w]+mp_col[h][w]-1)
print(mx)


### FIXED CODE ###

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

# def print_map(mp):
#     for r in mp:
#         print(['{:2d}'.format(n) for n in r])

H, W = map(int, input().split())
mp = [[] for h in range(H)]
mp_row = [[0 for w in range(W)] for h in range(H)]
mp_col = [[0 for w in range(W)] for h in range(H)]

# True = なし、 False = 障害物
for h in range(H):
    mp[h] = [True if c == "." else False for c in input()]

# 全探索はO(HWHW)となって爆発。
# 縦横でまずカウントするのがよさげ。
# このプログラムはO(HW)だがTLE: カウントしたものの書き込みでO(HHW+HWW)あたりになっている？
# これpythonのforの遅さでTLEしてないか…？

## 横のパネル数
for h in range(H):
    st = 0
    cnt = 0
    for w in range(W):
        if mp[h][w] is False:
            for i in range(st, w):
                mp_row[h][i] = cnt
            cnt = 0
            st = w+1
        elif w == W-1:
            cnt += 1
            for i in range(st, W):
                mp_row[h][i] = cnt
        else:
            cnt += 1

## 縦のパネル数
for w in range(W):
    st = 0
    cnt = 0
    for h in range(H):
        if mp[h][w] is False:
            for i in range(st, h):
                mp_col[i][w] = cnt
            cnt = 0
            st = h+1
        elif h == H-1:
            cnt += 1
            for i in range(st, H):
                mp_col[i][w] = cnt
        else:
            cnt += 1

#print_map(mp_row)
#print()
#print_map(mp_col)

mx = 0
for h in range(H):
    for w in range(W):
        # 重なっている中央を引くのを忘れずに
        mx = max(mx, mp_row[h][w]+mp_col[h][w]-1)
print(mx)