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

from collections import deque

H,W=map(int,input().split())
CH,CW=map(int,input().split())
DH,DW=map(int,input().split())

S=[list(input()) for _ in range(H)]
MAX_COST = 10 ** 9
Cost=[ [ MAX_COST for _ in range(W)] for _ in range(H)]

# print(S)

ans = -1

deq = deque()

deq.append((CH-1,CW-1,0))
Cost[CH-1][CW-1] = 0;

# used = set()
five_five = [ (i,j) for i in range(-2,3,1) for j in range(-2,3,1) ]
# print(five_five)

while 0 < len(deq):
	h,w,c=deq.popleft()
	# print(h,w,c)
	for i,j in five_five:
		# print(i,j)
		if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
			if S[h+i][w+j] == '.':
				if (j == 0 and (i==1 or i==-1)) or (i==0 and (j==1 or j==-1)):
					if c < Cost[h+i][w+j]:
						Cost[h+i][w+j] = c
						deq.appendleft((h+i,w+j,Cost[h+i][w+j]))
				elif c + 1 < Cost[h+i][w+j]:
					Cost[h+i][w+j] = c + 1
					deq.append((h+i,w+j,Cost[h+i][w+j]))
					# print("updr ", h+i,w+j,Cost[h+i][w+j])

if Cost[DH-1][DW-1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH-1][DW-1])

### FIXED CODE ###

from collections import deque

H,W=map(int,input().split())
CH,CW=map(int,input().split())
DH,DW=map(int,input().split())

S=[list(input()) for _ in range(H)]
MAX_COST = 10 ** 9
Cost=[ [ MAX_COST for _ in range(W)] for _ in range(H)]

# print(S)

ans = -1

deq = deque()

deq.append((CH-1,CW-1,0))
Cost[CH-1][CW-1] = 0;

walk=[(1,0),(0,1),(-1,0),(0,-1)]

# used = set()

while 0 < len(deq):
	h,w,c=deq.popleft()
	# print(h,w,c)
	for i,j in walk:
		if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
			if S[h+i][w+j] == '.' and c < Cost[h+i][w+j]:
				Cost[h+i][w+j] = c
				# print("updl ", i,j,h+i,w+j,c)
				deq.appendleft((h+i,w+j,Cost[h+i][w+j]))
	for i in range(-2,3,1):
		for j in range(-2,3,1):
			# print(i,j)
			if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
				if S[h+i][w+j] == '.':
					if c + 1 < Cost[h+i][w+j]:
						Cost[h+i][w+j] = c + 1
						deq.append((h+i,w+j,Cost[h+i][w+j]))
						# print("updr ", h+i,w+j,Cost[h+i][w+j])

if Cost[DH-1][DW-1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH-1][DW-1])
### BUGGY CODE ###

n = int(input())
s = ""
for _ in range(n):
    s += input()+" "
ls = s.split()
counter = 0
res = []
for x in ls:
    if ls.count(x) > counter:
        counter = ls.count(x)
for x in set(ls):
    if ls.count(x) == counter:
        res.append(x)
r = sorted(res)
print("\n".join(r))

### FIXED CODE ###

from collections import Counter
n = int(input())
ls = []
for _ in range(n):
    ls.append(input())
res = []
counter = Counter(ls).most_common()
for x in counter:
    if x[1] == counter[0][1]:
        res.append(x[0])
print("\n".join(sorted(res)))
### BUGGY CODE ###

n=int(input())
a=[int(x) for x in input().split()]
from collections import defaultdict
d=defaultdict(int)
for ai in a:
    for i in range(1, int(ai**0.5)+1):
        if ai % i == 0:
            d[i]+=1
            if i != ai // i:
                d[ai//i]+=1
print(max([x for x in d.keys() if d[x]==n or d[x]==n-1]))

### FIXED CODE ###

n=int(input())
a=[int(x) for x in input().split()]
anses=set()
for i in [0,1]:
    for j in range(1, int(a[i]**0.5)+1):
        if a[i] % j == 0:
            anses.add(j)
            if j != a[i] // j:
                anses.add(a[i] // j)
anses=sorted(anses,reverse=True)
for ans in anses:
    solvenum=0
    for j in a:
        if j%ans==0:
            solvenum+=1
    if solvenum==n or solvenum==n-1:
        print(ans)
        break
### BUGGY CODE ###

n = input().split()
a = list(map(int, input().split()))
b = 0
c = []
count = 0


while(True):
    T = False
    for i in range(len(a)):
        if a[i]%2 != 0 :
            T = True 
            
    if T:
        break

    for i in range(len(a)):
        b = a[i] / 2
        c.append(b)
        
    a = c
    count+=1


print(count)


### FIXED CODE ###

n = input().split()
a = list(map(int, input().split() ))
count = 0

while(True):
    T = False
    for i in range(len(a)):
        if a[i]%2 != 0:
            T=True
        else:
            a[i] = a[i] / 2

    if T:
        break

    count+=1

print(count)
### BUGGY CODE ###

N=int(input())
S=input()
V=[]
for i in range(10):
    for j in range(10):
        for k in range(10):
            s=""
            a=str(i)
            b=str(j)
            c=str(k)
            s=a+b+c
            V.append(s)
ans=0
for i in range(len(V)):
    v=V[i]
    flag1=False
    flag2=False
    flag3=False
    for j in range(N):
        if not flag1:
            if S[j]==v[0]:
                flag1=True
                continue
        if not flag2:
            if flag1:
                if S[j]==v[1]:
                    flag2=True
                    continue
        if flag2:
            if S[j]==v[2]:
                flag3=True
        if flag3:
            ans+=1
            break
print(ans)

### FIXED CODE ###

N=int(input())
S=input()
V=[]
for i in range(10):
    for j in range(10):
        for k in range(10):
            s=""
            a=str(i)
            b=str(j)
            c=str(k)
            s=a+b+c
            V.append(s)
ans=0
for i in range(len(V)):
    v=V[i]
    flag1=False
    flag2=False
    flag3=False
    for j in range(N):
        if not flag1:
            if S[j]==v[0]:
                flag1=True
                continue
        if not flag2:
            if flag1:
                if S[j]==v[1]:
                    flag2=True
                    continue
        if flag2:
            if S[j]==v[2]:
                flag3=True
        if flag3:
            ans+=1
            break
print(ans)
### BUGGY CODE ###

from math import factorial

num=int(input())

#for i in range(num):
#    str=input()
#    str=''.join(sorted(str))
#    str = ''.join(sorted(input()))
#    stl.append(str)
stl =[(''.join(sorted(input()))) for i in range(num)]

duplicate=[x for x in set(stl) if stl.count(x) > 1]
count=0

for dup in duplicate:
    count += factorial(stl.count(dup)) // 2 // factorial(stl.count(dup) - 2)
    
print(count)

### FIXED CODE ###

num=int(input())
stl =[''.join(sorted(input())) for i in range(num)]

#duplicate=[x for x in set(stl) if stl.count(x) > 1]

t = {}
for i in range(num):
  if stl[i] in t:
    t[stl[i]] += 1
  else:
    t[stl[i]] = 1
print(sum(t[k] * (t[k] -1) // 2 for k in t))
### BUGGY CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    # d %= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d %= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]
def t(s):
  return [[s[i][j] for i in range(len(s))] for j in range(len(s[0]))]
def calc(s):
  res = []
  for v in s:
    v.append('-')
    tmp = []
    nc = ''
    nn = 0
    for c in v:
      if nc == '':
        nc = c
        nn += 1
        continue
      if nc == c:
        nn += 1
        continue
      else:
        if nc == '#':
          tmp = tmp + [0 for _ in range(nn)]
        else:
          tmp = tmp + [nn for _ in range(nn)]
        nc = c
        nn = 1
    res.append(tmp)
  return res

tate = t(calc(t(S)))
yoko = calc(S)
print(max([tate[i][j] + yoko[i][j] for i in range(h) for j in range(w) if tate[i][j] * yoko[i][j] != 0])-1)

### FIXED CODE ###

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

def calc(s):
    res = []
    for v in s:
        v = v + '-'
        tmp = []
        nc = v[0]
        nn = 0
        for c in v:
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp.extend([0 for _ in range(nn)])
                else:
                    tmp.extend( [nn for _ in range(nn)])
                nc = c
                nn = 1
        res.append(tmp)
    return res

def calc2(s):
    res = []
    for j in range(w):
        tmp = []
        nc = s[0][j]
        nn = 0
        for i in range(h):
            c = s[i][j]
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp.extend([0 for _ in range(nn)])
                else:
                    tmp.extend( [nn for _ in range(nn)])
                nc = c
                nn = 1
        if nc == '#':
            tmp.extend([0 for _ in range(nn)])
        else:
            tmp.extend( [nn for _ in range(nn)])
        res.append(tmp)
    return res

tate = calc2(S)
yoko = calc(S)

print(max([tate[j][i] + yoko[i][j] for i in range(h) for j in range(w) if tate[j][i] * yoko[i][j] != 0]) - 1)
### BUGGY CODE ###

from collections import deque
from typing import List


def main():
    h, w = map(int, input().split())
    g = []
    for _ in range(h):
        r = list(input())
        g.append(r)
    print(mm(h, w, g))


def mm(h: int, w: int, g: List[List[str]]) -> int:
    ret = 0
    for i in range(h):
        for j in range(w):
            if (g[i][j] == '#'):
                continue
            q = deque([(i, j, 0)])
            v = set()
            while q:
                ii, jj, cnt = q.popleft()
                v.add((ii, jj))
                ret = max(ret, cnt)
                # ↓
                if ii < h - 1 and g[ii + 1][jj] == '.' and (ii + 1, jj) not in v:
                    q.append((ii + 1, jj, cnt + 1))
                # →
                if jj < w - 1 and g[ii][jj + 1] == '.' and (ii, jj + 1) not in v:
                    q.append((ii, jj + 1, cnt + 1))
                # ↑
                if ii > 0 and g[ii - 1][jj] == '.' and (ii - 1, jj) not in v:
                    q.append((ii - 1, jj, cnt + 1))
                # ←
                if jj > 0 and g[ii][jj - 1] == '.' and (ii, jj - 1) not in v:
                    q.append((ii, jj - 1, cnt + 1))
    return ret


if __name__ == '__main__':
    main()


### FIXED CODE ###

import queue


def get_longest(s_tmx, i, j, h, w):
    q = queue.Queue()
    q.put((i, j))
    dist_mtx = [[-1] * w for a in range(h)]
    dist_mtx[i][j] = 0
    while not q.empty():
        pnt = q.get()
        y = pnt[0]
        x = pnt[1]
        if x - 1 >= 0 and dist_mtx[y][x-1] == -1 and s_mtx[y][x-1] == 1:
            dist_mtx[y][x-1] = dist_mtx[y][x] + 1
            q.put((y, x-1))
        if y - 1 >= 0 and dist_mtx[y-1][x] == -1 and s_mtx[y-1][x] == 1:
            dist_mtx[y-1][x] = dist_mtx[y][x] + 1
            q.put((y-1, x))
        if x < w - 1 and dist_mtx[y][x+1] == -1 and s_mtx[y][x+1] == 1:
            dist_mtx[y][x+1] = dist_mtx[y][x] + 1
            q.put((y, x+1))
        if y < h - 1 and dist_mtx[y+1][x] == -1 and s_mtx[y+1][x] == 1:
            dist_mtx[y+1][x] = dist_mtx[y][x] + 1
            q.put((y+1, x))
    ret = 0
    for item in dist_mtx:
        for item_item in item:
            if item_item > ret:
                ret = item_item
    return ret


h, w = map(int, input().split())
s_mtx = []

for i in range(h):
    s_list = [0] * w
    tmp = input()
    for j in range(len(tmp)):
        if tmp[j] == ".":
            s_list[j] = 1
        else:
            s_list[j] = 0
    s_mtx.append(s_list)

ret = 0

for i in range(h):
    for j in range(w):
        if s_mtx[i][j] == 1:
            tmp = get_longest(s_mtx, i, j, h, w)
            if tmp > ret:
                ret = tmp

print(ret)
### BUGGY CODE ###

N = int(input())
D = list(map(int, input().split()))
M = int(input())
T = list(map(int, input().split()))
i = 0

for t in set(T):
    if D.count(t) < T.count(t):
        print('NO')
        exit()
        
print('YES')


### FIXED CODE ###

N = int(input())
D = sorted(map(int, input().split()))
M = int(input())
T = sorted(map(int, input().split()))
i = 0
for t in T:
    while D[i] < t:
        i += 1
    if D[i] == t:
        i += 1
    else:
        print('NO')
        exit()
print('YES')
### BUGGY CODE ###

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

for i in range(1,N+1):
  Ai = A.count(i)
  print(Ai)

### FIXED CODE ###

from collections import Counter

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

for i in range(1,N+1):
  print(A[i])
### BUGGY CODE ###

import collections
import sys
N=int(input())
A=list(map(int, input().split()))
A_dict=collections.Counter(A)
ANS=1

if 0 in A_dict.keys():
    print("0")
    sys.exit()
for i in A_dict.keys():
    ANS=ANS*(i**A_dict[i])

if ANS>10**18:
    print(-1)
else:
    print(ANS)

### FIXED CODE ###

import collections
import sys

N=int(input())
A=list(map(int, input().split()))
A_dict=collections.Counter(A)
ANS=1
if 0 in A_dict.keys():
    print("0")
    sys.exit()
    
for key, value in A_dict.items():
    ANS=ANS*(key**value)
    if ANS>10**18:
        print(-1)
        sys.exit()

print(ANS)
### BUGGY CODE ###

n = int(raw_input())
a = map(int, raw_input().split())
for i in range(len(a)):
  a[i] -= (i+1)
min_total = sum([abs(t) for t in a])
for item in a:
  total = sum([abs(t-item) for t in a])
  if total < min_total:
    min_total = total

print(min_total)


### FIXED CODE ###

n = int(raw_input())
a = map(int, raw_input().split())
for i in range(len(a)):
  a[i] -= (i+1)


b = sorted(a)
i = n // 2
what = b[i]
print(sum([abs(t - what) for t in b]))
### BUGGY CODE ###

N = int(input())
p_list  = list(map(int,input().strip().split(" ")))

c = 1

for i in range(1, N):
    p_list_min = min(p_list[:i])
    if p_list[i] <= p_list_min:
        c += 1
        
print(c)


### FIXED CODE ###

N = int(input())
p_list  = list(map(int,input().strip().split(" ")))

ans = 1
mi = p_list[0]

for i in range(1, N):
    if mi >= p_list[i]:
        ans += 1
        mi = p_list[i]
        
print(ans)
### BUGGY CODE ###

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

def check(L):
  for i in range(N - (L * 2) + 1):
    if S.count(S[i:i+L]) >= 2:                                                      return True
  return False

left = 0
right = N // 2 + 1
while right - left > 1:
  mid = left + (right - left) // 2
  if check(mid):
    left = mid
  else:
    right = mid
print(left)

### FIXED CODE ###

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

def check(L):
  a = set()
  for i in range(N - (L * 2) + 1):
    a.add(S[i:i+L])
    if S[i+L:i+L+L] in a:
      return True
  return False

left = 0
right = N // 2 + 1
while right - left > 1:
  mid = left + (right - left) // 2
  if check(mid):
    left = mid
  else:
    right = mid
print(left)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
count = 0
for i in range(len(a)):
    ans = 1
    for i in range(len(a)):
        if a[i] != i + 1:
            ans = 0
            count += 1
            del a[i]
            break
    if len(a) == 0:
        break
    if ans == 1:
        break
if ans == 1:
    print(count)
else:
    print(-1)

### FIXED CODE ###

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

s = input()
K = int(input())

n = len(s)
sub = []
for i in range(n):
    for j in range(i+1, n+1):
        if s[i:j] not in sub:
            sub.append(s[i:j])
sub.sort()
print(sub[K-1])

### FIXED CODE ###

s = input()
K = int(input())

n = len(s)

sub = []
alp = [chr(i) for i in range(ord('a'), ord('z')+1)]

for a in alp:
    if a in s:
        start = -1
        while True:
            start = s.find(a, start+1)
            if start==-1:
                break
            for j in range(start+1, min(start+K+1,n+1)):
                if s[start:j] not in sub:
                    sub.append(s[start:j])
    if len(sub) > K:
        break

sub.sort()
print(sub[K-1])
### BUGGY CODE ###

import math
def dis(x1,y1,r1,x2,y2,r2):
     return max(math.sqrt(abs(x1-x2)**2+abs(y1-y2)**2)-r1-r2,0)

import heapq
def dijkstra(s,c,n):
    d=[10**10]*n
    d[s]=0
    pq=[]
    heapq.heappush(pq,[0,s])
    while len(pq)!=0:
        t,u=heapq.heappop(pq)
        if d[u]<t:
            continue
        for v in xrange(n):
            if u==v:continue
            if d[u]+c[u][v]<d[v]:
                d[v]=d[u]+c[u][v]
                heapq.heappush(pq,[d[v],v])
    return d
    
def main():
    xs,ys,xt,yt=map(int,raw_input().split())
    n=int(raw_input())
    c=[[xs,ys,0]]+[map(int,raw_input().split()) for _ in xrange(n)]+[[xt,yt,0]]
    dist=[[10**10]*(n+2) for _ in xrange(n+2)]
    for i in xrange(n+2):
        for j in xrange(n+2):
            if i==j:continue
            dist[i][j]=min(dist[i][j],dis(c[i][0],c[i][1],c[i][2],c[j][0],c[j][1],c[j][2]))
            dist[j][i]=dist[i][j]
    ans=dijkstra(0,dist,n+2)
    print(ans[n+1])
main()


### FIXED CODE ###

import math
import heapq
def dijkstra(s,m,n):
    visited=[0]*n
    d=[float("inf")]*n
    d[s]=0
    while True:
        mincost=float("inf")
        for i in xrange(n):
            if visited[i]!=2 and d[i]<mincost:
                mincost=d[i]
                u=i
        if mincost==float("inf"):
            break
        visited[u]=2
        for v in xrange(n):
            if visited[v]!=2:
                if d[u]+m[u][v]<d[v]:
                    d[v]=d[u]+m[u][v]
                    visited[v]=1
    return d

def main():
    xs,ys,xt,yt=map(int,raw_input().split())
    n=int(raw_input())
    c=[[xs,ys,0]]+[map(int,raw_input().split()) for _ in xrange(n)]+[[xt,yt,0]]
    dist=[[float("inf")]*(n+2) for _ in xrange(n+2)]
    for i in xrange(n+2):
        for j in xrange(n+2):
            if i==j:continue
            dist[i][j]=min(dist[i][j],dist[j][i],max(math.sqrt(abs(c[i][0]-c[j][0])**2+abs(c[i][1]-c[j][1])**2)-c[i][2]-c[j][2],0))
            dist[j][i]=dist[i][j]
    ans=dijkstra(0,dist,n+2)
    print(ans[n+1])
main()
### BUGGY CODE ###

from fractions import gcd

import sys
input = sys.stdin.readline


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

    B = []
    C = []

    ok = True
    a = A[0]
    c = 0
    while a%2 == 0:
        a //= 2
        c += 1
    
    p = 2**c

    for a in A:
        if a % p == 0 and a % (2*p) != 0:
            B.append(a//p)
        else:
            ok = False
            break
    if not ok:
        print(0)
    else:
        g = 1
        for b in B:
            l = gcd(g, b)
            g = g*b//l
        p = g*2**(c-1)
        ans = (M+p)//(2*p)
        print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from fractions import gcd

import sys
input = sys.stdin.readline


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

    B = []

    ok = True
    a = A[0]
    c = 0
    while a%2 == 0:
        a //= 2
        c += 1
    
    p = 2**c

    for a in A:
        if a % p == 0 and a % (2*p) != 0:
            B.append(a//p)
        else:
            ok = False
            break
    if not ok:
        print(0)
    else:
        B.sort()
        g = 1
        for b in B:
            l = gcd(b, g)
            g = g*b//l
            if g > M:
                ok = False
                break
        if not ok:
            print(0)
        else:
            p = g*2**(c-1)
            ans = (M+p)//(2*p)
            print(ans)


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

N = int(input())
A = list(map(int,input().split()))
K = 0
for i in range(N):
  while True:
    if(A[i]%2==0):
      A[i]==A[i]//2
      K+=1
    else:
      break
print(K)

### FIXED CODE ###

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

for i in range(N):
    while A[i] % 2 == 0:
        A[i] = A[i] // 2
        cnt += 1

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

n = int(input())
A = list(map(int, input().split()))
amax =max(A)
amin =min(A)
ans = 0
for i in range(amin - 1, amax + 2):
    ans = max(ans, A.count(i - 1) + A.count(i) + A.count(i + 1))
print(ans)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
lst =[0] * (10 ** 5 +10)
for i in A:
    if i > 0:
        lst[i - 1] += 1
    lst[i] += 1
    lst[i + 1] += 1
print(max(lst))
### BUGGY CODE ###

h, w = map(int, input().split())
s = [input() for _ in range(h)]
leftbeam = [[0 for _ in range(w)] for _ in range(h)]
rightbeam = [[0 for _ in range(w)] for _ in range(h)]
downbeam = [[0 for _ in range(w)] for _ in range(h)]
upbeam = [[0 for _ in range(w)] for _ in range(h)]

def can_light(y, x):
    return (0 <= y < h) and (0 <= x < w) and s[y][x] == '.'

for y in range(h):
    beamlen = 0
    for x in range(w):
        if can_light(y, x):
            beamlen += 1
        else:
            beamlen = 0
        leftbeam[y][x] = beamlen

for y in range(h):
    beamlen = 0
    for x in range(w):
        if can_light(y, w - x - 1):
            beamlen += 1
        else:
            beamlen = 0
        rightbeam[y][w - x - 1] = beamlen


for x in range(w):
    beamlen = 0
    for y in range(h):
        if can_light(y, x):
            beamlen += 1
        else:
            beamlen = 0
        downbeam[y][x] = beamlen

for x in range(w):
    beamlen = 0
    for y in range(h):
        if can_light(h - y - 1, x):
            beamlen += 1
        else:
            beamlen = 0
        upbeam[h - y - 1][x] = beamlen

ans = 0
for y in range(h):
    for x in range(w):
        ans = max(ans, leftbeam[y][x] + rightbeam[y][x]
                     + downbeam[y][x] + upbeam[y][x] - 3)

print(ans)

### FIXED CODE ###

h, w = map(int, input().split())
s = [input() for _ in range(h)]
leftbeam = [[0 for _ in range(w)] for _ in range(h)]
rightbeam = [[0 for _ in range(w)] for _ in range(h)]
downbeam = [[0 for _ in range(w)] for _ in range(h)]
upbeam = [[0 for _ in range(w)] for _ in range(h)]

def can_light(y, x):
    return (0 <= y < h) and (0 <= x < w) and s[y][x] == '.'

for y in range(h):
    beamlen = 0
    for x in range(w):
        if can_light(y, x):
            beamlen += 1
        else:
            beamlen = 0
        leftbeam[y][x] = beamlen

for y in range(h):
    beamlen = 0
    for x in range(w):
        if can_light(y, w - x - 1):
            beamlen += 1
        else:
            beamlen = 0
        rightbeam[y][w - x - 1] = beamlen


for x in range(w):
    beamlen = 0
    for y in range(h):
        if can_light(y, x):
            beamlen += 1
        else:
            beamlen = 0
        downbeam[y][x] = beamlen

for x in range(w):
    beamlen = 0
    for y in range(h):
        if can_light(h - y - 1, x):
            beamlen += 1
        else:
            beamlen = 0
        upbeam[h - y - 1][x] = beamlen

ans = 0
for y in range(h):
    for x in range(w):
        ans = max(ans, leftbeam[y][x] + rightbeam[y][x]
                     + downbeam[y][x] + upbeam[y][x] - 3)

print(ans)