Harryxun/stf_run huggingface dataset:
N, A, B, C = [int(i) for i in input().split()]

ans = list()
l = list()

for n in range(N):
    l.append(input())

def dfs(i, a, b, c):
    if i == N:
        return True

    ss = l[i]
    if ss == 'AB':
        if a == 0 and b == 0:
            return False
        if b > 0 and dfs(i + 1, a + 1, b - 1, c):
            ans.append('A')
            return True
        if a > 0 and dfs(i + 1, a - 1, b + 1, c):
            ans.append('B')
            return True
        else:
            return False
    elif ss == 'AC':
        if a == 0 and c == 0:
            return False
        if c > 0 and dfs(i + 1, a + 1, b, c - 1):
            ans.append('A')
            return True
        if a > 0 and dfs(i + 1, a - 1, b, c + 1):
            ans.append('C')
            return True
        else:
            return False
    elif ss == 'BC':
        if b == 0 and c == 0:
            return False
        if c > 0 and dfs(i + 1, a, b + 1, c - 1):
            ans.append('B')
            return True
        if b > 0 and dfs(i + 1, a, b - 1, c + 1):
            ans.append('C')
            return True
        else:
            return False

dfs(0, A, B, C)

if len(ans) > 0:
    print('Yes')
    for x in reversed(ans):
        print(x)
else:
    print('No')

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)

N, A, B, C = [int(i) for i in input().split()]

ans = list()
l = list()

for n in range(N):
    l.append(input())

def dfs(i, a, b, c):
    if i == N:
        return True

    ss = l[i]
    if ss == 'AB':
        if a == 0 and b == 0:
            return False
        if b > 0 and dfs(i + 1, a + 1, b - 1, c):
            ans.append('A')
            return True
        if a > 0 and dfs(i + 1, a - 1, b + 1, c):
            ans.append('B')
            return True
    if ss == 'AC':
        if a == 0 and c == 0:
            return False
        if c > 0 and dfs(i + 1, a + 1, b, c - 1):
            ans.append('A')
            return True
        if a > 0 and dfs(i + 1, a - 1, b, c + 1):
            ans.append('C')
            return True
    if ss == 'BC':
        if b == 0 and c == 0:
            return False
        if c > 0 and dfs(i + 1, a, b + 1, c - 1):
            ans.append('B')
            return True
        if b > 0 and dfs(i + 1, a, b - 1, c + 1):
            ans.append('C')
            return True
    return False

dfs(0, A, B, C)

if len(ans) > 0:
    print('Yes')
    for x in reversed(ans):
        print(x)
else:
    print('No')
s=[int(i) for i in input.split()]
if len(s)==3 and s.count("5")==2 and s.count("7")==1:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

s=[int(i) for i in input().split()]
#print(s,len(s))
if len(s)==3 and s.count(5)==2 and s.count(7)==1:
    print("YES")
else:
    print("NO")
#!/usr/bin/env python3
# Knapsack問題

import numpy as np

# input
N,W = map(int, input().split())
w = np.zeros(N, dtype=int)
v = np.zeros(N, dtype=int)
for i in range(N):
  a,b = map(int ,input().split())
  w[i] = a 
  v[i] = b 

# calc
dp = [[0 for _ in range(W+1)] for _ in range(N+2)]
dp = np.array(dp, dtype=int)
for i in np.arange(N):
   for j in np.arange(W+1):
        if w[i] <= j:
            dp[i+1,j] = max(dp[i, j-w[i]]+v[i], dp[i,j])
        else:
            dp[i+1,j] = dp[i,j]

print(dp[N,W])


### FIXED CODE ###

# Knapsack問題

# input
N,W = map(int, input().split())
w = []
v = []
for _ in range(N):
    a,b = map(int ,input().split())
    w.append(a)
    v.append(b)

# calc
dp = [[0 for _ in range(W+1)] for _ in range(N+2)]

for i in range(N):
    for j in range(W+1):
        if w[i] <= j:
            dp[i+1][j] = max(dp[i][j-w[i]]+v[i], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[N][W])
import sys
input=sys.stdin.readline
n = int(input())
s = input()
quenum = int(input())
q = []
for i in range(quenum):
    q.append(input().split())

N0 = 2**(n-1).bit_length()
INF = 2**31-1
data = [set()]*(2*N0)
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = data[2*k+1]  | data[2*k+2]
def query(l, r):
    L = l + N0; R = r + N0
    s = set()
    while L < R:
        if R & 1:
            R -= 1
            s = s | data[R-1]

        if L & 1:
            s = s |  data[L-1]
            L += 1
        L >>= 1; R >>= 1
    return s

for i in range(len(s)):
    update(i,set([s[i]]))

for que in q:
    if que[0] == "1":
        update(int(que[1])-1,set([que[2]]))
    else:
        print(len(query(int(que[1])-1,int(que[2]))))

### FIXED CODE ###

n=int(input())
s=input()
q=int(input())

query=[]
for i in range(q):
    query.append(input())

ide_ele = set()

def segfunc(x, y):
    return x | y

class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        # param k: index(0-index)
        # param x: update value
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1
    def query(self, l, r):
        #[l, r)segfunc, 0-index
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

al = [{s[i]} for i in range(n)]
seg = SegTree(al, segfunc, ide_ele)

for q in query:
    que,a,b=q.split()

    if que == "1":
        seg.update(int(a)-1,set(b))
    else:
        ret=seg.query(int(a)-1,int(b))
        print(len(ret))
if __name__ == "__main__":
    N, K = input().split(" ")
    D = input().split()
    num = set([str(i) for i in range(10)])
    diff = num ^ set(D)

    temp = N
    while True:
        setN = set(list(N))
        if setN - diff:
            temp += 1
        else:
            break
    print(temp)


### FIXED CODE ###


def main():
    N, K = input().split(" ")

    D = list(input().split(" "))
    use_num = list(set([str(i) for i in range(10)]) - set(D))

    N = int(N)
    i = N
    while True:

        if not set(str(i)) <= set(use_num) and i >= N:
            i += 1
        else:
            print(i)
            break

if __name__ == "__main__":
    main()
W = input()
W_list = set(list(s for s in W))
ans = True 
for s in W_list:
    if W.count(s) % 2 != 0
        False
        break

if ans:
    print("Yes")
else 
    print("No")

### FIXED CODE ###

W = input()
W_list = set(list(s for s in W))
ans = True 
for s in W_list:
    if W.count(s) % 2 != 0:
        ans = False
        break


if ans:
    print("Yes")
else:
    print("No")
N, M = map(int, input().split())
def dfs(p):
    if memo[p] != -1:
        return memo[p]
    m = 0
    for d in dic[p]:
        m = max(m, dfs(d)+1)
    memo[p] = m
    return m
dic = [[] for i in range(N)]
for m in range(M):
    x, y = map(int, input().split())
    dic[x-1].append(y-1)
    
inf = -1
memo = [inf]*N
ans = 0
for i in range(N):
    k= dfs(i)
    memo[i] = k
    ans = max(ans,k)
print(ans)

### FIXED CODE ###

import sys
 
sys.setrecursionlimit(100000)
 
N, M = map(int, input().split(" "))
G = [[] for _ in range(N)]
 
for _ in range(M):
    x, y = map(int, input().split(" "))
    G[x-1].append(y-1)
dp = [-1] * N
def pathlen(G, dp, v):
    if dp[v] != -1:
        return dp[v]
 
    plen = 0
    for i in G[v]:
        plen = max(plen, pathlen(G, dp, i)+1)
    dp[v] = plen
    return plen
ans = 0
for i in range(N):
    ans = max(ans, pathlen(G, dp, i))
print(ans)
#import numpy as np
import sympy as sp
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

num = defaultdict(int)
ans = defaultdict(int)
for i, a in enu(A):
    if num[a] > 0:
        num[a] += 1
        continue

    divs = sp.divisors(a)
    # print('divs', divs)
    for div in divs:
        if num[div] > 0:
            break
    else:
        ans[a] += 1
    num[a] += 1

cnt = 0 
# print(num)
# print(ans)
for an in ans.items():
    k, v = an
    if num[k]==1:
        cnt += 1
print(cnt)



### FIXED CODE ###

#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

N = int(input())
A = list(map(int, input().split()))
A.sort()
C = Counter(A)
S = set(A)

maxA = A[-1]
chk = [0] * (maxA+1)
for s in S:
    for i in range(s, maxA+1, s):
        chk[i] += 1

res = [s for s in S if chk[s] == 1 and C[s] == 1]
# print(res)
print(len(res))
if __name__ == '__main__':

	n = int(input())
	m = int(n//2)

   	end = n - 1
	for x in range(2,int(n**0.5)+1):
		if n % x == 0:
			y = n // x
			end = min(x+y-2,end)

	print(end)


### FIXED CODE ###

if __name__ == '__main__':

	n = int(input())
	m = int(n//2)

	end = n - 1
	for x in range(2,int(n**0.5)+1):
		if n % x == 0:
			y = n // x
			end = min(x+y-2,end)

	print(end)
import numpy as np
from collections import Counter
import collections
import numpy as np 
from scipy import sqrt, power, exp, log10
from scipy.fftpack import fft, ifft, fftfreq
import tarfile
import re
import os
import glob
from datetime import datetime
import time
import numpy.linalg as LA

round = lambda x:(x*2+1)//2
a,b = list(map(int,input().split()))
S = input()
sub= "AC"
for i in range(b):
    r,l = list(map(int,input().split()))
    print(S1)
    n = S1.count(sub)
    print(n)

### FIXED CODE ###

import numpy as np
from collections import Counter
import collections
import numpy as np 
from scipy import sqrt, power, exp, log10
from scipy.fftpack import fft, ifft, fftfreq
import tarfile
import re
import os
import glob
from datetime import datetime
import time
import numpy.linalg as LA

round = lambda x:(x*2+1)//2
a,b = list(map(int,input().split()))
S = input()
sub= "AC"
l = np.zeros(len(S)+1)
for i in range(len(S)):
  l[i+1] = l[i] + (1 if S[i:i+2]=="AC" else 0)

for i in range(b):
    r,t = list(map(int,input().split()))
    n = l[t-1]-l[r-1]
    print(int(n))
def matrixChainMultiplication(p):
    # p = [p_0, p_1, ..., p_n]
    n = len(p) - 1
    # n+1 x n+1 zero matrix?????????(0,...,n)
    # cost(i,j): (M_i...M_j)???????°??????????
    cost = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for numOfMatrices in range(2, n + 1):
        for i in range(1, n - numOfMatrices + 2):
            j = i + numOfMatrices - 1
            cost[i][j] = 99000000
            for k in range(i, j):
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k + 1][j] + p[i - 1] * p[k] * p[j])
    print(m[1][n])

p = []
n = int(input())

for _ in range(n):
    listed_input = input().split()
    p.append(int(listed_input.[0]))
p.append(int(listed_input[1]))

matrixChainMultiplication(p)

### FIXED CODE ###

def matrixChainMultiplication(p):
    # p = [p_0, p_1, ..., p_n]
    n = len(p) - 1
    # n+1 x n+1 zero matrix?????????(0,...,n)
    # cost(i,j): (M_i...M_j)???????°??????????
    cost = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for numOfMatrices in range(2, n + 1):
        for i in range(1, n - numOfMatrices + 2):
            j = i + numOfMatrices - 1
            cost[i][j] = float('inf')
            for k in range(i, j):
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k + 1][j] + p[i - 1] * p[k] * p[j])
    print(cost[1][n])

p = []
n = int(input())

for _ in range(n):
    listed_input = input().split()
    p.append(int(listed_input[0]))
p.append(int(listed_input[1]))

matrixChainMultiplication(p)
N = int(input())
s_list = []
count = 0
n, m, l = 0, 0, 0

for i in range(N):
  s = input()
  s_list.append(s)
  count += s.count('AB')
  if s[0] == 'B' and s[-1] == 'A':
    n += 1
    continue
  elif s[-1] == 'A':
    m += 1
  elif s[0] == 'B':
    l += 1

if n < m and n < l:
  print(int(count + 2 * n + min(m - n, l - n)))
elif n > m and n > l:
  print(int(count + 2 * (n - max(m, l) + m + l)
else:
  print(int(count + min(n, m) + min(n, l)))

### FIXED CODE ###

N = int(input())
s_list = []
count = 0
n, m, l = 0, 0, 0
 
for i in range(N):
  s = input()
  s_list.append(s)
  count += s.count('AB')
  if s[0] == 'B' and s[-1] == 'A':
    n += 1
    continue
  elif s[-1] == 'A':
    m += 1
  elif s[0] == 'B':
    l += 1

if m == 0 and l == 0:
  if n == 0:
    print(int(count))
  else:
    print(int(count + (n - 1)))
else:
  print(int(count + min(n+m, n+l)))
import math

c  = raw_input();

for var in range(0, int(c)) :
	n1 = raw_input();
	n2 = raw_input();
	sum = int(n1) + int(n2);

	if int(math.log10(sum)) + 1 > 80 :
		print("overflow");
	else :
		print(sum);

### FIXED CODE ###

for _ in range(int(input())) :
    n = int(input()) + int(input())
    if (n >= 10 ** 80) :
        print("overflow")
    else :
        print(n)
import collections
a,b = map(int,input().split(" "))
ar = list(map(int,input().split(" ")))
br = set(ar)
cr = collections.Counter(ar)
n = len(br) - b
dr = []
for k in cr.keys():
    cr.append(k)
cr.sort()
count = 0
for i in range(n):
    count += cr[i]

### FIXED CODE ###

import collections
a,b = map(int,input().split(" "))
ar = list(map(int,input().split(" ")))
br = set(ar)
cr = collections.Counter(ar)
n = len(br) - b
dr = []
for v in cr.values():
    dr.append(v)
dr.sort()
count = 0
for i in range(n):
    count += dr[i]
print(count)
a,l=map(int,input().split())
s=0
if l/a==2 or l/a==4:
	print("YES")
else:
	t,f=0,0
	for i in range(1,a+1):
		t+=i*2
		f+=i*4
if f>l:
	while f!=l:
		f=f-2
	if f==l:
		print("YES")
	else:
		print("NO")
else:
	print("NO") 

### FIXED CODE ###

a,l=map(int,input().split())
s=0
if l<a or a==0:
	print("No")
elif l/a==2 or l/a==4:
	print("Yes")

else:
	f=a*4
	if f>l:
		for i in range(a):
			f=f-2
			if f==l:
				print("Yes")
				break			
		else:
			print("No")
	else:
		print("No")
A, B, C = map(int, input().split())
K = int(input())

for i in range(K):
  if A >= B:
    B = B*2
  elif B >= C:
    C = C*2
  else:
    break

if A<B<C:
  print(Yes)
else:
  print(No)

### FIXED CODE ###

A, B, C = map(int, input().split())
K = int(input())
 
for i in range(K):
  if A >= B:
    B = B*2
  elif B >= C:
    C = C*2
  else:
    break

if A<B<C:
  print('Yes')
else:
  print('No')
import math


def func(l):
    r = math.gcd(l[0], l[1])
    for i in range(1, len(l) - 1):
        r = math.gcd(r, l[i + 1])
    return r


def main():
    n, x = map(int, input().split())
    xl = [int(i) for i in input().split()]
    xl.append(x)
    xl.sort()
    
    dl = []
    for i in range(len(xl) - 1):
        d = xl[i + 1] - xl[i]
        dl.append(d)

    print(func(dl))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import fractions


def func(l):
    r = fractions.gcd(l[0], l[1])    
    for i in range(1, len(l) - 1):
        r = fractions.gcd(r, l[i + 1])
    return r


def main():
    n, x = map(int, input().split())
    xl = [int(i) for i in input().split()]
    xl.append(x)
    xl.sort()
    
    if n == 1:
      print(abs(xl[1] - xl[0]))
      return
    
    dl = []
    for i in range(len(xl) - 1):
        d = xl[i + 1] - xl[i]
        dl.append(d)

    print(func(dl))


if __name__ == '__main__':
    main()
s = input()
n = len(s)

sa = s[:(n-1) // 2]
sb = s[(n + 1) // 2:]

if s == s[::-1] and a == a[::-1] and b == b[::-1]:
  print("Yes")
  
else:
  print("No")

### FIXED CODE ###

s = input()
n = len(s)

sa = s[:(n - 1) // 2]
sb = s[(n + 1) // 2:]

if s == s[::-1] and sa == sa[::-1] and sb == sb[::-1]:
  print("Yes")
  
else:
  print("No")
n, m, r = [ int(v) for v in input().split() ]
town_list = [ int(v)-1 for v in input().split() ]

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1


min_dist_matrix = []
for h in range(n):
	min_dist = road_matrix[h]
	searched_point = []
	sarching_point = []
	j = h
	while len(searched_point) < n:
		searched_point.append(j)
		for i in range(n):
			if road_matrix[j][i] != 10**9 and i != h:
				sarching_point.append((road_matrix[j][i],i))
				min_dist[i] = min(min_dist[i],min_dist[j] + road_matrix[j][i])
		sarching_point.sort()

		for k in range(len(sarching_point)):
			if sarching_point[k][1] not in searched_point:
				j = sarching_point[k][1]
				sarching_point = sarching_point[k+1:]
				break
	min_dist_matrix.append(min_dist)


mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0
	for j in range(r-1):
		dist += min_dist_matrix[i[j]][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)

### FIXED CODE ###

import itertools
import sys
input = sys.stdin.readline

n, m, r = [ int(v) for v in input().split() ]
town_list = [ int(v)-1 for v in input().split() ]

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1


for k in range(n):
	 for i in range(n):
		 for j in range(n):
			 road_matrix[i][j]  = min(road_matrix[i][k] + road_matrix[k][j], road_matrix[i][j])


mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0
	for j in range(r-1):
		dist += road_matrix[i[j]][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)
import sys
argv = sys.argv
x = int(argv[1])
y = int(argv[2])
print x*y,
print " "
print 2*x+2*y

### FIXED CODE ###

num = map(int, raw_input().split())
print num[0]*num[1], 2*(num[0] + num[1])
import math
q=int(input())
for j in range(q):
	AB=[int(i) for i in input().split()]
	AB.sort()#4,11
	ab=AB[0]*AB[1] #44
	for i in range(AB[0],AB[1]+1):
		if i*i>=ab:
			x=i-1
			break
	for i in range(x,ab+1):
		if x*i>=ab:
			y=i-1
			break
	cnt1=2*x
	cnts=1 if x==y else 0
	cntdd=1 if x-AB[0]>=0 else 0
	cntdu=1 if AB[1]-y>=0 and (AB[1]+1)*(x-AB[1]+y)>=ab else 0 #x-i, y+i=c,b->c,b+1
	print(cnt1-cnts-cntdd-cntdu)

### FIXED CODE ###

import math
q=int(input())
for j in range(q):
	AB=[int(i) for i in input().split()]
	AB.sort()#4,11
	ab=AB[0]*AB[1] #44
	for i in range(int(math.sqrt(ab)),AB[1]+1):
		if i*i>=ab:
			x=i-1
			break
	if x==0:
		print(0)
		continue
	for i in range(int(ab/x),ab+1):
		if x*i>=ab:
			y=i-1
			break
	cnt1=2*x
	cnts=1 if x==y else 0
	cntdd=1 if x-AB[0]>=0 else 0
	cntdu=1 if AB[1]-y>=0 and (AB[1]+1)*(x-AB[1]+y)>=ab else 0 #x-i, y+i=c,b->c,b+1
	print(cnt1-cnts-cntdd-cntdu)
# -*- coding: utf-8 -*-
a = int(input().split()[1])
c = [int(input().split()[0]) for i in range(a)]
import collections
c = collections.Counter(c)
for k,v in sorted(c.items()):
    for i in range(v):
        j = i+1
        print(f'{k:08}{j:08}')


### FIXED CODE ###

# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
d = [[i,tuple(map(int,input().split()))] for i,_ in enumerate(range(m))]
#print(d)

d.sort(key=lambda x:x[1][1])
p_cnt = [0] * (n+1)
ret_tuples = [0] * m #(市id,認識番号) のtupleのリスト

for i,v in enumerate(d):
    p = v[1][0]
    x = p_cnt[p]+1
    p_cnt[p]+=1
    ret_tuples[i] = (v[0],"{:0=6}{:0=6}".format(p,x))

ret_tuples.sort(key=lambda x:x[0])
for i in ret_tuples:
    print(i[1])
s=list(input())
k=int(input())

a = 0
while s[a] == '1':
    a += 1

if k <= a:
    print('1')
else:
    print(s[a])

### FIXED CODE ###

s=list(input())
k=int(input())

a = 0
while s[a] == '1':
    a += 1
    if a >= len(s):
        break

if k <= a:
    print('1')
else:
    if a >= len(s):
        print('1')
    else:
        print(s[a])
n,k = map(int,input().split())
l = list(map(input().split()))
ls = []
for i in range(n-k):
  if l[i] <0 and l[i+k]<0:
    ls.append(abs(l[i]))
  elif l[i] >0 and l[i+k]>0:
    ls.append(abs(l[i+k]))
  elif l[i] <0 and l[i+k]>0:
    ls.append(2*min(abs(l[i]),l[i+k]) + max(abs(l[i]),l[i+k]))
print(min(ls))

### FIXED CODE ###

n,k = map(int,input().split())
l = list(map(int,input().split()))
ls = []
for i in range(n-k+1):
  a = l[i]
  b = l[i+k-1]
  ls.append(min(abs(a)+abs(a-b), abs(b)+abs(a-b)))
print(min(ls))
H, W = map(int, input().split())
s = []
ans = 0
dp = {}
for i in range(H):
    s.append(input())

def getCount(h, w):
    if s[h][w] == '#':
	return 0
    rCnt = 0
    lCnt = 0
    uCnt = 0
    dCnt = 0
    key = str(h) + str(w)

    # to right
    rkey = key + 'r'
    if rkey in dp:
	rCnt = dp[rkey]
    else:
        for i in range(w+1, W):
            if s[h][i] == '.':
		rCnt += 1
            else:
                break
	dp[rkey] = rCnt

    # to left
    lkey = key + 'l'
    if lkey in dp:
	lCnt = dp[lkey]
    else:
        for i in reversed(range(w)):
            if s[h][i] == '.':
		lCnt += 1
            else:
                break
	dp[lkey] = lCnt

    # to down
    dkey = key + 'd'
    if dkey in dp:
	dCnt = dp[dkey]
    else:
        for i in range(h+1, H):
            if s[i][w] == '.':
		dCnt += 1
            else:
                break
	dp[dkey] = dCnt

    # to up
    ukey = key + 'u'
    if ukey in dp:
	uCnt = dp[ukey]
    else:
        for i in reversed(range(h)):
            if s[i][w] == '.':
		uCnt += 1
            else:
                break
	dp[ukey] = uCnt

    return rCnt + lCnt + uCnt + dCnt + 1

for i in reversed(range(H)):
    for j in reversed(range(W)):
	ans = max(ans, getCount(i, j))

print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
s, ans = [], 0
dpr = [[0] * W for _ in range(H)]
dpl = [[0] * W for _ in range(H)]
dpd = [[0] * W for _ in range(H)]
dpu = [[0] * W for _ in range(H)]

for i in range(H):
    s.append(input())

# to right
for i in range(H):
    for j in reversed(range(W)):
        if j == W-1 and s[i][j] == '.':
            dpr[i][j] = 1
        elif s[i][j] == '#':
            dpr[i][j] = 0
        else:
            dpr[i][j] = dpr[i][j+1] + 1

# to left
for i in range(H):
    for j in range(0, W):
        if j == 0 and s[i][j] == '.':
            dpl[i][j] = 1
        elif s[i][j] == '#':
            dpl[i][j] = 0
        else:
            dpl[i][j] = dpl[i][j-1] + 1

# to down
for i in reversed(range(H)):
    for j in range(W):
        if i == H-1 and s[i][j] == '.':
            dpd[i][j] = 1
        elif s[i][j] == '#':
            dpd[i][j] = 0
        else:
            dpd[i][j] = dpd[i+1][j] + 1

# to up
for i in range(0, H):
    for j in range(W):
        if i == 0 and s[i][j] == '.':
            dpu[i][j] = 1
        elif s[i][j] == '#':
            dpu[i][j] = 0
        else:
            dpu[i][j] = dpu[i-1][j] + 1

for i in reversed(range(H)):
    for j in reversed(range(W)):
        cnt = dpr[i][j] + dpl[i][j] + dpd[i][j] + dpu[i][j] - 3
        ans = max(ans, cnt)

print(ans)