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

def main():
    ConstNum,PersonNum=map(int,input().split())

    ConstInfo={}
    for i in range(ConstNum):
        S,T,X=map(int,input().split())

        if (X in ConstInfo):
            ConstInfo[X].append((S,T))
        else:
            ConstInfo[X]=[(S,T)]

        #ConstInfo=>{X:[(S,T),(S,T)],X:[(S,T)],...}

    ConstPlace=ConstInfo.keys()
    MaxConstPlace=max(ConstPlace)

    DepartureTime=[]
    for i in range(PersonNum):
        d=int(input())
        DepartureTime.append(d)

    res=[]

    for i in range(PersonNum):
        distance=0
        time=DepartureTime[i]

        underConst=False
        while distance<MaxConstPlace and underConst==False:
            time += 1
            distance += 1
            if (distance in ConstPlace):
                for const_time in ConstInfo[distance]:
                    if time>=const_time[0]-0.5 and time<=const_time[1]-0.5:
                        underConst=True
                        break



        if underConst:
            res.append(distance)
        else:
            res.append(-1)

    for i in res:
        print(i)

if __name__=="__main__":
    main()





### FIXED CODE ###

from bisect import bisect_left

def main():
    ConstNum,PersonNum=map(int,input().split())

    S=[]
    T=[]
    X=[]
    for i in range(ConstNum):
        s,t,x=map(int,input().split())
        S.append(s)
        T.append(t)
        X.append(x)

    DepartureTime=[]
    for i in range(PersonNum):
        d=int(input())
        DepartureTime.append(d)

    XST=zip(X,S,T)
    XST=sorted(XST)

    res=[-1]*PersonNum
    stop=[-1]*PersonNum

    for x,s,t in XST:
        left_value=s-x
        right_value=t-x

        left_index=bisect_left(DepartureTime,left_value)
        right_index=bisect_left(DepartureTime,right_value)

        while left_index<right_index:
            if stop[left_index]==-1:
                res[left_index]=x
                stop[left_index]=right_index
                left_index+=1
            else:
                left_index=stop[left_index]

    for i in range(PersonNum):
        print(res[i])

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

import numpy as np

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

field = [[None] * w for _ in range(h)]
aaa = [list(map(int, input().split())) for _ in range(h)]
bbb = [list(map(int, input().split())) for _ in range(h)]
aaa = np.array(aaa, dtype=np.int64)
bbb = np.array(bbb, dtype=np.int64)
diff = abs(aaa - bbb)

offset = 15000
can = np.zeros(30001, dtype=np.int64)
can[diff[0][0] + offset] = 1
field[0][0] = can


def merge_new_can(d, can, prev_can):
    if d == 0:
        can |= prev_can
    else:
        can[d:] |= prev_can[:-d]
        can[:-d] |= prev_can[d:]


for j in range(1, w):
    d = diff[0][j]
    prev_can = field[0][j - 1]
    can = np.zeros(30001, dtype=np.int64)
    merge_new_can(d, can, prev_can)
    field[0][j] = can

for i in range(1, h):
    d = diff[i][0]
    prev_can = field[i - 1][0]
    can = np.zeros(30001, dtype=np.int64)
    merge_new_can(d, can, prev_can)
    field[i][0] = can

for i in range(1, h):
    for j in range(1, w):
        d = diff[i][j]
        can = np.zeros(30001, dtype=np.int64)
        prev_can1 = field[i][j - 1]
        prev_can2 = field[i - 1][j]
        merge_new_can(d, can, prev_can1)
        merge_new_can(d, can, prev_can2)
        field[i][j] = can

goal = field[-1][-1]
goal[15001:] |= goal[:15000][::-1]
goal = goal[15000:]
print(np.argmax(goal))


### FIXED CODE ###

import numpy as np

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

aaa = [list(map(int, input().split())) for _ in range(h)]
bbb = [list(map(int, input().split())) for _ in range(h)]
aaa = np.array(aaa, dtype=np.int8)
bbb = np.array(bbb, dtype=np.int8)
diff = abs(aaa - bbb)


def merge_new_can(d, can, prev_can):
    if d == 0:
        can |= prev_can
    else:
        can[d:] |= prev_can[:-d]
        can[:-d] |= prev_can[d:]


prev_row = [None] * w

can = np.zeros(25601, dtype=np.int8)
can[diff[0][0] + 12800] = 1
prev_row[0] = can

for j in range(1, w):
    d = diff[0][j]
    can = np.zeros(25601, dtype=np.int8)
    prev_can = prev_row[j - 1]
    merge_new_can(d, can, prev_can)
    prev_row[j] = can

for i in range(1, h):
    curr_row = [None] * w

    d = diff[i][0]
    prev_can = prev_row[0]
    can = np.zeros(25601, dtype=np.int8)
    merge_new_can(d, can, prev_can)
    curr_row[0] = can

    for j in range(1, w):
        d = diff[i][j]
        can = np.zeros(25601, dtype=np.int8)
        prev_can1 = prev_row[j]
        prev_can2 = curr_row[j - 1]
        merge_new_can(d, can, prev_can1)
        merge_new_can(d, can, prev_can2)
        curr_row[j] = can

    prev_row = curr_row

goal = prev_row[-1]
goal[12801:] |= goal[:12800][::-1]
goal = goal[12800:]
print(np.argmax(goal))
### BUGGY CODE ###

a = int(input())
b = list(map(int,input().split()))
n = 1
m = 1
aa = a/2

c = 0
d = 0

if a%2 == 1:
    aa = (aa*2+1)//2

for i in b:
    if i == 0:
        c += 1
    elif i > 10**18:
        d += 1
        
if c > 0:
    print(0)
    exit()
if d > 1 and c == 0:
    print(-1)
    exit()
    
for i in range(int(aa)):
  n = n * b[i]

for i in range(int(aa),a):
    m *= b[i]

if n * m <= 10**18:
    print(n*m)
    exit()
  
print('-1')


### FIXED CODE ###

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

c = 0
d = 0

for i in b:
    if i == 0:
        c += 1
    elif i > 10**18:
        d += 1
        
if c > 0:
    print(0)
    exit()
if d > 1 and c == 0:
    print(-1)
    exit()

for i in b:
  n *= i
  if n > 10**18:
    print(-1)
    exit()
print(n)
### BUGGY CODE ###

import itertools
N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

diff =[V[n] - C[n] for n in range(N)]
XY = 0

for v in itertools.permutations([0, 1] * N, N):
  xy = 0
  for n in range(N):
    xy += diff[n] * v[n]
  if xy > XY:
    XY = xy
print(XY)

### FIXED CODE ###

N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

diff = [0]
for n in range(N):
  if V[n] - C[n] > 0:
    diff.append(V[n] - C[n])

print(sum(diff))
### BUGGY CODE ###

N = int(input())
D = list(map(int, input().split()))
mod = 998244353
if D[0] != 0:
  print(0)
  exit()
ans = 1
for i in range(max(D)+1):
  if D.count(i) == 0:
    print(0)
    exit()
  if i > 0:
    ans *= pow(D.count(i-1), D.count(i), mod)
print(ans % mod)

### FIXED CODE ###

N = int(input())
D = list(map(int, input().split()))
mod = 998244353
ans = 1
A = [0]*(max(D)+1)
for i in range(N):
  A[D[i]] += 1
if D[0] != 0 or not all(D[1:]) or not all(A):
  print(0)
  exit()
if D[0] != 0:
  print(0)
  exit()
for i in range(1, max(D)+1):
#  if A[i] == 0:
#    print(0)
#    exit()
  ans = ans * pow(A[i-1], A[i], mod) % mod
print(ans % mod)
### BUGGY CODE ###

def main():
    import sys
    K=int(sys.stdin.readline())
    if K%2==0:
        print(-1)
        return

    L=[7%K]
    L2=[7%K]
    if L[0]==0:
        print(1)
        return

    idx=0
    while True:
        L2.append((L2[idx]*10)%K)
        L.append((L[idx]+L2[idx+1])%K)
        if L[-1]==0:
            print(len(L))
            return
        idx+=1


main()

### FIXED CODE ###

def main():
    import sys
    import time
    start=time.time()
    K=int(sys.stdin.readline())
    if K%2==0:
        print(-1)
        return

    L=[7%K]
    L2=[7%K]
    if L[0]==0:
        print(1)
        return

    idx=0
    while True:
        L2.append((L2[idx]*10)%K)
        L.append((L[idx]+L2[idx+1])%K)
        if L[-1]==0:
            print(len(L))
            return
        idx+=1

        if time.time()-start>=1.5:
            print(-1)
            return
main()
### BUGGY CODE ###

from decimal import Decimal
from numba import njit, i4, i8


def main():
    @njit(i8(i8, i4), cache=True)
    def div(n, d):
        cnt = 0
        while n % d == 0:
            n //= d
            cnt += 1
        return cnt

    @njit(cache=True)
    def solve(arr):
        ans = 0
        for i in range(len(arr)):
            for j in range(i + 1, len(arr)):
                (a, b), (c, d) = arr[i], arr[j]
                if a + c >= 18 and b + d >= 18:
                    ans += 1
        return ans

    n = int(input())
    arr = [int(Decimal(input()) * 10**9) for _ in range(n)]
    arr = [(div(x, 2), div(x, 5)) for x in arr]

    print(solve(arr))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def div(n, d):
    cnt = 0
    while n % d == 0 and cnt < 18:
        n //= d
        cnt += 1
    return cnt


n = int(input())
dp = [[0]*19 for _ in range(19)]

ans = 0
for _ in range(n):
    x = round(float(input()) * pow(10, 9))
    two = div(x, 2)
    five = div(x, 5)
    ans += dp[18 - two][18 - five]
    for i in range(two + 1):
        for j in range(five + 1):
            dp[i][j] += 1

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

N,K = map(int,input().split())
Dices = list(map(int,input().split()))

from collections import deque

d=deque([])
total= 0
for i in range(N):
    d.append((Dices[i]+1)/2)
    if len(d)==K:
        total = max(total,sum(d))
        d.popleft()

print(total)



### FIXED CODE ###

N,K = map(int,input().split())
Dices = list(map(int,input().split()))

Dices = list(map(lambda n:(n+1)/2,Dices))
import numpy as np 
Dices = np.cumsum(Dices)
# from collections import deque

# d=deque([])
# total= 0
# for i in range(N):
#     d.append((Dices[i]+1)/2)
#     if len(d)==K:
#         total = max(total,sum(d))
#         d.popleft()

# print(total)

#累積和
S=np.append(0,Dices)
total = 0
# for i in range(N+1):
#     S[i] = sum(Dices[:i])

for j in range(N-K+1):
    total = max(total,S[j+K]-S[j])

print(total)
### BUGGY CODE ###

n = int(input())
seq = list(map(int,input().split()))
ans = 1

for i in range(1, len(seq)):
    if seq[i] <= n - i + 2:
        for j in range(0, i+1):
            if seq[j]<seq[i]:
                break
            if j==i:
                ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
seq = list(map(int,input().split()))
ans = 1
minim = n

for i in range(1, n):
    minim = min(minim, seq[i-1])
    if minim > seq[i]:
        ans += 1

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

N = int(input())
D = [list(map(int, input().split())) for _ in range(N)]

A=0
B=0
for i in range(N):
  if i%2==0:
    m=max(D, key=lambda x:x[0])
    tmp=[d for d in D if d[0]==m[0]]
    t=max(tmp, key=lambda x:x[1])
    A+=t[0]
    D.remove(t)
  else:
    m=max(D, key=lambda x:x[1])
    tmp=[d for d in D if d[1]==m[1]]
    t=max(tmp, key=lambda x:x[0])
    B+=t[1]
    D.remove(t)
  
print(A-B)

### FIXED CODE ###

N = int(input())
D=[]
b=0
for _ in range(N):
  A,B=map(int, input().split())
  D.append([A,B,A+B])
  b+=B
D.sort(reverse=True, key=lambda x:x[2])

ans=0
while D!=[]:
  ans+=D[0][2]
  D.pop(0)
  if D!=[]:
    D.pop(0)
  
print(ans-b)
### BUGGY CODE ###

h, w = map(int, input().split())
lst = []
for i in range(h):
    lst.append(list(input()))

R = [[0]*w for _ in range(h)]
L = [[0]*w for _ in range(h)]
U = [[0]*w for _ in range(h)]
D = [[0]*w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if lst[i][j] == '.':
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1] + 1
        

for i in range(h):
    for j in range(w-1, -1, -1):
        if lst[i][j] == '.':
            if j == w-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j+1] + 1            


for i in range(h):
    for j in range(w):
        if lst[i][j] == '.':
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j] + 1

for i in range(h-1, -1, -1):
    for j in range(w):
        if lst[i][j] == '.':
            if i == h-1:
                D[i][j] = 1
            else:
                D[i][j] = D[i+1][j] + 1

ans = 0
x = [[0]*w for _ in range(h)]
for i in range (h):
    for j in range(w):
        x[i][j] = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
        ans = max(ans, max(x[i]))
print(ans) 

### FIXED CODE ###

h, w = map(int, input().split())
lst = []
for i in range(h):
    lst.append(list(input()))

R = [[0]*w for _ in range(h)]
L = [[0]*w for _ in range(h)]
U = [[0]*w for _ in range(h)]
D = [[0]*w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if lst[i][j] == '.':
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1] + 1
        

for i in range(h):
    for j in range(w-1, -1, -1):
        if lst[i][j] == '.':
            if j == w-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j+1] + 1            


for i in range(h):
    for j in range(w):
        if lst[i][j] == '.':
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j] + 1

for i in range(h-1, -1, -1):
    for j in range(w):
        if lst[i][j] == '.':
            if i == h-1:
                D[i][j] = 1
            else:
                D[i][j] = D[i+1][j] + 1

ans = 0
x = [[0]*w for _ in range(h)]
for i in range (h):
    for j in range(w):
        x[i][j] = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
    ans = max(ans, max(x[i]))
print(ans)
### BUGGY CODE ###

import numpy as np

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

MOD = 998244353

dp = np.zeros(s+1) #動的計画法を用いる
dp[0] = 1

for i in range(n):
    ddp = dp * 2
    for ss in range(s,a[i]-1,-1):
        ddp[ss] += dp[ss-a[i]]%MOD #非常に大きな数になると考えられるため先にMOD計算を行う
    dp = ddp % MOD


print(int(dp[s]))

### FIXED CODE ###

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

MOD = 998244353

dp = [[0]*(s+1) for i in range(n+1)] #動的計画法を用いる
dp[0][0] = 1

for i in range(n):
    for ss in range(s+1):
        if(ss >= a[i]):
            dp[i+1][ss] = (dp[i][ss]*2 + dp[i][ss-a[i]])%MOD #非常に大きな数になると考えられるため先にMOD計算を行う
        else:
            dp[i+1][ss] = dp[i][ss]*2 % MOD

print(dp[n][s])
### BUGGY CODE ###

N = int(input())
A,B = [],[]
for i in range(N):
    n=int(input())
    A.append(n)
    for k in range(n):
        x,y = map(int,input().split())
        B.append([i,x,y])
ans = 0
for i in range(2**N):
    cnt = 0
    ok = True
    for j in range(N):
        #正直者を1にする
        if (i>>j) & 1:
            cnt += 1
            for k in range(len(B)):
                if B[k][0] == j:
                    if ((i >> (B[k][1]-1)) & 1) and B[k][2] == 1:
                        continue
                    elif ((i >> (B[k][1]-1)) & 1 == 0) and B[k][2] == 0:
                        continue
                    else:
                        ok = False
                        break
    if ok:
        ans = max(ans,cnt)
print(ans)

### FIXED CODE ###

N = int(input())
A,B = [],[]
for i in range(N):
    n=int(input())
    A.append(n)
    for k in range(n):
        x,y = map(int,input().split())
        B.append([i,x,y])
ans = 0
for i in range(2**N):
    cnt = 0
    ok = True
    for j in range(N):
        #正直者を1にする
        if (i>>j) & 1:
            cnt += 1
            for k in range(len(B)):
                if B[k][0] != j:
                    continue
                else:
                    if ((i >> (B[k][1]-1)) & 1) and B[k][2] == 1:
                        continue
                    elif ((i >> (B[k][1]-1)) & 1 == 0) and B[k][2] == 0:
                        continue
                    else:
                        ok = False
                        break
    if ok:
        ans = max(ans,cnt)
print(ans)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,Q = map(int,readline().split())
ki = []
for i in range(N-1):
    ki.append(list(map(int,readline().split())))
co = []
for i in range(Q):
    co.append(list(map(int,readline().split())))
 
ki.sort(key=lambda x: x[1])

kid = deque(ki)
ver = []
for i in range(N):
    ver.append([0,False])
 
for i in range(Q):
    ver[co[i][0]-1][0] += co[i][1]

ver[0][1] = True

while len(kid) != 0:
    k = kid.popleft()
    if ver[k[0]-1][1] == True:
        ver[k[1]-1][0] += ver[k[0]-1][0]
        ver[k[1]-1][1] = True
    elif ver[k[1]-1][1] == True:
        ver[k[0]-1][0] += ver[k[1]-1][0]
        ver[k[0]-1][1] = True
    else:
        kid.append(k)

ans = [ver[i][0] for i in range(N)]

print(' '.join(map(str,ans)))


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,Q = map(int,readline().split())
ki = []
for i in range(N-1):
    ki.append(list(map(int,readline().split())))
co = []
for i in range(Q):
    co.append(list(map(int,readline().split())))
 
ki.sort(key=lambda x: x[1])

kid = deque(ki)
ver = []
check = []
for i in range(N):
    ver.append(0)
    check.append(False)
 
for c in co:
    ver[c[0]-1] += c[1]

check[0] = True

kid2 = deque()

while len(kid) != 0:
    k = kid.popleft()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid2.append(k)

while len(kid2) != 0:
    k = kid2.pop()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid2.appendleft(k)


print(' '.join(map(str,ver)))
### BUGGY CODE ###

N = int(input())
s = []
for i in range(N):
    s.append(sorted(input()))

cnt = 0
for i in range(N):
    for j in range(N):
        if i >= j:
            continue
        if s[i] == s[j]:
            cnt += 1

print(cnt)

### FIXED CODE ###

import math
from collections import Counter

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N = int(input())
s = []
for i in range(N):
    s.append(''.join(sorted(input())))

c = Counter(s)
l = len(c.most_common())
a = c.most_common()

cnt = 0
for i in range(l):
    if a[i][1] < 2:
        continue
    cnt += combinations_count(a[i][1], 2)

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

N=int(input())

for h in range(1, 3501):
    for w in range(1, 3501):
        if 4*h*w-N*(h+w)!=0:
            n=N*h*w/(4*h*w-N*(h+w))
            if n.is_integer() and n>0:
                print(h,int(n),w)
                exit()


### FIXED CODE ###

N=int(input())

for h in range(1, 3501):
    for w in range(1, 3501):
        if 4*h*w-N*(h+w)!=0:
            n=N*h*w/(4*h*w-N*(h+w))
            if n.is_integer() and n>0:
                print(h,int(n),w)
                exit()
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

for s in sys.stdin:
  d = int(s)
  prime_list = range(d)[2:]
  for e in prime_list[2:]:
    lis = [ f for f in prime_list if f < e ]
    if len( [ 1 for g in lis if e % g == 0] ) > 0 :
      prime_list.remove(e)
  print len(prime_list)

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

def calc_prime(n):
  p_list = [True]*n
  p_list[0] = p_list[1] = False
  for i in xrange(2,int(n**0.5)+1):
    if p_list[i]:
      for j in xrange(i*i,n,i):
        p_list[j] = False
  return [ i for i in xrange(2,n) if p_list[i] ]

prime_list = calc_prime(999999)
for s in sys.stdin:
  d = int(s)
  print len([prime_list[i] for i in range(len(prime_list)) if prime_list[i] <= d ])
### BUGGY CODE ###

from itertools import accumulate
from collections import defaultdict

N,K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
A = [0]+[i-1 for i in A]
sumA = list(accumulate(A))
sumA = [i % K for i in sumA]
x = sumA[:K]
modmap = defaultdict(int)
ans = 0
for i in x:
    modmap[i] += 1

for i in range(K):
    t = modmap[i]
    ans += t * (t-1) // 2

for i in range(N-K+1):
    modmap[sumA[K+i]] += 1
    modmap[sumA[i]] -= 1
    ans += modmap[sumA[K+i]]-1

print(ans)

### FIXED CODE ###

import sys
from itertools import accumulate
from collections import defaultdict
input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))
a = [i-1 for i in a]
suma = [0]+list(accumulate(a))
suma = [i%k for i in suma]
rem = defaultdict(int)
ans = 0
if k > n:
    for i in range(n+1):
        x = suma[i]
        rem[x] += 1
    for s in rem.values():
        ans += s*(s-1)//2
    print(ans)
    exit()
for i in range(k):
    x = suma[i]
    rem[x] += 1
for s in rem.values():
    ans += s*(s-1)//2
for i in range(n-k+1):
    rem[suma[i]%k] -= 1
    rem[suma[i+k]%k] += 1
    ans += rem[suma[i+k]] -1
print(ans)
### BUGGY CODE ###

import itertools
n, m, R = map(int, input().split())
r = list(map(int, input().split()))
INF = float("inf")
G = [[INF] * n for i in range(n)]

for i in range(m):
    a, b, c = map(int, input().split())
    G[a - 1][b - 1] = c
    G[b - 1][a - 1] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            G[i][j] = min(G[i][k] + G[k][j], G[i][j])

num = INF
for per in itertools.permutations(r):
    rec = 0
    pre = per[0] - 1
    for j in range(1, len(r)):
        rec += G[pre][per[j] - 1]
        pre = per[j] - 1

    num = min(rec, num)

print(num)

### FIXED CODE ###

import itertools
n, m, R = map(int, input().split())
r = list(map(int, input().split()))
INF = float("inf")
G = [[INF] * n for i in range(n)]

for i in range(m):
    a, b, c = map(int, input().split())
    G[a - 1][b - 1] = c
    G[b - 1][a - 1] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            G[i][j] = min(G[i][k] + G[k][j], G[i][j])

num = INF
for per in itertools.permutations(r):
    rec = 0
    pre = per[0] - 1
    for j in range(1, len(r)):
        rec += G[pre][per[j] - 1]
        pre = per[j] - 1
        if rec > num:
            break

    num = min(rec, num)

print(num)
### BUGGY CODE ###

h,w=map(int,input().split())
a = []
for i in range(h):
  l = input()
  l = list(l)
  a.append(l)
arrh = []
arrw = []
for i in range(w):
  arr = []
  c = 0
  k = 0
  while k < h:
    if a[k][i] == "#":
      for j in range(c):
        arr.append(c)
      arr.append(0)
      c = 0
    elif a[k][i] == "." and k == h - 1:
      for j in range(c+1):
        arr.append(c+1)
    elif a[k][i] == ".":
      c += 1
    k += 1
  arrh.append(arr)
for i in range(h):
  arr = []
  c = 0
  k = 0
  while k < w:
    if a[i][k] == "#":
      for j in range(c):
        arr.append(c)
      arr.append(0)
      c = 0
    elif a[i][k] == "." and k == w - 1:
      for j in range(c+1):
        arr.append(c+1)
    elif a[i][k] == ".":
      c += 1
    k += 1
  arrw.append(arr)
arrf = []
for i in range(h):
  for j in range(w):
    arrf.append(arrh[j][i] + arrw[i][j] - 1)
print(max(arrf))

### FIXED CODE ###

import numpy as np
h,w = map(int,input().split())
s = np.array([[1 if i == "." else 0 for i in input()] for j in range(h)])
l,r,u,d = np.zeros((h,w)),np.zeros((h,w)),np.zeros((h,w)),np.zeros((h,w))
for i in range(h):
  u[i] = (u[i-1]+1)*s[i]
  d[-i-1] = (d[-i]+1)*s[-i-1]
for i in range(w):
  l[:,i] = (l[:,i-1]+1)*s[:,i]
  r[:,-i-1] = (r[:,-i]+1)*s[:,-i-1]
print(int(np.max(l+r+u+d))-3)