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

import math
import itertools
ans = 0
k = int(input())

permutations_lis = list(itertools.product(range(1,k+1), repeat=3))
for one_case in permutations_lis:
    ans += math.gcd(one_case[0],math.gcd(one_case[1],one_case[2]))
print(ans)

### FIXED CODE ###

k = int(input())
li=[1, 9, 30, 76, 141, 267, 400, 624, 885, 1249, 1590, 2208, 2689, 3411, 4248, 5248, 6081, 7485, 8530, 10248, 11889, 13687, 15228, 17988, 20053, 22569, 25242, 28588, 31053, 35463, 38284, 42540, 46581, 50893, 55362, 61824, 65857, 71247, 76884, 84388, 89349, 97881, 103342, 111528, 120141, 128047, 134580, 146316, 154177, 164817, 174438, 185836, 194157, 207927, 218812, 233268, 245277, 257857, 268182, 288216, 299257, 313635, 330204, 347836, 362973, 383709, 397042, 416448, 434025, 456967, 471948, 499740, 515581, 536073, 559758, 583960, 604833, 633651, 652216, 683712, 709065, 734233, 754734, 793188, 818917, 846603, 874512, 909496, 933081, 977145, 1006126, 1041504, 1073385, 1106467, 1138536, 1187112, 1215145, 1255101, 1295142, 1342852, 1373253, 1422195, 1453816, 1502376, 1553361, 1595437, 1629570, 1691292, 1726717, 1782111, 1827492, 1887772, 1925853, 1986837, 2033674, 2089776, 2145333, 2197483, 2246640, 2332104, 2379085, 2434833, 2490534, 2554600, 2609625, 2693919, 2742052, 2813988, 2875245, 2952085, 3003306, 3096024, 3157249, 3224511, 3306240, 3388576, 3444609, 3533637, 3591322, 3693924, 3767085, 3842623, 3912324, 4027884, 4102093, 4181949, 4270422, 4361548, 4427853, 4548003, 4616104, 4718640, 4812789, 4918561, 5003286, 5131848, 5205481, 5299011, 5392008, 5521384, 5610705, 5739009, 5818390, 5930196, 6052893, 6156139, 6239472, 6402720, 6493681, 6623853, 6741078, 6864016, 6953457, 7094451, 7215016, 7359936, 7475145, 7593865, 7689630, 7886244, 7984165, 8130747, 8253888, 8403448, 8523897, 8684853, 8802826, 8949612, 9105537, 9267595, 9376656, 9574704, 9686065, 9827097, 9997134, 10174780, 10290813, 10493367, 10611772, 10813692]
print(li[k-1])
### BUGGY CODE ###

from math import sqrt, factorial
from sys import setrecursionlimit
setrecursionlimit(100000)

def inpl(): return list(map(int, input().split()))
N = int(input())
S = int(input())

RN = int(sqrt(N))
RN += ((RN+1)**2 == N)

def func(b, N):
    if b == 0:
        return -1
    tmp = 0
    while N:
        N, d = divmod(N, b)
        tmp += d
    return tmp

for b in range(2, RN+1):
    tmp = func(b, N)
    if tmp == S:
        print(b)
        break
else:
    for x in range(RN, 0, -1):
        num = (N-S+x)//x
        b = num//x
        if func(b, N) == S:
            print(b)
            break
    else:
        print(-1)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from math import sqrt
n = int(input())
s = int(input())

def f(b, n):
    ans = 0
    while n >= b:
        ans += n%b
        n = n//b
    return ans + n

if n==s:
    print(n+1)
    exit()

for b in range(2, int(sqrt(n))+1):
    if f(b, n) == s:
        print(b)
        break
else:
    for p in range(1, int(sqrt(n))+1)[::-1]:
        d, m = divmod(p+n-s, p)
        if m == 0 and d >= 2 and f(d, n) == s:
            print(d)
            break
    else:
        print(-1)
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
	a.append(int(input()))
ma=max(a)
keiken=0
b=[]
for i in range(n):
	if a[i]==ma and keiken==0:
		for ii in range(n):
			if ii!=i:
				b.append(a[ii])
		print(max(b))
	else:
		print(ma)


### FIXED CODE ###

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

N = int(input())
a = [int(input()) for _ in range(N)]
L = [0]
i = 0
cnt = 0
while True:
    if a[i]-1 == 1:
        cnt += 1
        break
    elif a[i]-1 in L:
        cnt = -1
        break
    else:
        L.append(a[i]-1)
        cnt += 1
        i = a[i]-1
print(cnt)

### FIXED CODE ###

N = int(input())
a = [int(input()) for _ in range(N)]
L = set([0])
i = 0
cnt = 0
while True:
    if a[i]-1 == 1:
        cnt += 1
        break
    elif a[i]-1 in L:
        cnt = -1
        break
    else:
        L.add(a[i]-1)
        cnt += 1
        i = a[i]-1
print(cnt)
### BUGGY CODE ###

N = int(input())
S = input()
count = 0
while True:
	if S.count('R') == 0:
			break
	if S[0] == 'R':
		S=S.lstrip('R')
	else:
		count += 1
		S = S[1:]
		Rpos = S.rfind('R')
		S = S[:Rpos]
print(count)


### FIXED CODE ###

N = int(input())
S = input()
part = 0
leftW = 0
rightR = S.count('R')
moves = [rightR]

for i in range(N):
	if S[i] == 'R':  # rightR:decrease
		rightR -= 1
	else:          # leftW:increase
		leftW += 1
	moves.append(max(leftW, rightR))
# print(moves)
ans = min(moves[i] for i in range(N+1))
print(ans)
### BUGGY CODE ###

#!python3.4.3

n = int(input())
a_list = list(map(int, input().split(' ')))
a_list.sort()
A = 2**(n//2)%(10**9+7)

for i in range(1, n):
    c = a_list.count(i)
    if c%2 != 0:
        A = 0
        break
print(A)


### FIXED CODE ###

#!python3.4.3

n = int(input())
a = list(map(int, input().split(' ')))
a.sort()
# a_list.sort()

b = [abs(i) for i in range(-n+1, n, 2)]
b.sort()
if a==b:
    result = 2**(n//2)%(10**9+7)
else:
    result = 0
print(result)
### BUGGY CODE ###

n,k = input().split(" ")
n = int(n)
k = int(k)
min = 1000000000000000001
abs0 = 0
if n == 0:
    print(0)
elif k == 1:
    print(0)
elif n == 1:
    print(1)
else:
    for i in range(1000000000):
        abs0 = abs(k - n)
        n = abs0
        if abs0 < min:
            min = abs0
        elif min == abs0:
            print(abs0)
            break

### FIXED CODE ###

n,k = input().split(" ")
n = int(n)
k = int(k)
min = 1000000000000000001
abs0 = 0
if n == 0:
    print(0)
elif k == 1:
    print(0)
elif n == 1:
    print(1)
else:
    if n > k:
        n = n % k
        print(abs(k-n))
    else:        
        for i in range(1000000000):
            abs0 = abs(k - n)
            n = abs0
            if abs0 < min:
                min = abs0
            elif min == abs0:
                print(abs0)
                break
### BUGGY CODE ###

M=998244353
N=int(input())
d=[0]*90001
d[0]=1
e=[0]*90001
e[0]=1
z=1
s=0
for _ in range(N):
	a=int(input())
	i=s
	while i>=0:
		d[i+a]+=d[i]
		d[i+a]%=M
		d[i]*=2
		d[i]%=M
		e[i+a]+=e[i]
		e[i+a]%=M
		i-=1
	s+=a
	z=z*3%M
for i in range(s+1>>1,s+1):
	z-=d[i]*3
	z%=M
print([(z+e[s//2]*3)%M,z][s%2])


### FIXED CODE ###

M=998244353
N=int(input())
d=[0]*90001
d[0]=1
e=[0]*90001
e[0]=1
z=1
s=0
for _ in range(N):
	a=int(input())
	i=s
	while i>=0:
		d[i+a]+=d[i]%M
		d[i]*=2
		e[i+a]+=e[i]%M
		i-=1
	s+=a
	z=z*3%M
for i in range(s+1>>1,s+1):
	z-=d[i]*3
	z%=M
print([(z+e[s//2]*3)%M,z][s%2])
### BUGGY CODE ###

H, W = map(int, input().split())
STAGE = [list(input()) for _ in range(H)]

def score(y, x):
	if STAGE[y][x] == "#":
		return 0
	s = 1
	for n in range(y + 1, H):
		if STAGE[n][x] == ".":
			s += 1
		else:
			break
	for n in range(y - 1, -1, -1):
		if STAGE[n][x] == ".":
			s += 1
		else:
			break
	for n in range(x + 1, W):
		if STAGE[y][n] == ".":
			s += 1
		else:
			break
	for n in range(x - 1, -1, -1):
		if STAGE[y][n] == ".":
			s += 1
		else:
			break
	return s

result = 0
for y in range(H):
	for x in range(W):
		result = max(result, score(y, x))

print(result)


### FIXED CODE ###

H, W = map(int, input().split())
STAGE = [list(input()) for _ in range(H)]

sum_s = [[], []]

for y in range(H):
	count, line = 0, []
	for x in range(W):
		if STAGE[y][x] == ".":
			count += 1
		else:
			if 0 < count:
				line += [count] * count
			line += [0]
			count = 0
	else:
		if 0 < count:
			line += [count] * count
	sum_s[0] += [line]

for x in range(W):
	count, line = 0, []
	for y in range(H):
		if STAGE[y][x] == ".":
			count += 1
		else:
			if 0 < count:
				line += [count] * count
			line += [0]
			count = 0
	else:
		if 0 < count:
			line += [count] * count
	sum_s[1] += [line]
"""
for line in sum_s[0]:
	print(*line)
print()
for line in sum_s[1]:
	print(*line)
"""
max_score = 0
for y in range(H):
	for x in range(W):
		max_score = max(max_score, sum_s[0][y][x] + sum_s[1][x][y] - 1)

print(max_score)
### BUGGY CODE ###

import itertools
n, y = map(int, input().split())
a = [i for i in range(y // 10000 + 1)]
b = [i for i in range(y // 5000 + 1)]
m = list(itertools.product(a, b))
ans = 0
for i in range(len(m)):
  if n - m[i][0] - m[i][1] >= 0 and m[i][0] * 10000 + m[i][1] * 5000 + (n - m[i][0] - m[i][1]) * 1000 == y:
    print(m[i][0], m[i][1], n - m[i][0] - m[i][1])
    ans = 1
    break
if ans == 0:
  print('-1 -1 -1')

### FIXED CODE ###

import itertools
n, y = map(int, input().split())
k = [i for i in range(n + 1)]
ans = 0
for a, b in itertools.product(k, k):
  if n >= a + b and a * 10000 + b * 5000 + (n - a - b) * 1000 == y:
    print(a, b, n - a - b)
    ans = 1
    break
if ans == 0:
  print('-1 -1 -1')
### BUGGY CODE ###

n,k=map(int,input().split())
p1=list(map(int,input().split()))
c=0
i=0
while (i+k)<=n:
  c_list=[]
  for j in range(k):
    c_list.append((p1[j+i]+1)/2)
    if sum(c_list)>c:
      c=sum(c_list)
  i+=1
print(c)
    
    

### FIXED CODE ###

n,k=map(int,input().split())
p1=list(map(int,input().split()))
p2=[]
for i in range(n):
  p2.append(((1+p1[i])/2))
ans=sum(p2[0:k])
sum1=sum(p2[0:k])
for j in range(n-k):
  sum1=sum1+p2[j+k]-p2[j]
  if ans<sum1:
    ans=sum1
print(ans)
### BUGGY CODE ###

raw_input = input()
length = len(raw_input)
input_number = int(raw_input)
count = 0

top_lane = input().split()
mid_lane = input().split()
bot_lane = input().split()

for i in range(input_number):
    top_lane[i] = int(top_lane[i])
    mid_lane[i] = int(mid_lane[i])
    bot_lane[i] = int(bot_lane[i])

for i in range(input_number):
    top = top_lane[i]
    for j in range(input_number):
        mid = mid_lane[j]
        for k in range(input_number):
            bot = bot_lane[k]
            if top < mid < bot:
                count += 1

print(count)

### FIXED CODE ###

import bisect

raw_input = input()
input_number = int(raw_input)
counts = 0

top_lane = input().split()
mid_lane = input().split()
bot_lane = input().split()

for i in range(input_number):
    top_lane[i] = int(top_lane[i])
    mid_lane[i] = int(mid_lane[i])
    bot_lane[i] = int(bot_lane[i])

top_lane.sort()
mid_lane.sort()
bot_lane.sort()

for mid in mid_lane:
    top_index = bisect.bisect_left(top_lane, mid)
    bot_index = input_number - bisect.bisect_right(bot_lane, mid)
    counts += top_index * bot_index

print(counts)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

if n==1:
    print('Yes')

else:
    z=0
    for i in range(n-2):
        if h[i]-1>h[i+1]:
            print('No')
            break
        elif h[i]-1==h[i+1]:
            if h[i]-1>min(h[i+1:n]):
                print('No')
                break
            else:
                z+=1
        else:
            z+=1
           
    if z==n-2:
        print('Yes')


### FIXED CODE ###

import sys
input = sys.stdin.readline

n=int(input())
h=list(map(int,input().split()))
l=h
s=[]
t=max(h)

for i in range(n-1):
        if l[i]-1==l[i+1]:
                l[i]=l[i]-1
                s.append(l[i])
        elif l[i]==l[i+1] and l[i]==t:
                l[i]=l[i]-1
                s.append(l[i])
        elif l[i]-1>l[i+1]:
                break
        elif l[i]-1<l[i+1]:
                s.append(l[i])
                continue

s.append(h[n-1])
s.sort()
if len(s)==n:
        if l==s:
                print('Yes')
        else:
                print('No')

else:
        print('No')
### BUGGY CODE ###

a, b = list(map(int, input().split()))

cands = set()

for i in range(2, min(a, b) + 1):
    if a % i != 0 or b % i != 0:
        continue
    if not any([i % x == 0 for x in cands]):
        cands.add(i)

print(len(cands) + 1)

### FIXED CODE ###

a, b = list(map(int, input().split()))


def prime_factorize(n):
    """Return the prime factorization of n > 1.
    >>> prime_factorize(36)
    [2, 2, 3, 3]
    """
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2

    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2

    if n != 1:
        a.append(n)

    return a


def main(a, b):
    pf_a = set(prime_factorize(a))
    pf_b = set(prime_factorize(b))
    return len(pf_a & pf_b) + 1


print(main(a, b))
### BUGGY CODE ###

def submit():
  n,q = map(int,input().split())
  y = [[] for _ in range(n)]
  c = [0]*n
  for _ in range(n-1):
    ai,bi = map(int,input().split())
    y[ai-1].append(bi-1)
    y[bi-1].append(ai-1)
  for _ in range(q):
    pi,xi = map(int,input().split())
    c[pi-1] += xi
  z = [(0,-1)]
  while z:
    j,b = z.pop(0)
    for yj in y[j]:
      if yj != b:
        z.append((yj,j))
        c[yj] += c[j]
  for i in range(n):
    print(c[i],end=" ")
submit()

### FIXED CODE ###

from collections import deque
def submit():
  n,q = map(int,input().split())
  y = [[] for _ in range(n)]
  c = [0]*n
  for _ in range(n-1):
    ai,bi = map(int,input().split())
    y[ai-1].append(bi-1)
    y[bi-1].append(ai-1)
  for _ in range(q):
    pi,xi = map(int,input().split())
    c[pi-1] += xi
  z = deque([[0,-1]])
  while z:
    j,b = z.popleft()
    for yj in y[j]:
      if yj != b:
        z.append([yj,j])
        c[yj] += c[j]
  for i in range(n):
    print(c[i],end=" ")
submit()
### BUGGY CODE ###

import sys

def f(s):
    if s=="A":
        return 0
    elif s=="B":
        return 1
    else:
        return 2

S=list(map(f,input()))+[3,3,3]
N=len(S)


if N<=2:
    print(0)
    sys.exit()

T=0
F=True
while F:
    j=0
    F=False
    while j<=N-3:
        k=j
        while (S[k]==0) and (S[k+1]==1) and (S[k+2]==2):
            k+=3

        for i in range(j,k):
            S[i]=(S[i]+1)%3
            F=True
            
        T+=(k-j)//3
        j=k+1
print(T)
            


### FIXED CODE ###

import sys

def f(s):
    if s=="A":
        return 0
    elif s=="B":
        return 1
    else:
        return 2

S=list(map(f,input()))
N=len(S)

if N<=2:
    print(0)
    sys.exit()

T=0
U=0

I=0
K=0
while I<N-2:
    if (S[I]==0) and (S[I+1]==1) and (S[I+2]==2):
        U+=1
        T+=U
        I+=3
    elif S[I]==0:
        U+=1
        I+=1
    elif (S[I]==1) and (S[I+1]==2):
        T+=U
        I+=2
    else:
        U=0
        I+=1

if (S[-2]==1 and S[-1]==2) and S[-3]!=0:
    T+=U
    
print(T)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)

def main():
    n,k = [int(i) for i in input().strip().split()]
    A = [int(i) for i in input().strip().split()] 
    cur_mul = [1] * n
    for i in range(n):
        if i == 0:
            cur_mul[i] = A[i]
        elif i > 0 and i <= k-1:
            cur_mul[i] = A[i] * cur_mul[i - 1]
        elif i > k-1:
            cur_mul[i] = cur_mul[i - 1] * A[i] // A[i - k]
            if cur_mul[i] > cur_mul[i - 1]:
                print("Yes")
            else:
                print("No")
    return

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)

def main():
    n,k = [int(i) for i in input().strip().split()]
    A = [int(i) for i in input().strip().split()] 

    for i in range(k, n):
        if A[i] > A[i - k]:
            print("Yes")
        
        else:
            print("No")
    return

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

n = int(input())
A = list(map(int,input().split()))
B = []
def Cumulative_sum(n,A):
  B=[0]
  for i in range(n):
    B.append(A[i] + B[i])
  return B
B = Cumulative_sum(n,A)
count = 0
for x in range(n):
  for y in range(x+1,n+1):
    if B[y] - B[x] == 0:
      count += 1
print(count)

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
B = []
def Cumulative_sum(n,A):
  B=[0]
  for i in range(n):
    B.append(A[i] + B[i])
  return B
B = Cumulative_sum(n,A)
B_sort = sorted(B)
y = 0
ans = 0
count = 1
while(y < n):
  if B_sort[y] == B_sort[y+1]:
    count += 1
    y += 1
  else:
    if count > 1:
      ans += (count*(count-1)/2)
      count = 1
    y += 1
    
if count > 1:
  ans += (count*(count-1)/2)
print(int(ans))
### BUGGY CODE ###

N,K = map(int, input().split())
A = [int(a) for a in input().split()]

A.sort()

def f(n): #aiが必要か不必要か判定
    if A[n] >= K:
        return True
    if n == 0:
        L = A[n+1:]
    elif n == N-1:
        L = A[:n]
    else:
        L = A[:n] + A[n+1:]
    
    dp0 = [0]*K
    dp0[0] = 1
    dp1 = [0]*K
    for i in range(N-1):
        for j in range(K):
            if i%2 == 0:
                if j < L[i]:
                    dp1[j] = dp0[j]
                    continue
                dp1[j] = dp0[j] | dp0[j-L[i]]
            else:
                if j < L[i]:
                    dp0[j] = dp1[j]
                    continue
                dp0[j] = dp1[j] | dp1[j-L[i]]
        
    res = False
    if N%2 == 0:
        for j in range(K-A[n], K):
            if dp1[j]:
                res = True
                break
    else:
        for j in range(K-A[n], K):
            if dp0[j]:
                res = True
                break
            
    return res

l = -1
r = N
while r-l > 1:
    m = (l+r)//2
    if f(m):
        r = m
    else:
        l = m
        
print(r)

### FIXED CODE ###

N,K = map(int, input().split())
A = [int(a) for a in input().split()]

A.sort()
for i in range(N):
    if A[i] >= K:
        A = A[:i]
        break

N = len(A)

def f(n): #aiが必要か不必要か判定
    dp = [0]*K
    dp[0] = 1
    for i in range(N):
        if i == n:
            continue
        for j in range(K-1, A[i]-1, -1):
            dp[j] |= dp[j-A[i]]
            
    res = False
    for j in range(K-A[n], K):
        if dp[j]:
            res = True
            break
    return res

l = -1
r = N
while r-l > 1:
    m = (l+r)//2
    if f(m):
        r = m
    else:
        l = m
        
print(r)
### BUGGY CODE ###

from collections import deque

H, W = [int(item) for item in input().split()]
Ch, Cw = [int(item)-1 for item in input().split()]
Dh, Dw = [int(item)-1 for item in input().split()]
grid = [input() for _ in range(H)]
max_num = 10**6
fp = [[max_num for _ in range(W)] for _ in range(H)]

que = deque([[Ch, Cw, 0]])
fp[Ch][Cw] = 0

walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

while que:
    y, x, w_num = que.popleft()

    for dy, dx in walk:
        ny = y + dy
        nx = x + dx

        if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > w_num:
            que.appendleft([ny, nx, w_num])
            fp[ny][nx] = w_num

    for dy, dx in warp:
        ny = y + dy
        nx = x + dx
        nw = w_num +1

        if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > nw:
            que.append([ny, nx, nw])
            fp[ny][nx] = nw

if fp[Dh][Dw] != max_num:
    print(fp[Dh][Dw])
else:
    print(-1)


### FIXED CODE ###

def resolve():
    '''
    code here
    '''
    from collections import deque

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [input() for _ in range(H)]
    max_num = 10**6
    fp = [[max_num] * W for _ in range(H)]

    que = deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while que:
        y, x, w_num = que.popleft()

        for dy, dx in walk:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                que.appendleft([ny, nx, w_num])
                fp[ny][nx] = w_num

        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            nw = w_num +1

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > nw:
                que.append([ny, nx, nw])
                fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

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

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
cnt1 = [[0]*W for _ in range(H)]
for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      continue
    cnt1[i][j] = 1

for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      continue
    if j-1 >= 0:
      cnt1[i][j] += cnt1[i][j-1]
for i in range(H):
  for j in range(W-1, -1, -1):
    if S[i][j] == '#':
      continue
    if j+1 <= W-1:
      cnt1[i][j] = max(cnt1[i][j], cnt1[i][j+1])

S2 = [[0]*H for _ in range(W)]
for i in range(H):
  for j in range(W):
    S2[j][i] = S[i][j]

cnt2 = [[0]*H for _ in range(W)]
for i in range(W):
  for j in range(H):
    if S2[i][j] == '#':
      continue
    cnt2[i][j] = 1

for i in range(W):
  for j in range(H):
    if S2[i][j] == '#':
      continue
    if j-1 >= 0:
      cnt2[i][j] += cnt2[i][j-1]
for i in range(W):
  for j in range(H-1, -1, -1):
    if S2[i][j] == '#':
      continue
    if j+1 <= H-1:
      cnt2[i][j] = max(cnt2[i][j], cnt2[i][j+1])


ans = 0
for i in range(H):
  for j in range(W):
    ans = max(ans, cnt1[i][j]+cnt2[j][i]-1)
print(ans)


### FIXED CODE ###

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

L = [[0 for _ in range(w)] for _ in range(h)]
R = [[0 for _ in range(w)] for _ in range(h)]
D = [[0 for _ in range(w)] for _ in range(h)]
U = [[0 for _ in range(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] = 1
      else:
        L[i][j] = L[i][j-1]+1     
      if i == 0:
        D[i][j] = 1
      else:
        D[i][j] = D[i-1][j]+1
      if i == h-1:
        U[i][j] = 1
      else:
        U[i][j] = U[i+1][j]+1
  for j in range(w-1, -1, -1):
    if s[i][j] == '.':
      if j == w-1:
        R[i][j] = 1
      else:
        R[i][j] = R[i][j+1]+1

for i in range(h-1, -1, -1):
  for j in range(w):
    if s[i][j] == '.':
      if i == h-1:
        U[i][j] = 1
      else:
        U[i][j] = U[i+1][j]+1
ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans, L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)

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

from sys import stdin
from itertools import combinations_with_replacement

x = int(stdin.readline().rstrip())

li = [0,1,2,3,4,5]

kosuu = x//100
amari = x%100

lin = list(combinations_with_replacement(li, kosuu))

for i in lin:
    if sum(i) == amari:
        print(1)
        exit()

print(0)

### FIXED CODE ###

from sys import stdin
from itertools import combinations_with_replacement

x = int(stdin.readline().rstrip())

li = [0,1,2,3,4,5]

kosuu = x//100
amari = x%100

if amari > kosuu*5:
    print(0)
else:
    print(1)