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

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import deque
import sys
def main(H, W, C, D, S):
    INF = 10**6
    dist = [[INF] * W for _ in range(H)]
    dist[D[0]][D[1]] = 0
    q = deque([D])
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W:
                if S[ni][nj] == '.':
                    if dist[ni][nj] > d:
                        dist[ni][nj] = d
                        q.append((ni, nj))
                else:
                    ni, nj = ni + di, nj + dj
                    if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
                        if dist[ni][nj] > d + 1:
                            dist[ni][nj] = d + 1
                            q.append((ni, nj))
        for di, dj in [(-2, -2), (-2, 1), (1, -2), (1, 1)]:
            for ddi, ddj in [(0, 0), (0, 1), (1, 0), (1, 1)]:
                ni, nj = i + di + ddi, j + dj + ddj
                if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
                    if dist[ni][nj] > d + 1:
                        dist[ni][nj] = d + 1
                        q.append((ni, nj))

    ans = dist[C[0]][C[1]]
    print(ans if ans < INF else -1)


if __name__ == '__main__':
    input = sys.stdin.readline
    H, W = map(int, input().split())
    C = tuple(map(lambda x: int(x) - 1, input().split()))
    D = tuple(map(lambda x: int(x) - 1, input().split()))
    S = [list(input().rstrip()) for _ in range(H)]
    main(H, W, C, D, S)


### FIXED CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import deque
import sys
def main(H, W, C, D, S):
    INF = 10**6
    dist = [[INF] * W for _ in range(H)]
    di, dj = D
    dist[di][dj] = 0
    q = deque([(di, dj, 0)])
    while q:
        i, j, d = q.popleft()
        if d > dist[i][j]: continue
        for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
                if dist[ni][nj] > d:
                    dist[ni][nj] = d
                    q.appendleft((ni, nj, d))
        for ni in range(i - 2, i + 2 + 1, 1):
            if not(0 <= ni < H): continue
            dni = dist[ni]
            sni = S[ni]
            for nj in range(j - 2, j + 2 + 1, 1):
                if 0 <= nj < W and sni[nj] == '.':
                    if dni[nj] > d + 1:
                        dni[nj] = d + 1
                        q.append((ni, nj, d + 1))

    ans = dist[C[0]][C[1]]
    print(ans if ans < INF else -1)


if __name__ == '__main__':
    input = sys.stdin.readline
    H, W = map(int, input().split())
    C = tuple(map(lambda x: int(x) - 1, input().split()))
    D = tuple(map(lambda x: int(x) - 1, input().split()))
    S = [list(input().rstrip()) for _ in range(H)]
    main(H, W, C, D, S)
### BUGGY CODE ###

import collections

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

q = collections.deque()
for i in range(m):
    if s[i][0] == 1:
        q.append(s[i][1])

for i in s:
    for j in q:
        if j in i and n in i:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")




### FIXED CODE ###

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

s1 = set()
s2 = set()
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        s1.add(b)
    elif b == 1:
        s1.add(a)
    elif a == n:
        s2.add(b)
    elif b == n:
        s2.add(a)

if s1.isdisjoint(s2):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")
### BUGGY CODE ###

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

    
from math import gcd

def lcm(x, y):
    return (x * y) // gcd(x, y)

g = a[0]
l = 1
f = True
for i in range(n):
    if gcd(a[i],l)!=1:
        f = False
    g = gcd(g,a[i])
    l = lcm(l,a[i])

if f:
    print('pairwise coprime')
elif g==1:
    print('setwise coprime')
else:
    print('not coprime')

### FIXED CODE ###

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

from math import gcd
g = a[0]
for i in range(n):
    g = gcd(g,a[i])

if g!=1:
    print('not coprime')
    exit()

f = True
l = set()
for i in a:
    for j in range(2,int(i**0.5)+1):
        if i%j==0:
            if i in l:
                f = False
                break
            l.add(i)
        while i%j==0:
            i = i//j
        if i<2:
            break
    if i>1:
        if i in l:
            f = False
            break
        l.add(i)
        
if f:
    print('pairwise coprime')
else:
    print('setwise coprime')
### BUGGY CODE ###

'''
N Q
s
t_1 d_1
\vdots
t_{Q} d_Q
'''
N, Q = map(int, input().split(' '))
s = input()
tile, dir = [], []
for _ in range(Q):
  pre, suff = input().split(' ')
  tile.append(pre)
  dir.append(suff)
  
def move(golem, i, d):
  if golem[i] == 0:  # No golem
    return golem
  elif golem[i] > 0:
    if d == 'L':
      if i > 0:
        golem[i-1], golem[i] = golem[i-1] + golem[i], 0
      elif i == 0:
        golem[i] = 0
    elif d == 'R':
      if i < N-1:
        golem[i], golem[i+1] = 0, golem[i] + golem[i+1]
      elif i == N-1:
        golem[i] = 0
  return golem
  
def move_R(golem, i):
  if golem[i] == 0:
    return golem
  if golem[i] > 0:
    golem[i] -= 1
  if i != N-1:
    golem[i+1] += 1
  return golem

def move_golem(golem, s, t, d):
  indexes = [i for i, x in enumerate(s) if x == t]
  for i in indexes:
    golem = move(golem, i, d)
  return golem
    
  
golem = [1]*N
for t, d in zip(tile, dir):
  golem = move_golem(golem, s, t, d)
print(sum(golem))

### FIXED CODE ###

N, Q = map(int, input().split(' '))
S = '0' + input() + '0'
A = [list(input().split(' ')) for _ in range(Q)]
l = 0
r = N+1
for i in range(Q-1, -1, -1):
  t, d = A[i]
  if t == S[l] and d == 'R':
    l -= 1
  elif t == S[l+1] and d == 'L':
    l += 1
    
  if t == S[r] and d == 'L':
    r += 1
  elif t == S[r-1] and d == 'R':
    r -= 1
print(max(0, r-l-1))
### BUGGY CODE ###

D, G = list(map(int, input().split(' ')))
p_list = list()
c_list = list()
for _ in range(D):
    p, c = list(map(int, input().split(' ')))
    p_list.append(p)
    c_list.append(c)
num_prob_list = [0] * D
min_prob_num_sum = sum(p_list)


def dfs(prob_index=-1, prob_num=0, current_score=0):
    """
    Returns whether score >= G.
    """
    global min_prob_num_sum
    if prob_index >= 0:
        num_prob_list[prob_index] = prob_num
        current_score += 100 * (prob_index + 1) * prob_num
        if prob_num == p_list[prob_index]:
            current_score += c_list[prob_index]
        if current_score >= G:
            prob_num_sum = sum(num_prob_list[:(prob_index + 1)])
            if min_prob_num_sum > prob_num_sum:
                min_prob_num_sum = prob_num_sum
                # print(num_prob_list[:(prob_index + 1)])
                # print(current_score)
            return True
    next_prob_index = prob_index + 1
    if next_prob_index > D - 1:
        return False
    for next_prob_num in range(p_list[next_prob_index] + 1):
        if dfs(next_prob_index, next_prob_num, current_score):
            break


dfs()
print(min_prob_num_sum)

### FIXED CODE ###

import itertools
import math
D, G = list(map(int, input().split(' ')))
p_list = list()
c_list = list()
for _ in range(D):
    p, c = list(map(int, input().split(' ')))
    p_list.append(p)
    c_list.append(c)
ans = sum(p_list)
pattern_list = itertools.product([0, 1], repeat=D)
for pattern in pattern_list:
    score = 0
    prob_num = 0
    # Solve all problems with bit `1`
    score += sum([bit * (100 * (index + 1) * p_list[index] + c_list[index]) for index, bit in enumerate(pattern)])
    prob_num += sum([bit * p_list[index] for index, bit in enumerate(pattern)])
    # Solve problems partially with bit `0'
    if score < G:
        for index in range(D - 1, -1, -1):
            if pattern[index] == 1:
                # skip because these cases are already counted
                continue
            required_num = math.ceil((G - score) / (100 * (index + 1)))
            sol_num = min([p_list[index] - 1, required_num])
            score += 100 * (index + 1) * sol_num
            prob_num += sol_num
            if score >= G:
                break
    # update answer
    if score >= G:
        ans = min([ans, prob_num])
print(ans)
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    #L = [0] * M
    #R = [0] * M
    
    for i in range(M):
        L, R = map(int, input().split())
        A = [j for j in range(L,R+1)]
        if i == 0:
            tmp = set(A)
            continue
        set_A = set(A)
        tmp = set(list(set_A.intersection(tmp)))
    
    print(len(tmp))



main()

### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    
    left = 0
    right = float('inf')
    
    for i in range(M):
        L, R = map(int, input().split())
        left = max(left, L)
        right = min(right, R)
    
    if left <= right:
        print(right - left + 1)
    else:
        print(0)

main()
### BUGGY CODE ###

from collections import deque

S = list(input())

Q = int(input())

cnt = 0
for i in range(Q):
    l = list(map(str,input().split()))
    if int(l[0]) == 1:
        cnt += 1
    else:
        if int(l[1]) == 1:
            if cnt % 2 == 1:
                S.append(l[2])
            else:
                S.insert(0,l[2])
        else:
            if cnt % 2 == 1:
                S.insert(0,l[2])
            else:
                S.append(l[2])

if cnt % 2 == 1:
    S = S[::-1]
print(''.join(S))

### FIXED CODE ###

from collections import deque

S = deque(list(input()))

Q = int(input())

cnt = 0
for i in range(Q):
    l = list(map(str,input().split()))
    if int(l[0]) == 1:
        cnt += 1
    else:
        if int(l[1]) == 1:
            if cnt % 2 == 1:
                S.append(l[2])
            else:
                S.appendleft(l[2])
        else:
            if cnt % 2 == 1:
                S.appendleft(l[2])
            else:
                S.append(l[2])

if cnt % 2 == 1:
    S = list(S)[::-1]
print(''.join(S))
### BUGGY CODE ###

import sys
import itertools
readline = sys.stdin.buffer.readline

n,a = map(int,readline().split())
lst1 = list(map(int,readline().split()))

dig = n #桁数
bit_mask = list(itertools.product([0,1],repeat=dig))
ans = 0
for i in bit_mask:
    res = 0
    num = 0
    for j,k in enumerate(i):
        if k == 1:
            res += lst1[j]
            num += 1
    try:
        if res/num == a:
            ans += 1
    except:
        pass

print(ans)

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,a = map(int,readline().split())
lst1 = list(map(int,readline().split()))

import numpy as np

dp = np.zeros((n+1,3000),dtype=np.int64) # 枚数、目標数ごとに場合の数
dp[0,0] = 1

for x in lst1:
  dp[1:,x:] += dp[:-1,:-x].copy()
  
ans = 0
for i in range(1,n+1):
  ans += dp[i,i*a]
  
print(ans)
### BUGGY CODE ###

n=int(input())
mul=1
limit=1000000000000000000
x=input().split()
for i in range (n):
    p=int(x[i])
    mul*=p
if(mul>limit):
  print(-1)
else:
  print(mul)

### FIXED CODE ###

n=int(input())
mul=1
limit=1000000000000000000
x=input().split()
for i in range (n):
    p=int(x[i])
    if(p==0):
        mul=0
        break
if(mul==0):
    print(mul)
else:
    for i in range (n):
        p=int(x[i])
        mul*=p
        if(mul>limit):
            break
    if(mul>limit):
      print(-1)
    else:
      print(mul)
### BUGGY CODE ###

s = list(map(lambda x: -1 if x == '?' else int(x), input()))

def test(c):
    # current point can be seen as xth smallest val, where x can be any value in [a, b] (subset of [0, c])
    # a <= b
    a, b = 0, c
    ok = True
    discrete = False # when True x = a, a+2, ..., b-2, b
    for si in s:
        if si == 1:
            if a == b == c:
                return False
            a += 1
            b += 1
            if b > c:
                b = c - 1 if discrete else c
        elif si == 0:
            if a == b == 0:
                return False
            a -= 1
            b -= 1
            if a < 0:
                a = 1 if discrete else 0
        else:
            if a == b == 0:
                a = b = 1
            elif a == b == c:
                a = b = c - 1
            elif a == b:
                discrete = True
                a -= 1
                b += 1
            else:
                a -= 1
                b += 1
                if a < 0:
                    a = 1 if discrete else 0
                if b > c:
                    b = c - 1 if discrete else c
    return True

l, r = 0, len(s)
while r - l > 1:
    c = (l + r) // 2
    if test(c):
        r = c
    else:
        l = c
print(r)


### FIXED CODE ###

from numba import njit
import numpy as np
s = np.array(list(map(lambda x: -1 if x == '?' else int(x), input())))
@njit
def test(c):
    # current point can be seen as xth smallest val, where x can be any value in [a, b] (subset of [0, c])
    # a <= b
    a, b = 0, c
    ok = True
    discrete = False # when True x = a, a+2, ..., b-2, b
    for si in s:
        if si == 1:
            if a == b == c:
                return False
            a += 1
            b += 1
            if b > c:
                b = c - 1 if discrete else c
        elif si == 0:
            if a == b == 0:
                return False
            a -= 1
            b -= 1
            if a < 0:
                a = 1 if discrete else 0
        else:
            if a == b == 0:
                a = b = 1
            elif a == b == c:
                a = b = c - 1
            elif a == b:
                discrete = True
                a -= 1
                b += 1
            else:
                a -= 1
                b += 1
                if a < 0:
                    a = 1 if discrete else 0
                if b > c:
                    b = c - 1 if discrete else c
    return True

l, r = 0, s.size
while r - l > 1:
    c = (l + r) // 2
    if test(c):
        r = c
    else:
        l = c
print(r)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
P = [int(x) for x in input().split()]

cnt = 0
for i in range(N):
    if P[i] <= min(P[:i+1]):
        cnt += 1
print(cnt)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
P = [int(x) for x in input().split()]
cnt = 1
minP = P[0]
for i in range(1, N):
    if minP >= P[i]:
        cnt += 1
        minP = P[i]

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

#n = int(input())
n,k = map(int,input().split())
#a_L = list(map(int,input().split()))

if abs(n-k) >= n:
    print(n)
    exit()

if n > k:
    tmp = n%k
    print(min(tmp,abs(tmp-k)))
    exit()

if n==k:
    print(0)
    exit()

if n == 0:
    print(0)

while True:
    pass
#print(0)


### FIXED CODE ###

#n = int(input())
n,k = map(int,input().split())
#a_L = list(map(int,input().split()))

if abs(n-k) >= n:
    print(n)
    exit()

if n > k:
    tmp = n%k
    print(min(tmp,abs(tmp-k)))
    exit()

if n==k:
    print(0)
    exit()

if n == 0:
    print(0)


print(abs(n-k))
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
for i in range(N) :
    k = A[i]
    del A[i]
    print(max(A))
    A.insert(i, k)


### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
A_sort = sorted(A)
for i in range(N) :
    if A[i] == A_sort[-1] :
        print(A_sort[-2])
    else :
        print(A_sort[-1])
### BUGGY CODE ###

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

used = [False] * N
def solve(index, cur_elem, cost, cur_min):
    #print(" " * index, cur_elem, cost, cur_min)
    for i in range(N):
        if used[i]:
            continue

        if (index - i) % 2 == 0:
            if A[i] >= cur_elem:
                new_cost = cost
                for j in range(i, N):
                    if used[j]:
                        new_cost += 1
                if new_cost < cur_min:
                    if index + 1 == N and new_cost < cur_min:
                        cur_min = new_cost
                    else:
                        used[i] = True
                        cur_min = min(cur_min, solve(index + 1, A[i], new_cost, cur_min))
                        used[i] = False
        else:
            if B[i] >= cur_elem:
                cost_delta = 0
                for j in range(i, N):
                    if used[j]:
                        cost_delta += 1
                new_cost = cost + cost_delta
                if new_cost < cur_min:
                    if index + 1 == N and new_cost < cur_min:
                        cur_min = new_cost
                    else:
                        used[i] = True
                        cur_min = min(cur_min, solve(index + 1, B[i], new_cost, cur_min))
                        used[i] = False
    return cur_min

ans = solve(0, -1, 0, 100000)
if ans == 100000:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

dp = [[100100] * (1 << N) for _ in range(N)]
for i in range(N):
    dp[i][1 << i] = 0
for mask in range(1, 1 << N):
    mask_pop = format(mask, 'b').count('1')
    for j in range(N):
        if (1 << j) & mask:
            if (j - mask_pop) % 2 == 1:
                cur_elem = A[j]
            else: 
                cur_elem = B[j]
            prev_mask = mask & ~(1 << j)
            cost_delta = format(prev_mask & (-1 << j), 'b').count('1')
            for t in range(N):
                if (1 << t) & prev_mask:
                    prev_elem = A[t] if (t - mask_pop - 1) % 2 == 1 else B[t]
                    if prev_elem <= cur_elem:
                        if dp[j][mask] > dp[t][prev_mask] + cost_delta:
                            dp[j][mask] = dp[t][prev_mask] + cost_delta
            
# print(*dp, sep = '\n')

ans = min((dp[i][-1] for i in range(N)))
if ans == 100100:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

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

num_cnt = [0]*n
sum_cnt = 0

for num in range(n):
    cnt = a.count(num+1)
    if cnt > 0:
        num_cnt[num] = cnt
        sum_cnt += cnt*(cnt-1)//2
res = [0]*n

for num in range(n):
    cnt = num_cnt[num]
    res[num] = (sum_cnt - (cnt-1)*(cnt - (cnt-2))//2) if cnt != 0 else 0

for a_k in a:
    print(res[a_k-1])

### FIXED CODE ###

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

import collections
cnt = collections.Counter(a)

sum_cnt = 0
for v in cnt.values():
    sum_cnt += v*(v-1)//2

res = []
for value in a:
    res.append(str( sum_cnt - (cnt[value]-1) ))
print('\n'.join(res))
### BUGGY CODE ###

from sys import stdin
def main():
    #入力
    readline=stdin.readline
    S=readline().strip()
    li=[0]*2019
    n=int(S)
    for i in range(len(S)):
        if i==0:
            pass
        else:
            n-=int(S[i-1])*10**(len(S)-i)
        li[n%2019]+=1

    res=li[0]
    for i in range(2019):
        res+=li[i]*(li[i]-1)//2
    print(res)
    
if __name__=="__main__":
    main()

### FIXED CODE ###

from sys import stdin
def main():
    #入力
    readline=stdin.readline
    S=readline().strip()
    li=[0]*2019
    n=int(S[-1])%2019
    m=1
    for i in range(len(S)):
        if i==0:
            pass
        else:
            m*=10
            m%=2019
            l=int(S[len(S)-i-1])
            n+=m*l
            n%=2019
        li[n]+=1

    res=li[0]
    for i in range(2019):
        res+=li[i]*(li[i]-1)//2
    print(res)
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

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

if K > Q: 
    for _ in range(N):
        print("Yes")
else:
    for i in range(1, N + 1):
        if i in A:
            print("{}".format("Yes" if (K + A.count(i) - Q) > 0 else "No"))
        else:
            print("No")

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
pnts = [0] * N

for i in A:
    pnts[i - 1] += 1

for i in pnts:
    if K - Q + i > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    X = int(input())
    import math
    for i in range(-10**4,10**5,2):
        for j in range(10**4 + 1,-10**5,-2):
            if i == j:
                continue
            if X % (i - j) == 0:
                if (i-j) * (pow(i,4) + pow(i,3)*j + pow(i,2)*pow(j,2) + i*pow(j,3) + pow(j,4)) == X:
                    print(i,j)
                    exit()
if __name__ == '__main__':
  main()


### FIXED CODE ###

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    X = int(input())
    import math
    for i in range(-119,119):
        for j in range(-119,119):
            if i == j:
                continue
            if X % (i - j) == 0:
                if (i-j) * (pow(i,4) + pow(i,3)*j + pow(i,2)*pow(j,2) + i*pow(j,3) + pow(j,4)) == X:
                    print(i,j)
                    exit()
if __name__ == '__main__':
  main()
### BUGGY CODE ###

n = input()
a_list = list(map(int, input().split()))
sum_ = 0
mod = 10 ** 9 + 7
for i in range(len(a_list) - 1):
  for j in range(i + 1, len(a_list)):
    sum_ += ((a_list[i] % mod) * (a_list[j] % mod)) % mod 
print(sum_ % mod)

### FIXED CODE ###

n = input()
a_list = list(map(int, input().split()))
ruisekiwa = [0] * (len(a_list) + 1) 
for i in range(len(a_list)):
    ruisekiwa[i + 1] = ruisekiwa[i] + a_list[i]
sum_ = 0
mod = 10 ** 9 + 7
for i in range(len(a_list)):
    sum_ += ((a_list[i] % mod) * ((ruisekiwa[-1] % mod) - (ruisekiwa[i + 1] % mod))) % mod
print(sum_ % mod)
### BUGGY CODE ###

t,*l=open(0)
h,w=map(int,t.split())
grid = [[c=="."for c in C]for C in l]
L,R,U,D = eval("[[0]*(w+2) for _ in range(h+2)],"*4)
for y in range(h):
	for x in range(w):
		L[y+1][x+1] = (L[y+1][x]+1)*grid[y][x]
		R[y+1][w-x] = (R[y+1][w-x+1]+1)*grid[y][w-x-1]
for x in range(w):
	for y in range(h):
		U[y+1][x+1] = (U[y][x+1]+1)*grid[y][x]
		D[h-y][x+1] = (D[h-y+1][x+1]+1)*grid[h-y-1][x]
print(max(L[y][x] + R[y][x] + U[y][x] + D[y][x] -3 for y in range(1,h+1) for x in range(1,w+1)))

### FIXED CODE ###

t,*grid = open(0)
h,w = map(int,t.split())
L,R,U,D = eval("[[0]*(w+2) for _ in range(h+2)],"*4)
for y in range(h):
	for x in range(w):
		if grid[y][x]==".":
			L[y+1][x+1] = L[y+1][x]+1
		if grid[y][w-x-1]==".":
			R[y+1][w-x] = R[y+1][w-x+1]+1
for x in range(w):
	for y in range(h):
		if grid[y][x]==".":
			U[y+1][x+1] = U[y][x+1]+1
		if grid[h-y-1][x]==".":
			D[h-y][x+1] = D[h-y+1][x+1]+1
a = 0
for y in range(1,h+1):
	for x in range(1,w+1):
		a = max(a, L[y][x] + R[y][x] + U[y][x] + D[y][x] -3)
print(a)