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

#!/usr/bin/env python3
from collections import Counter
n = int(input())
s = input()
count = 0
for le in range(1, n-1):
    mojiretu = Counter()
    for i in range(n-le+1):
        j = i+le
        if 0 < mojiretu[s[i:j]] <= i:
            count = le
            break
        else:
            mojiretu[s[i:j]] = j
print(count)


### FIXED CODE ###

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

class RollingHash():
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009
 
    def __init__(self, s, opt=2):
        self.n = len(s)
        self.opt = opt
        self.hash1 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        if opt == 2:
            self.hash2 = [0] * (self.n + 1)
            self.power2 = [1] * (self.n + 1)
        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
            if opt == 2:
                self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
                self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2
 
    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        if self.opt == 2:
            res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
            if(res2 < 0):
                res2 += self.__class__.MOD2
        return (res1, res2) if self.opt == 2 else res1


    
rh = RollingHash(S, opt=1)

def check(n: int):
    d = dict()
    for i in range(N - n + 1):
        p = rh.get(i, i + n)
        if p in d.keys():
            if(i - d[p] >= n):
                return True
        else:
            d[p] = i
    return False
    
ok, ng = 0, N // 2 + 1
while ng - ok > 1:
    mid = (ok + ng) // 2
    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)
### BUGGY CODE ###

import sys
read = sys.stdin.readline
import time
from heapq import heappush, heappop, heapify
import math
import itertools as it
from collections import deque 


def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
start_time = time.perf_counter()
# ------------------------------

H, W = inpl()
ch, cw = inpl()
dh, dw = inpl()
ch -= 1
cw -= 1
dh -= 1
dw -= 1

S = []
for i in range(H):
    S.append(input())

dist = []
INF = 1001001001
for i in range(H):
    dist.append([INF for i in range(W)])

q = deque([])
q.append((ch, cw))
dist[ch][cw] = 0
while q:
    h, w = q.popleft()
    # 歩き回る
    for i, j in ((1,0),(-1,0),(0,1),(0,-1)):
        if not 0 <= h + i < H:
            continue
        if not 0 <= w + j < W:
            continue
        if S[h+i][w+j] == '#':
            continue
        if dist[h][w] < dist[h+i][w+j]:
            dist[h+i][w+j] = dist[h][w]
            q.append((h+i, w+j))
    # ワープ
    for i in range(-2, 3):
        for j in range(-2, 3):
            if not 0 <= h + i < H:
                continue
            if not 0 <= w + j < W:
                continue
            if S[h+i][w+j] == '#':
                continue
            if dist[h][w] + 1 < dist[h+i][w+j]:
                dist[h+i][w+j] = dist[h][w] + 1
                q.append((h+i, w+j))

print(dist[dh][dw] if dist[dh][dw] != INF else -1)



# -----------------------------
end_time = time.perf_counter()
print('time:', end_time-start_time, file=sys.stderr)



### FIXED CODE ###

import sys
read = sys.stdin.readline
import time
from heapq import heappush, heappop, heapify
import math
import itertools as it
from collections import deque 


def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
start_time = time.perf_counter()
# ------------------------------

H, W = inpl()
ch, cw = inpl()
dh, dw = inpl()
ch -= 1
cw -= 1
dh -= 1
dw -= 1

S = []
for i in range(H):
    S.append(input())

dist = []
INF = 1001001001
for i in range(H):
    dist.append([INF for i in range(W)])

q = deque([])
q.append((ch, cw))
dist[ch][cw] = 0
while q:
    h, w = q.popleft()
    # 歩き回る
    for i, j in ((1,0),(-1,0),(0,1),(0,-1)):
        if not 0 <= h + i < H:
            continue
        if not 0 <= w + j < W:
            continue
        if S[h+i][w+j] == '#':
            continue
        if dist[h][w] < dist[h+i][w+j]:
            dist[h+i][w+j] = dist[h][w]
            q.appendleft((h+i, w+j))
    # ワープ
    for i in range(-2, 3):
        for j in range(-2, 3):
            if not 0 <= h + i < H:
                continue
            if not 0 <= w + j < W:
                continue
            if S[h+i][w+j] == '#':
                continue
            if dist[h][w] + 1 < dist[h+i][w+j]:
                dist[h+i][w+j] = dist[h][w] + 1
                q.append((h+i, w+j))

print(dist[dh][dw] if dist[dh][dw] != INF else -1)



# -----------------------------
end_time = time.perf_counter()
print('time:', end_time-start_time, file=sys.stderr)
### BUGGY CODE ###

import numpy as np
import copy
import queue


q = queue.Queue()

n, m = map(int, input().split())
l = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    l[a-1][b-1] = 1
    l[b-1][a-1] = 1


l = np.array(l)
lc = copy.deepcopy(l)
li = [-1 for _ in range(n)]

def search(x):
    if sum(lc[x]) == 0:
        q.queue = False
        return
    
    ind_lis = np.where(lc[x] == 1)
#     print(ind_lis)
    for e in ind_lis[0]:
#         print(e+1)

        lc[x][e] =0
        lc[e][x] =0
        if li[e] == -1:
            li[e] = x
            q.put(e)
x = 0
search(x)
while q.queue:
    search(q.get())

if li[1:].count(-1) == 0:
    print('Yes')
    for e in li[1:]:
        print(e+1)
else:
    print('No')


### FIXED CODE ###

# import numpy as np
# import copy
from collections import defaultdict
import queue


q = queue.Queue()

n, m = map(int, input().split())
graph = defaultdict(list)
for _ in range(m):
    a, b = map(lambda x: int(x), input().split())
    graph[a].append(b)
    graph[b].append(a)


# l = np.array(l)
# lc = copy.deepcopy(l)
li = [-1 for _ in range(n)]
li[0] = 1

def search(x):
#     if sum(l[x]) == 0:
#         q.queue = False
#         return
    
#     ind_lis = np.where(lc[x] == 1)[0]
#     ind_lis = [e for e in ind_lis if li[e] == -1]
#     print(li)
#     print(lc[x])
    for e in graph[x]:
#         print(e)
        if li[e-1] != -1:
            continue
        li[e-1] = x
#         print('q', i+1)
        q.put(e)
x = 1
search(x)
while q.queue:
    search(q.get())

if li[1:].count(-1) == 0:
    print('Yes')
    for e in li[1:]:
        print(e)
else:
    print('No')
### BUGGY CODE ###

n,k = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]
dp = [float("inf") for _ in range(n)]
dp[0] = 0
for i in range(1,n):
    for j in range(1,min(k,i)+1):
        dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp[-1])

### FIXED CODE ###

n,k = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]
dp = [float("inf") for _ in range(n)]
dp[0] = 0
for i in range(1,n):
    for j in range(1,min(k,i)+1):
        dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp[-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

n = int(input())
a = list(map(int, input().split()))
dic = dict()
dic[(0,0,0)] = 0
def dfs(uno,dos,tres):
  if uno < 0 or dos < 0 or tres < 0:
    return 0
  if (uno,dos,tres) in dic:
    return dic[(uno,dos,tres)]
  t = uno + dos + tres
  res = n
  res += uno*dfs(uno-1,dos,tres)
  res += dos*dfs(uno+1,dos-1,tres)
  res += tres*dfs(uno,dos+1,tres-1)
  res /= t
  dic[(uno,dos,tres)] = res
  return res

print(dfs(a.count(1),a.count(2),a.count(3)))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
uno = a.count(1)
dos = a.count(2)
tres = n - uno - dos
dp = [[[0]*(n+1) for _ in range(dos+tres+1)] for j in range(tres+1)]
for k in range(tres+1):
  for j in range(dos+tres-k+1):
    for i in range(n+1-j-k):
      if i+j+k == 0: continue
      v = i+j+k
      res = n
      if i: res += i * dp[k][j][i-1]
      if j: res += j * dp[k][j-1][i+1]
      if k: res += k * dp[k-1][j+1][i]
      dp[k][j][i] = res / v
print(dp[tres][dos][uno])
### BUGGY CODE ###

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

a = [0 for _ in range(n)]

a = [int(s) for s in input().split()]

a_sum = [0 for _ in range(n+1)]
a_sum[0] = 1


for i in range(1,n+1):
    a_sum[i] = a_sum[i-1] * a[i-1]


score = [0 for _ in range(n-k+1)]

for i in range(k,n+1):
    score[i-k] = int(a_sum[i]/a_sum[i-k])

#print(score)

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

### FIXED CODE ###

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

a = [0 for _ in range(n)]

a = [int(s) for s in input().split()]

for i in range(k,n):
    if(a[i] > a[i-k]):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    n,u,v = map(int,input().split())

    edges = [[] for _ in range(n)]

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

    stack1 = [u-1]
    stack2 = [v-1]

    dis1 = [-1] * n
    dis2 = [-1] * n
    dis1[u-1] = 0
    dis2[v-1] = 0

    while stack1 or stack2:
        for _ in range(len(stack1)):
            q1 = stack1.pop(0)
            for i in edges[q1]:
                if dis1[i] == -1 and dis2[i] == -1:
                    dis1[i] = dis1[q1] + 1
                    stack1.append(i)

        for _ in range(len(stack2)):
            q2 = stack2.pop(0)
            for i in edges[q2]:
                if dis2[i] == -1:
                    dis2[i] = dis2[q2] + 1
                    stack2.append(i)

    ans = 0
    for i in range(n):
        if dis1[i] != -1:
            ans = max(ans, dis2[i])

    print(ans-1)

if __name__ == '__main__':
    main()
    


### FIXED CODE ###

import sys
input = sys.stdin.readline

n,u,v = map(int,input().split())
edges = [[] for _ in range(n)]

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

visit1 = [False] * n
visit2 = [False] * n
visit1[u-1] = True
visit2[v-1] = True

dis1 = [-1] * n
dis2 = [-1] * n
dis1[u-1] = 0
dis2[v-1] = 0

stack1 = [u-1]
stack2 = [v-1]

while stack1:
    l = stack1.pop(-1)
    for i in edges[l]:
        if visit1[i] == False:
            visit1[i] = True
            dis1[i] = dis1[l] + 1
            stack1.append(i)

while stack2:
    l = stack2.pop(-1)
    for i in edges[l]:
        if visit2[i] == False:
            visit2[i] = True
            dis2[i] = dis2[l] + 1
            stack2.append(i)

ans = 0

for i in range(n):
    if dis1[i] < dis2[i]:
        ans = max(ans, dis2[i])

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

import bisect
n = int(input())
a = list(map(int,input().split()))
d = int(input())
graph = [0 for i in range(n+1)]
for i in range(n-1):
  x = bisect.bisect_right(a,a[i]+d)
  if x == i:
    continue
  graph[i+1] = x
group = [0]*(n+1)
row = [[]]
cnt = 0
stack = []
for i in range(1,n+1):
  if group[i] == 0:
    stack.append(i)
    cnt += 1
    row.append([])
    while stack:
      x = stack.pop()
      row[cnt].append(x)
      group[x] = cnt
      if x != n:
        stack.append(graph[x])
q = int(input())
for _ in range(q):
  l,r = map(int,input().split())
  if l>r:
    l,r = r,l
  x = group[l]
  yl = bisect.bisect_left(row[x],l)
  yr = bisect.bisect_left(row[x],r)
  print(yr-yl)

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
d = int(input())
graph = [[0 for i in range(n+1)] for j in range(18)]
for i in range(n):
  x = bisect.bisect_right(a,a[i]+d)
  graph[0][i+1] = x
for j in range(1,18):
  for i in range(n):
    t = graph[j-1][i+1]
    graph[j][i+1] = graph[j-1][t]
q = int(input())
for _ in range(q):
  x,y = map(int,input().split())
  x,y = min(x,y),max(x,y)
  ans = 0
  for j in range(18)[::-1]:
    if graph[j][x] < y:
      ans += 2**j
      x = graph[j][x]
    if j == 0 and x < y:
      ans += 1
  print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
s = []
c = 0
for i in a:
    if not i in s:
        s.append(i)
    else:
        c += 1
print(n - 2 * ((c + 1) // 2))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = set(a)
print(n - 2 * ((n - len(b) + 1) // 2))
### BUGGY CODE ###

n, mw = map(int, input().split())
iwv = [list(map(int, input().split())) for _ in range(n)]

vw = [0] * (mw + 1)

for i in range(n):
  for j in reversed(range(iwv[i][0], mw + 1)):
    vw[j] = max(vw[j], vw[j - iwv[i][0]] + iwv[i][1])
  
print(max(vw))


### FIXED CODE ###

n, mw = map(int, input().split())
iwv = [list(map(int, input().split())) for _ in range(n)]

vw = [0] * (mw + 1)

for i in range(n):
  for j in reversed(range(iwv[i][0], mw + 1)):
    vw[j] = max(vw[j], vw[j - iwv[i][0]] + iwv[i][1])
  
print(max(vw))
### BUGGY CODE ###

import math
import numpy as np

n,k = map(int, input().split())
# lstA = list(map(int, input().split()))
# lstF = list(map(int, input().split()))
# lstA.sort()
# lstF.sort()
# lstF.reverse()
lstA = np.array(sorted(list(map(int, input().split()))))
lstF = np.array(sorted(list(map(int, input().split())), reverse=True))

def check(x):
    checker = 0
    for i in range(n):
        checker += math.ceil(lstA[i]-x/lstF[i])
    if checker <= k:
        return True
    else:
        return False

left = -1
right = 10**12

while True:
    center = (left+right)//2
    if check(center) == True:
        right = center
    else:
        left = center
    if right <= left+1:
        print(right)
        exit()


### FIXED CODE ###

import numpy as np

n,k = map(int, input().split())
lstA = np.array(sorted(list(map(int, input().split()))))
lstF = np.array(sorted(list(map(int, input().split())), reverse=True))
s = lstA.sum()

left = -1
right = 10**12

while True:
    center = (left+right)//2
    if s-np.minimum(lstA, center//lstF).sum() <=k:
        right = center
    else:
        left = center
    if right <= left+1:
        print(right)
        exit()
### BUGGY CODE ###

N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
ans = 0
for i in C:
    for j in B:
        if i <= j:
            break
        for k in A:
            if j <= k:
                break
            ans += 1
print(ans)

### 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())))
ans = 0

for i in B:
    ans += bisect.bisect_left(A,i)*(N-bisect.bisect_right(C,i))
print(ans)
### BUGGY CODE ###

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

ans_al = [0]*n

for i in range(n):
    ans_al[i-1] += al.count(i)

for ans in ans_al:
    print(ans)

### FIXED CODE ###

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

ans_al = [0]*n

# for i in range(n):
#     ans_al[i-1] += al.count(i)

for a in al:
    ans_al[a-1] += 1

for ans in ans_al:
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
N,M = list(map(int,input().split()))
p = [i-1 for i in map(int,input().split())]
alr = [False for i in range(N)]
xy = [[] for i in range(N)]
for i in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    xy[x].append((y,p.index(y)))
    xy[y].append((x,p.index(x)))
count = 0

for i in range(N):
    if (not alr[i]) and (xy[i]):
        alr[i] = True
        stack = [i]
        indlist = set()
        indlist.add(p.index(i))
        numlist = set()
        numlist.add(i)
        while stack:
            j = stack.pop()
            for num,ind in xy[j]:
                if not alr[num]:
                    alr[num] = True
                    stack.append(num)
                    numlist.add(num)
                    indlist.add(ind)
        count += len(numlist & indlist)
    else:
        if (not alr[i]) and p[i] == i:
            count += 1
print(count)
                

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
N,M = list(map(int,input().split()))
p = [i-1 for i in map(int,input().split())]
alr = [False for i in range(N)]
xy = [[] for i in range(N)]
for i in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    xy[x].append(y)
    xy[y].append(x)
count = 0

for i in range(N):
    if (not alr[i]) and (xy[i]):
        alr[i] = True
        stack = [i]
        numlist = set()
        numlist.add(i)
        while stack:
            j = stack.pop()
            for k in xy[j]:
                if not alr[k]:
                    alr[k] = True
                    stack.append(k)
                    numlist.add(k)
        indlist = set([p[i] for i in numlist])
        count += len(numlist & indlist)
    else:
        if (not alr[i]) and p[i] == i:
            count += 1
print(count)
### BUGGY CODE ###

import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A)
#B=list(reversed(A))
A=np.array(A)
Aneg=A[A<0]
Azero=A[A==0]
Apos=A[A>0]

n_neg=len(Aneg)*len(Apos)
n_zero=len(Azero)*(len(Azero)-1)//2+len(Azero)*(len(Aneg)+len(Apos))
n_pos=(len(Apos)*(len(Apos)-1)+len(Aneg)*(len(Aneg)-1))//2

if K <=n_neg:
    n=K
    B=sorted(Aneg)
    C=sorted(Apos)
    ans=[]
    for i in range(len(B)):
        for j in range(len(C)):
            ans.append(B[i]*C[j])
    ans=sorted(ans)
    print(ans[n-1])
    
elif K>n_neg+n_zero:
    n=K-(n_neg+n_zero)
    B=sorted(Aneg)
    B=list(reversed(B))
    C=sorted(Apos)
    ans=[]
    if len(B)>2:
        for i in range(len(B)-1):
            for j in range(i+1,len(B)):
                ans.append(B[i]*B[j])
    if len(C)>2:
#         k=min(len(C),n-1)
        for i in range(len(C)-1):
            for j in range(i+1,len(C)):
                ans.append(C[i]*C[j])
    ans=sorted(ans)
    print(ans[n-1])
    
else:
    print(0)

### FIXED CODE ###

import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=-A_neg[::-1]
n_pos=len(A_pos)
n_neg=len(A_neg)
n_zero=N-n_pos-n_neg

def position_in_neg(x):
    y=n_pos-np.searchsorted(A_pos,x//A_neg,side='right')
    return y.sum()

def position_in_pos(x):
    z=np.searchsorted(A_pos,-(-x//A_pos),side='left')
    w=np.searchsorted(A_neg2,-(-x//A_neg2),side='left')
    tmp=len(A_pos[A_pos**2<x])+len(A_neg2[A_neg2**2<x])
    return (z.sum()+w.sum()-tmp)//2

def position(x):
    if x<0:
        return position_in_neg(x)
    elif x==0:
        return n_pos*n_neg
    else:
        return position_in_pos(x)+n_pos*n_neg+(n_pos+n_neg)*n_zero+n_zero*(n_zero-1)//2

l=-pow(10,18)
r=pow(10,18)
while(r-l>1):
    mid=(l+r)//2
    if position(mid)<K:
        l=mid
    else:
        r=mid
print(l)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
n = int(input())
s = str(n)
l = len(s)

INF = float('inf')
dp = [[INF]*2 for _ in range(l+1)]
dp[0][0]=0
dp[0][1]=1
for i in range(l):
    num = int(s[i])
    dp0 = dp[i][0]
    dp1 = dp[i][1]
    dp[i+1][0] = min(dp0+num, dp1+min(10-num,num+1))
    dp[i+1][1] = min(dp0+num+1,dp1+10-num-1)

print(dp[-1][0])


### FIXED CODE ###

s = input()
l = len(s)

INF = float('inf')
dp = [[INF]*2 for _ in range(l+1)]
dp[0][0]=0
dp[0][1]=1
for i in range(l):
    num = int(s[i])
    dp0 = dp[i][0]
    dp1 = dp[i][1]
    dp[i+1][0] = min(dp0+num, dp1+min(10-num,num+1))
    dp[i+1][1] = min(dp0+num+1,dp1+10-num-1)

print(dp[-1][0])
### BUGGY CODE ###

import re
import sys
s = sys.stdin.readlines()
N, Q = map(int, s[0].split())
S = s[1]
for i in s[2:]:
    a, b = map(int, i.split())
    print(len(re.findall("AC", S[a-1:b])))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

acl = [0]*(N+1)

for i in range(N):
    acl[i+1] = acl[i] + (1 if S[i:i+2] == "AC" else 0)

for _ in range(Q):
    l, r = map(int, input().split())
    print(acl[r-1] - acl[l-1])
### BUGGY CODE ###

from functools import reduce
n=int(input())
A=list(map(int,input().split()))
ans=reduce(lambda x,y:x*y,A)

if ans>1000000000000000000:
    print(-1)
else:
    print(ans)
    

### FIXED CODE ###

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

ans=1

if 0 in A:
    print(0)
    exit()

for i in A:
   ans=ans*i
   if ans>10**18:
    print(-1)
    exit()


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

from collections import deque
import sys
input = sys.stdin.readline

k = int(input())
n = 7
ans = -1

for i in range(10**6): #注意
  if n % k  == 0:
    ans = i+1
    break
  else:
    n =  n*10 + 7
    
print(ans)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
 
k = int(input())
n = 7
ans = -1
 
for i in range(10**6): #注意
  if n % k  == 0:
    ans = i+1
    break
  else:
    n =  (n % k) *10 + 7
    
print(ans)
### BUGGY CODE ###

import numpy as np

def calculate(h, w, arr):
    L = np.zeros([h, w])
    U = np.zeros([h, w])
    D = np.zeros([h, w])
    R = np.zeros([h, w])

    for ih in range(h):
        for iw in range(w):
            if arr[ih][iw] == ".":
                if ih == 0:
                    U[ih][iw] = 1
                if iw == 0:
                    L[ih][iw] = 1

                if iw > 0:
                    L[ih][iw] = L[ih][iw - 1] + 1
                if ih > 0:
                    U[ih][iw] = U[ih - 1][iw] + 1


    for ih in range(h):
        for iw in range(w):
            rih = h - 1 - ih
            riw = w - 1 - iw
            if arr[rih][riw] == ".":
                if rih == h - 1:
                    D[rih][riw] = 1
                if riw == w - 1:
                    R[rih][riw] = 1

                if riw < w - 1:
                    R[rih][riw] = R[rih][riw + 1] + 1
                if rih < h - 1:
                    D[rih][riw] = D[rih + 1][riw] + 1

    max = 0
    for ih in range(h):
        for iw in range(w):
            if arr[ih][iw] == "#":
                continue
            value = L[ih][iw] + R[ih][iw] + U[ih][iw] + D[ih][iw] - 3
            if value > max:
                max = value
    print(int(max))


S = input().split(" ")
H = int(S[0])
W = int(S[1])

arr = []
for i in range(H):
    arr.append(input())

calculate(H, W, arr)


### FIXED CODE ###

def calculate(h, w, arr):
    L = [[0]*w for i in range(h)]
    U = [[0]*w for i in range(h)]
    D = [[0]*w for i in range(h)]
    R = [[0]*w for i in range(h)]

    for ih in range(h):
        for iw in range(w):
            if ih == 0:
                U[ih][iw] = 1
            if iw == 0:
                L[ih][iw] = 1

            if arr[ih][iw] == 1:
                L[ih][iw] = 0
                U[ih][iw] = 0

            else:
                if iw > 0:
                    L[ih][iw] = L[ih][iw - 1] + 1
                if ih > 0:
                    U[ih][iw] = U[ih - 1][iw] + 1

            rih = h - 1 - ih
            riw = w - 1 - iw

            if rih == h - 1:
                D[rih][riw] = 1
            if riw == w - 1:
                R[rih][riw] = 1

            if arr[rih][riw] == 1:
                D[rih][riw] = 0
                R[rih][riw] = 0
            else:
                if riw < w - 1:
                    R[rih][riw] = R[rih][riw + 1] + 1
                if rih < h - 1:
                    D[rih][riw] = D[rih + 1][riw] + 1

    max = 0
    for ih in range(h):
        for iw in range(w):
            value = L[ih][iw] + R[ih][iw] + U[ih][iw] + D[ih][iw] - 3
            if value > max:
                max = value
    print(int(max))


S = input().split(" ")
H = int(S[0])
W = int(S[1])

arr = []
for i in range(H):
    q = input()
    tmp = []
    for qs in q:
        if qs == "#":
            tmp.append(1)
        if qs == ".":
            tmp.append(0)
    arr.append(tmp)

calculate(H, W, arr)