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

# coding: utf-8
# Your code here!
MOD = 10**9 + 7
N = int(input())
S = list(input())
if S[0] == "W" or S[2*N-1] == "W":
    print(0)
    exit()

L,R = [0], []
l,r = 1,0
prev = "L"
for i in range(1, 2*N):
    if S[i] == S[i-1]:
        if prev == "L":
            R.append(i)
            r += 1
            prev = "R"
        else:
            L.append(i)
            l += 1
            prev = "L"
    else:
        if prev == "L":
            L.append(i)
            l += 1
        else:
            R.append(i)
            r += 1
    if l < r:
        print(0)
        exit()

if not (len(L) == N and len(R) == N):
    print(0)
    exit()

def fact(n):
    ret = 1
    while n > 1:
        ret *= n
        n -= 1
    return ret
    
R.reverse()
R_border = 0
cnt = 1
l = N-1
while l >= 0:
    while R_border < N-1 and L[l] < R[R_border+1]:
        R_border += 1
    cnt = cnt * (R_border + 1 - (N-1 - l)) % MOD
    l -= 1
print(cnt * fact(N) % MOD)

### FIXED CODE ###

# coding: utf-8
# Your code here!
MOD = 10**9 + 7
N = int(input())
S = list(input())
if S[0] == "W" or S[2*N-1] == "W":
    print(0)
    exit()

L,R = [0], []
total = [0 for i in range(2*N)]
total[0] = 1
l,r = 1,0
prev = "L"
for i in range(1, 2*N):
    if S[i] == S[i-1]:
        if prev == "L":
            R.append(i)
            total[i] = total[i-1] - 1
            r += 1
            prev = "R"
        else:
            L.append(i)
            total[i] = total[i-1] + 1
            l += 1
            prev = "L"
    else:
        if prev == "L":
            L.append(i)
            total[i] = total[i-1] + 1
            l += 1
        else:
            R.append(i)
            total[i] = total[i-1] - 1
            r += 1
    if l < r:
        print(0)
        exit()

if not (len(L) == N and len(R) == N):
    print(0)
    exit()

def fact(n):
    ret = 1
    while n > 1:
        ret = (ret * n) % MOD
        n -= 1
    return ret
    
cnt = 1
for r in R:
    cnt = (cnt * (total[r] + 1)) % MOD
print(cnt * fact(N) % MOD)
### BUGGY CODE ###


#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    As = [tuple(map(int, input().split())) for _ in range(N-1)]

    m = [[0 for _ in range(N)] for _ in range(N)]
    for u, v in As:
        m[u-1][v-1] = 1
        m[v-1][u-1] = 1

    n_e = max([l.count(1) for l in m])
    print(n_e)

    ans={}

    def dfs(u, c0):
        c = c0
        for v in range(N):
            if m[u][v]:
                m[u][v]=0
                m[v][u]=0
                c = c%n_e + 1
                ans[(u+1, v+1)] = c
                dfs(v, c)

    dfs(0, 0)

    for u, v in As:
        print(ans[(u, v)])



# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc146","d",main)


### FIXED CODE ###


#%%
import sys
sys.setrecursionlimit(100000)

def input():
    return sys.stdin.readline().rstrip()

def main():
    N = int(input())

    g = [[] for _ in range(N-1)]
    for i in range(N-1):
        a, b = map(int, input().split())
        g[a-1].append((b-1, i))

    ans = [[None] for _ in range(N-1)]

    def dfs(v0, c0):
        c = 1
        for v1, e in g[v0]:
            if c==c0:
                c += 1
            ans[e] = c
            if v1 < N-1:
                dfs(v1, c)
            c += 1

    dfs(0, 0)

    print(max(ans))
    for c in ans:
        print(c)



# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc146","d",main)
### BUGGY CODE ###

#200419C
N = int(input())
A = list(map(int,input().split()))
A = sorted(A)

for i in range(N-1):
    print(A.count(i+1))
    for j in range(A.count(i+1)):
        A.remove(i +1)
        #print(A)


print("0")

### FIXED CODE ###

#200419C
N = int(input())
A = list(map(int,input().split()))
A = sorted(A)

count = 0
for i in range(N-1):
    L = len(A)
    #print(A)
    Ans = 0
    count += Ans
    for j in range(L-count):
        if A[count + j]==i+1:
            Ans += 1
        else:            
            break
    print(Ans)
    count += Ans

        
print("0")
### BUGGY CODE ###

S = input()
s = list(S)
n = len(s)
ans = [[0 for i in range(13)]for i in range(n)]
mod = 10**9+7
if s[0] == '?':
    for i in range(10):
        ans[0][i] += 1
else:
    ans[0][int(s[0])] += 1
for i in range(n-1):
    if s[i+1] == '?':
        for j in range(10):
            for k in range(13):
                ans[i+1][(10*k+j)%13] += ans[i][k]%mod
    else:
        for k in range(13):
            ans[i+1][(10*k+int(s[i+1]))%13] += ans[i][k]%mod
print((ans[n-1][5])%(10**9+7))

### FIXED CODE ###

S = input()
s = list(S)
n = len(s)
ans = [[0 for i in range(13)]for i in range(n)]
mod = 10**9+7
if s[0] == '?':
    for i in range(10):
        ans[0][i] += 1
else:
    ans[0][int(s[0])] += 1
for i in range(n-1):
    if s[i+1] == '?':
        for j in range(10):
            for k in range(13):
                ans[i+1][(10*k+j)%13] += ans[i][k]%mod
    else:
        for k in range(13):
            ans[i+1][(10*k+int(s[i+1]))%13] += ans[i][k]%mod
print((ans[n-1][5])%(10**9+7))
### BUGGY CODE ###

n, m = map(int, input().split())

ans = 0
for i in range(1, m//n+1):
    if m % i == 0:
        ans = max(ans, i)
        if m // i > i and m // i <= m // n:
            ans = max(ans, m // i)
            
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
a = m // n
ans = 0

for i in range(1, a + 1):
    if m % i == 0:
        ans = i
        
        if (m // i) > i and (m // i) <= a:
            ans = m // i
            break
        
print(ans)
### BUGGY CODE ###

L, R = map(int, input().split())
modlist =[]
for i in range(L, R):
    for j in range(L+1,R+1):
        nummod = i * j % 2019
        modlist.append(nummod)
    if nummod == 0:
        break
print(min(modlist))

### FIXED CODE ###

L, R = map(int, input().split())
modlist =[]
for i in range(L, R):
    for j in range(L+1,R+1):
        nummod = i * j % 2019
        modlist.append(nummod)
        if nummod == 0:
            break
    if nummod == 0:
        break
print(min(modlist))
### BUGGY CODE ###

N = int(input())
S = input()
DP = [[0]*5005 for _ in range(5005)]

for i in range(N):
    for j in range(N):
        if S[i] == S[j]:
            DP[N-i][N-j] = DP[N-i+1][N-j+1] + 1
ans = 0
for i in range(N):
    for j in range(N):
        if i >= j:
            continue
        now = min(DP[i][j], j-i)
        ans = max(ans, now)

print(ans)

### FIXED CODE ###

N = int(input())
S = input()
DP = [[0]*5005 for _ in range(5005)]

for i in range(N):
    for j in range(N):
        if S[i] == S[j]:
            DP[N-i][N-j] = DP[N-i+1][N-j+1] + 1
ans = 0
for i in range(N):
    for j in range(N):
        if i >= j:
            continue
        now = min(DP[i][j], j-i)
        ans = max(ans, now)

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

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0

    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True

        for j in range(n):
            d[j] = min(d[j],d[v]+cost[v][j])
    return d

n,x,y = map(int,input().split())

#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
cost = [[float("inf") for i in range(n)] for i in range(n)]

for i in range(n-1):
    cost[i][i+1] = 1
    cost[i+1][i] = 1
cost[x-1][y-1] = 1
cost[y-1][x-1] = 1

cost = tuple(cost)

ans = [0 for _ in range(n)]
for i in range(n):
    #nは頂点数、wは辺の数
    res = dijkstra(i,n,n,cost)
    for j in range(i+1,n):
        ans[res[j]] += 1

for i in range(1,n):
    print(ans[i])


### FIXED CODE ###

from scipy.sparse.csgraph import dijkstra
import sys
def main():
	input = sys.stdin.readline

	n,x,y = map(int,input().split())

	route = [[0 for _ in range(n)]for _ in range(n)]
	for i in range(n-1):
		route[i][i+1] = 1

	route[x-1][y-1] = 1
	route[y-1][x-1] = 1
	route = tuple(route)
	#res = shortest_path(route, unweighted=False,directed=False)
	res = tuple(dijkstra(route, directed=False))

	ans = [0 for _ in range(n)]
	for i in range(n):
		for j in range(i,n):
			ans[int(res[i][j])] += 1

	for i in range(1,n):
		print(ans[i])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
A = [int(input()) for x in range(N)]
As = sorted(A)

for i in range(N):
    As.remove(A[i])
    print(As[-1])
    As.insert(i, A[i])
    


### FIXED CODE ###

N = int(input())
A = [int(input()) for x in range(N)]
As = sorted(A)

for i in range(N):
    if As[-1] > A[i]:
        print(As[-1])
        
    elif As[-1] == A[i]:
        print(As[-2])
### BUGGY CODE ###

# N = 4
N = int(input())
# X = [2, 4, 4, 3]
X = list(map(int, input().split(' ')))

# def get_median(l):
#     return median(l)

for i in range(N):
    target_l = X[:i] + X[i+1:]
    target_l = sorted(target_l)
    print(target_l[int((N-1)/2)])

### FIXED CODE ###

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

# N = 2
# X = [1, 2]

# N = 6
# X = [5, 5, 4, 4, 3, 3]

# target = int((N-1)/2)
first_m = int(N/2)
second_m = first_m - 1
X_ = sorted(X)
for i in range(N):
    if X[i] <= X_[second_m]: print(X_[first_m])
    else: print(X_[second_m])
### BUGGY CODE ###

n = int(input())
s_li = []
for i in range(n):
    s = input()
    s_i = {}
    for j in range(10):
        s_i[s[j]] = 0
    for j in range(10):
        s_i[s[j]] += 1    
    s_li.append(s_i)

ans = 0

for i in range(n):
    for j in range(n):
        if i >= j :
            continue
        if s_li[i] == s_li[j]:
            ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s_li = [input() for i in range(n)]

ans = 0
s_dict = {}
for i in s_li :
    s_i = [ch for ch in i]
    s_i.sort()
    s_i = "".join(s_i)
    if s_i in s_dict :
        ans += s_dict[s_i]
        s_dict[s_i] += 1
    else :
        s_dict[s_i] = 1
print(ans)
### BUGGY CODE ###

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

L = sorted(L)
ans = 0
H = {}
for i in range(N-1):
    for j in range(i+1, N-1):
        H.update({(i,j): L[i]+L[j]})


for h, v in H.items():
    for j in range(h[1]+1, N):
#        if h[0] == j or h[1] == j: continue
        if h[1]>=j: continue
        if v > L[j]:
            ans += 1
        else: break

print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import bisect
N = int(input())
L = sorted(list(map(int, input().split())))
ans = 0
for i in range(len(L)):
    for j in range(i+1, len(L)):
        b_i = bisect.bisect_left(L, L[i]+L[j]) # a+bより小さい数
        ans += b_i - (j+1)
print(ans)
### BUGGY CODE ###

n = int(input())
sum = 0
for i in range(n):
  sum += i
print(sum)

### FIXED CODE ###

n = int(input())
sum = n * (n - 1) // 2
print(sum)
### BUGGY CODE ###

k=int(input())
ans=1
s=7
if k%2==0:
    print(-1)
else:
    mod=k
    while s%mod!=0:
        s=(10*s+7)%mod
        ans+=1
    print(ans)

### FIXED CODE ###

k=int(input())
ans=1
s=7
if k%2==0 or k%5==0:
    print(-1)
else:
    mod=k
    while s%mod!=0:
        s=(10*s+7)%mod
        ans+=1
    print(ans)
### BUGGY CODE ###

from numba import jit

n , m = map(int, input().split())
p = list(map(int,input().split()))


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
    @jit
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

uf = UnionFind(n)

for i in range(m):
    x , y = map(int, input().split())
    x-=1
    y-=1
    uf.union(x,y)
ans = 0

ro=uf.roots()

for i in ro:
    mem = uf.members(i)
    for j in mem:
        if p[j]-1 in mem:
            ans+=1
print(ans)



### FIXED CODE ###

n , m = map(int, input().split())
p = list(map(int,input().split()))

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)


uf = UnionFind(n)

for i in range(m):
    x , y = map(int, input().split())
    x-=1
    y-=1
    uf.union(x,y)
ans = 0
for i in range(n):
    if uf.same(i,p[i]-1):
        ans+=1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h, w, m = LI()
bomb = defaultdict(lambda : 0)
cnt_h = [0] * h
cnt_w = [0] * w
for _ in range(m):
    H, W = LI()
    bomb[(H-1, W-1)] = 1
    cnt_h[H-1] += 1
    cnt_w[W-1] += 1

m_h = max(cnt_h)
m_w = max(cnt_w)
H_l = []
W_l = []
for i in range(h):
    if cnt_h[i] == m_h:
        H_l.append(i)

for i in range(w):
    if cnt_w[i] == m_w:
        W_l.append(i)

ans = m_h + m_w

flag = False
for i in H_l:
    for j in W_l:
        if not bomb[(i, j)]:
            flag = True
if flag:
    print(ans)
else:
    print(ans-1)

### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h, w, m = LI()
bomb = defaultdict(lambda : 0)
cnt_h = [0] * h
cnt_w = [0] * w
for _ in range(m):
    H, W = LI()
    bomb[(H-1, W-1)] = 1
    cnt_h[H-1] += 1
    cnt_w[W-1] += 1

m_h = max(cnt_h)
m_w = max(cnt_w)
H_l = defaultdict(int)
W_l = defaultdict(int)
for i in range(h):
    if cnt_h[i] == m_h:
        H_l[i] = 1

for i in range(w):
    if cnt_w[i] == m_w:
        W_l[i] = 1

ans = m_h + m_w

for i in H_l.keys():
    for j in W_l.keys():
        if bomb[(i, j)] == 0:
            print(ans)
            quit()

print(ans-1)
### BUGGY CODE ###

h, w, m = list(map(int, input().split()))
count_row = [0 for _ in range(h)]
count_col = [0 for _ in range(w)]
X = [[0 for i in range(w)] for _ in range(h)]
for i in range(m):
    mh, mw = list(map(int, input().split()))
    X[mh-1][mw-1] = 1
    count_row[mh-1] += 1
    count_col[mw-1] += 1
max_row_index = [i for i, v in enumerate(count_row) if v == max(count_row)]
max_col_index = [i for i, v in enumerate(count_col) if v == max(count_col)]
ans = max(count_row) + max(count_col) -1
flag = False
for i in max_row_index:
    for j in max_col_index:
        if X[i][j] == 0:
            ans += 1
            flag = True
            break
    if flag:
        break

print(ans)

### FIXED CODE ###

h, w, m = list(map(int, input().split()))
count_row = [0 for _ in range(h)]
count_col = [0 for _ in range(w)]
# X = [[0 for i in range(w)] for _ in range(h)]
max_col = 0
max_row = 0
max_row_index = []
max_col_index = []
M = set()
for i in range(m):
    mh, mw = list(map(int, input().split()))
    # X[mh-1][mw-1] = 1
    M.add((mh-1, mw-1))
    count_row[mh-1] += 1
    count_col[mw-1] += 1
    if count_row[mh-1] > max_row:
        max_row = count_row[mh-1]
        max_row_index = [mh-1]
    elif count_row[mh-1] == max_row:
        max_row_index.append(mh-1)
    
    if count_col[mw-1] > max_col:
        max_col = count_col[mw-1]
        max_col_index = [mw-1]
    elif count_col[mw-1] == max_col:
        max_col_index.append(mw-1)
# max_row_index = [i for i, v in enumerate(count_row) if v == max(count_row)]
# max_col_index = [i for i, v in enumerate(count_col) if v == max(count_col)]
# ans = max(count_row) + max(count_col) -1
ans = max_col + max_row -1

if len(max_col_index)*len(max_row_index) > m:
    ans += 1
else:
    flag = False
    for i in max_row_index:
        for j in max_col_index:
            if (i, j) not in M:
                ans += 1
                flag = True
                break
        if flag:
            break
print(ans)
### BUGGY CODE ###

n = int(raw_input())
L = []

for i in xrange(n):
    a, b = raw_input().split()
    if a == "insert":
        L.append(b)
    if a == "find":
        if b in L:
            print "yes"
        else:
            print "no"

### FIXED CODE ###

n = int(raw_input())
dic = {}

for i in xrange(n):
    a, b = raw_input().split()
    if a == "insert":
        dic[b] = True
    elif a == "find":
        if b in dic:
            print "yes"
        else:
            print "no"
### BUGGY CODE ###

import sys
from itertools import accumulate

n, k, *aaa = map(int, sys.stdin.buffer.read().split())

for _ in range(k):
    bbb = [0] * (n + 1)
    for i in range(n):
        a = aaa[i]
        bbb[max(0, i - a)] += 1
        bbb[min(n, i + a + 1)] -= 1

    aaa = list(accumulate(bbb))
    aaa.pop()

    if all(a == n for a in aaa):
        break

print(*aaa)


### FIXED CODE ###

import sys
from itertools import accumulate

n, k, *aaa = map(int, sys.stdin.buffer.read().split())

for _ in range(k):
    bbb = [0] * (n + 1)
    for i in range(n):
        a = aaa[i]
        bbb[max(0, i - a)] += 1
        bbb[min(n, i + a + 1)] -= 1

    aaa = list(accumulate(bbb))
    aaa.pop()

    if all(a == n for a in aaa):
        break

print(*aaa)
### BUGGY CODE ###

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

from collections import defaultdict
D = defaultdict(list)

for i in range(N):
    for j in range(i+1,N+1):
        if D[S[i:j]] == []:
            D[S[i:j]].append(j-i)
        D[S[i:j]].append(i)
        
ans = 0
for i in D:
    L = D[i][0]
    tmp = 0
    if len(D[i]) >= 3:
        if D[i][1] + L <= D[i][-1]:
            tmp = L
    if ans < tmp:
        ans = tmp
print(ans)

### FIXED CODE ###

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

def main():
    N = int(input())
    S = input()
    #N = 5000
    #S = "a"*N
    import time
    star = time.time()
    A = [[] for i in range(N)]
    for i in range(N):
        A[i] = [0]*i + z_algo(S[i:])
    ans = 0
    for i in range(N):
        for j in range(N):
            if i + A[i][j] <= j and ans < A[i][j]:
                ans = A[i][j]
    
    g = time.time()
    #print(g-star)
    print(ans)
    
main()
### BUGGY CODE ###

import bisect
N = int(input())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))
count = 0
for a in A:
    b = bisect.bisect_left(B,a+1)
    if b == N:
        continue
    for i in range(b,N):
        c = bisect.bisect_left(C,B[i]+1)
        if c == N:
            continue
        count += N-c
print(count)

### FIXED CODE ###

import bisect
N = int(input())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))
count = 0
for b in B:
    a = bisect.bisect_left(A,b)
    c = bisect.bisect_right(C,b)
    count += a*(N-c)
print(count)
### BUGGY CODE ###

n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
alist = [[] for _ in range(n)]
for u, v in uv:
    alist[u-1].append(v-1)
s, t = map(int, input().split())

alist3 = [set([]) for _ in range(n)]
for v in range(n):
    for v1 in alist[v]:
        for v2 in alist[v1]:
            for v3 in alist[v2]:
                alist3[v].add(v3)

# BFS
queue = [s-1]
visited = [-1]*n
visited[s-1] = 0
while len(queue) > 0:
    q = queue.pop(0)
    for v in alist3[q]:
        if visited[v] < 0:
            queue.append(v)
            visited[v] = visited[q] + 1
print(visited[t-1])




### FIXED CODE ###

n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

alist = [[] for _ in range(3*n)]
for u, v in uv:
    u, v = u-1, v-1
    alist[u].append(n+v)
    alist[n+u].append(2*n+v)
    alist[2*n+u].append(v)


# BFS
queue = [s-1]
visited = [-3]*(3*n)
visited[s-1] = 0
while len(queue) > 0:
    q = queue.pop(0)
    for v in alist[q]:
        if visited[v] < 0:
            queue.append(v)
            visited[v] = visited[q] + 1
print(visited[t-1]//3)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
H, W = map(int, input().split())
S = [input() for _ in range(H)]

memo = [[[0] * 4 for _ in range(W)] for _ in range(H)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y, i):
	nx = x + dx[i]
	ny = y + dy[i]
	if nx >= 0 and nx < H and ny >= 0 and ny < W and memo[nx][ny][i] > 0:
		memo[x][y][i] = memo[nx][ny][i] + 1
		return memo[x][y][i]
	elif nx >= 0 and nx < H and ny >= 0 and ny < W and S[nx][ny] == '.':
		memo[x][y][i] = dfs(nx, ny, i) + 1
		return memo[x][y][i]
	else:
		return 0
		
ans = 0

for sx in range(H):
	for sy in range(W):
		if S[sx][sy] == '.':
			tmp = 1

			for j in range(4):
				nx = sx + dx[j]
				ny = sy + dy[j]
				if nx >= 0 and nx < H and ny >= 0 and ny < W and memo[nx][ny][j] > 0:
					memo[sx][sy][j] = memo[nx][ny][j] + 1
					tmp += memo[sx][sy][j]
				else:
					tmp += dfs(sx, sy, j)
				
			if tmp > ans:
				ans = tmp
				
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
H, W = map(int, input().split())
S = [input() for _ in range(H)]
R = [[0] * W for _ in range(H)]
L = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]

for i in range(H):
	for j in range(W):
		if S[i][j] == '.':
			if j > 0:
				L[i][j] = L[i][j - 1] + 1
			elif j == 0:
				L[i][j] = 1
				
			if i > 0:
				U[i][j] = U[i - 1][j] + 1
			elif i == 0:
				U[i][j] = 1
		
		if S[i][W - j - 1] == '.':
			if j > 0:
				R[i][W - j - 1] = R[i][W - j] + 1
			elif j == 0:
				R[i][W - j - 1] = 1
		
		if S[H - i - 1][j] == '.':
			if i > 0:
				D[H - i - 1][j] = D[H - i][j] + 1
			elif i == 0:
				D[H - i - 1][j] = 1
			
ans = 0
for i in range(H):
	for j in range(W):
		tmp = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
		if tmp > ans:
			ans = tmp
			
print(ans)