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

N,M,Q=map(int,input().split())
A=[0 for _ in range(N)]
query=[]
for _ in range(Q):
    query.append(tuple(map(int,input().split())))
list=[]
def dfs(v):
    for i in range(int(v[-1]),M):
        nv=v+str(i)
        if len(nv)==N+1:
            list.append(nv)
        else:
            dfs(nv)
dfs("0")
ans=0
for a in list:
    t_ans=0
    for q in query:
        if int(a[q[1]])-int(a[q[0]])==q[2]:
            t_ans+=q[3]
    ans=max(ans,t_ans)
print(ans)

### FIXED CODE ###

N,M,Q=map(int,input().split())
A=[0 for _ in range(N)]
query=[]
for _ in range(Q):
    query.append(tuple(map(int,input().split())))
list=[]
def dfs(v):
    for i in range(int(v[-1]),M):
        nv=v+str(i)
        if len(nv)==N+1:
            list.append(nv)
        else:
            dfs(nv)
dfs("0")
ans=0
for a in list:
    t_ans=0
    for q in query:
        if int(a[q[1]])-int(a[q[0]])==q[2]:
            t_ans+=q[3]
    ans=max(ans,t_ans)
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed Sep  9 20:56:06 2020

@author: liang
"""

N = int(input())
L = [int(x) for x in input().split()]

L.sort()
ans = 0
#print(L)
for i in range(N-2):
    p = i+2
    for j in range(i+1,N-1):
        while p < N and L[p] < L[i] + L[j] :
            p += 1
        ans += len(L[j+1:p])
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed Sep  9 20:56:06 2020

@author: liang
"""

N = int(input())
L = [int(x) for x in input().split()]

L.sort()
ans = 0
#print(L)
for i in range(N-2):
    #print("1:",i)
    p = i+2
    for j in range(i+1,N-1):
        #print("2",i,j)
        while p < N and L[p] < L[i] + L[j] :
            p += 1
            #print("up")
        #print(p)
        ans += len(L[j+1:p])
print(ans)
### BUGGY CODE ###

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

s = input()
n = len(s)
flag = True
while flag:
    flag = "01" in s or "10" in s
    s = s.replace("01", "").replace("10", "")
print(n-len(s))

### FIXED CODE ###

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

s = input()
n = len(s)
c0 = 0
c1 = 0
for i in s:
    if i == "0":
        c0 += 1
    else:
        c1 += 1
print(2*min(c0, c1))
### BUGGY CODE ###

n, k = map(int, input().split())
*H, = map(int, input().split())
X = [0]
for i in range(1, n):
    x = 1 << 30
    for j in range(1, k+1):
        if i-j >= 0:
            x = min(x, X[i-j]+abs(H[i]-H[i-j]))
    X.append(x)
print(X[n-1])


### FIXED CODE ###

N, K = map(int, input().split())
K = min(N, K)
*h, = map(int, input().split())
a = [abs(h[0] - h[k]) for k in range(K)]
for n in range(N - K):
    a = a[1:] + [min([a[k] + abs(h[n + k] - h[n + K]) for k in range(K)])]
print(a[K - 1])
### BUGGY CODE ###

import fractions
import sys
input = sys.stdin.buffer.readline

k, q = map(int, (input().split()))
d = list(map(int, (input().split())))
sumd = sum(d)

for i in range(q):
    n, x, m = map(int, input().split())
    lcm = sumd * m // fractions.gcd(sumd, m)
    ans = 0
    a = [x]
    for i in range(n-1):
        j = i%k
        a.append(a[-1] + d[j])
        if (a[-2] % m) < (a[-1] % m):
            ans += 1
    print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

k, q = map(int, (input().split()))
d = list(map(int, (input().split())))

for qi in range(q):
    n, x, m = map(int, input().split())
    last = x
    eq = 0
    for i in range(k):
        num = ((n-1-i)+(k-1))//k
        last += (d[i]%m) * num
        if d[i]%m == 0: eq += num
    ans = (n-1) - (last//m - x//m) - eq
    print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
def have_loop(G, V):
    #Gに閉路があるかを判定 Gは隣接グラフによる表現. 0-based Vは頂点数
    status = [0] * V #0 = 未訪問　1 = 訪問中 2 = 訪問済
    def visit(n):
        if status[n] == 1:
            print('Yes')
            exit()
        elif status[n] == 0:
            status[n] = 1
            for v in G[n]:
                visit(v)
            status[n] = 2
        return None
    for v in range(V):
        visit(v)
    print('No')
    return None


N, M = map(int, input().split())
s = input()
G = [[] for _ in range(2 * N)]
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    if s[a] == s[b]:
        G[a].append(b + N)
        G[b].append(a + N)
    else:
        G[a + N].append(b)
        G[b + N].append(a)

have_loop(G, 2 * N)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
s = input()
G = [[] for _ in range(2 * N)]
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    if s[a] == s[b]:
        G[a].append(b + N)
        G[b].append(a + N)
    else:
        G[a + N].append(b)
        G[b + N].append(a)

status = [0] * (2 * N) #0 = 未訪問　1 = 訪問中 2 = 訪問済
def dfs(v):
    if status[v] == 1:
        print('Yes')
        exit()
    elif status[v] == 0:
        status[v] = 1
        for u in G[v]:
            dfs(u)
        status[v] = 2

for v in range(2 * N):
    dfs(v)
print('No')
### BUGGY CODE ###

S=input()
Q=int(input())
R_count=0
for i in range(Q):
  Query=list(filter(lambda a:a!=" ",list(input())))
  if Query[0]=="1":
    R_count+=1
  elif Query[0]=="2":
    if Query[1]=="1":
      if R_count%2==0:
        S=str(Query[2])+S
      else:
        S=S+str(Query[2])
    elif Query[1]=="2":
      if R_count%2==0:
        S=S+str(Query[2])
      else:
        S=str(Query[2])+S
print(S if R_count%2==0 else S[::-1])


### FIXED CODE ###

from collections import deque

S=input()
Q=int(input())
r_flag=False
ans=deque((S))
for i in range(Q):
  Qu=input().split()
  if Qu[0]=="1":
    r_flag=not r_flag
  else:
    if Qu[1]=="1":
      if r_flag==True:
        ans.append(Qu[2])
      else:
        ans.appendleft(Qu[2])
    else:
      if r_flag==True:
        ans.appendleft(Qu[2])
      else:
        ans.append(Qu[2])
ans=list(ans)
print("".join(ans) if r_flag==False else "".join(ans[::-1]))
### BUGGY CODE ###

X = int(input())

CNT = 10000

for a in range(-CNT, CNT):
    for b in range(-CNT, CNT):
        if X == a ** 5 - b ** 5:
            print(a, b)
            exit()


### FIXED CODE ###

X = int(input())

CNT = 500

for a in range(-CNT, CNT):
    for b in range(-CNT, CNT):
        if X == a ** 5 - b ** 5:
            print(a, b)
            exit()
### BUGGY CODE ###

s = list((input()))
ans = 0
for i in range(len(s)):
         for j in range(i,len(s)):
                  tmp = s[i:j+1]
                  tmp = int("".join(tmp))
                  if tmp % 2019 == 0:
                           ans += 1
print(ans)


### FIXED CODE ###

p = 2019
s = [int(i) for i in input()]
p_cnt = 0
 
s = s[::-1]
div_dic = dict(zip(range(p), [0] * p))
tmp = 0

for i in range(len(s)):
    tmp += s[i] * pow(10, i, p)
    tmp %= p
    div_dic[tmp] += 1

for v in div_dic.values():
    p_cnt += v * (v - 1)
p_cnt //= 2
p_cnt += div_dic.get(0)
 
print(p_cnt)
### BUGGY CODE ###

N = int(input())
H = list(map(int,input().split()))
a = 0
if len(H) != 1:
    for i in range(N-1):
        if a == 1:
            break
        if H[i]>H[i+1]:
            if H[i]-1>H[i+1]:
                a = 1
            else:
                if i != 0:
                    H2 = H[:i]
                    if max(H2)>H[i]:
                        a = 1
                
if a == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N = int(input())
H = list(map(int,input().split()))
a = 0
b = 0
if len(H) != 1:
    for i in range(N-1):
        if b < H[i]:
            b = H[i]
        if a == 1:
            break
        if H[i]>H[i+1]:
            if H[i]-1>H[i+1]:
                a = 1
            else:
                if b>H[i]:
                    a = 1
                
if a == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

max_num = 10**6 + 1
prime = [i for i in range(max_num)]
r2_num = int(max_num**(1/2))+1
for i in range(2, r2_num):
  if prime[i] == i:
    for j in range(i**2, max_num, i):
      if prime[j] == j:
        prime[j] = i
def gcd(a, b): # a >= b
  if a%b == 0:
    return b
  else:
    return gcd(b, a%b)

flg_pairwise = True
flg_setwise = False

n = int(input().rstrip())
a_ls = list(map(int, input().rstrip().split(" ")))
gcd_a = 0
primes_a = []
count_prime = [0 for i in range(max_num)]
for a in a_ls:
  gcd_a = gcd(gcd_a, a)
  if gcd_a == 1:
    flg_setwise = True
  tmp_prime = []
  if flg_pairwise:
    while a > 1:
      p = prime[a]
      if tmp_prime == [] or tmp_prime[-1] != p:
        tmp_prime.append(p)
        a = a//p
    for tp in tmp_prime:
      for pa in primes_a:
        if pa == tp:
          flg_pairwise = False
          break
      if flg_pairwise:
        primes_a.append(tp)
      else:
        break
  if flg_setwise and not flg_pairwise:
    break
if flg_pairwise:
  print("pairwise coprime")
elif flg_setwise:
  print("setwise coprime")
else:
  print("not coprime")

### FIXED CODE ###

max_num = 10**6 + 1
prime = [i for i in range(max_num)]
r2_num = int(max_num**(1/2))+1
for i in range(2, r2_num):
  if prime[i] == i:
    for j in range(i**2, max_num, i):
      if prime[j] == j:
        prime[j] = i
def gcd(a, b): # a >= b
  if a%b == 0:
    return b
  else:
    return gcd(b, a%b)

flg_pairwise = True
flg_setwise = False

n = int(input().rstrip())
a_ls = list(map(int, input().rstrip().split(" ")))
gcd_a = 0
primes_a = []
count_prime = [0 for i in range(max_num)]
for a in a_ls:
  gcd_a = gcd(gcd_a, a)
  if gcd_a == 1:
    flg_setwise = True
  tmp_prime = 0
  while a > 1:
    p = prime[a]
    pp = prime[p]
    if p == 0 or pp == 0:
      flg_pairwise = False
      break
    if tmp_prime != p:
      prime[tmp_prime] = 0
      tmp_prime = p
    a = a//p
  if flg_pairwise:
    prime[tmp_prime] = 0
  if flg_setwise and not flg_pairwise:
    break
if flg_pairwise:
  print("pairwise coprime")
elif flg_setwise:
  print("setwise coprime")
else:
  print("not coprime")
### BUGGY CODE ###

s = input()
q = int(input())

for i in range(q) :
  t = list(map(str,input().split()))
  if t[0] == '1' :
    s = s[::-1]
  if t[0] == '2' :
    f = t[1] ; c = t[2]
    if f == '1' :
      s = c + s
    else :
      s = s + c
      
print(s)

### FIXED CODE ###

from collections import deque

ss = input()
q = int(input())
s = deque()

for i in range(len(ss)) :
  s.append(ss[i])

r = 0
for i in range(q) :
  t = list(map(str,input().split()))
  if t[0] == '1' :
    r += 1
  if t[0] == '2' :
    f = t[1] ; c = t[2]
    if r%2 == 0 :
      if f == '1' :
        s.appendleft(c)
      else :
        s.append(c)
    else :
      if f == '2' :
        s.appendleft(c)
      else :
        s.append(c)
        
if r%2 == 1 :
  s.reverse()
  
print(*s,sep='')
### BUGGY CODE ###

from itertools import product
from functools import reduce
import math
 
def gcd(tup):
  return reduce(lambda a, b: math.gcd(a, b), tup)


K = int(input())
lst = range(1, K+1)
memory = {}
Sum = 0


for tup in product(lst, lst, lst):
  if str(sorted(tup)) in memory.keys():
    Sum += memory[str(sorted(tup))]
  else:
    memory[str(sorted(tup))] =gcd(tup)
    Sum += memory[str(sorted(tup))]
  
print(Sum)

### FIXED CODE ###

from math import gcd
k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        ans_=gcd(i,j)
        for l in range(1,k+1):
            ans+=gcd(ans_,l)
print(ans)
### BUGGY CODE ###

N = int(input())
list = []
for i in range(N):
    number = int(input())
    if not number in list:
        list.append(number)
    else:
        list.remove(number)
print(len(list))

### FIXED CODE ###

N = int(input())
Result = set()
for i in range(N):
    number = int(input())
    if  number in Result:
        Result.remove(number)
    else:
        Result.add(number)
print(len(Result))
### BUGGY CODE ###

from itertools import accumulate

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

for j in range(k):
    a01 = [0] * (n + 1)
    for i, ai in enumerate(a):
        l, r = max(0, i - ai), min(i + ai + 1, n)
        a01[l] += 1
        a01[r] -= 1
    a = list(accumulate(a01))
print(*a[:-1])


### FIXED CODE ###

from itertools import accumulate
from math import log2

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

for j in range(k):
    a01 = [0] * (n + 1)
    for i, ai in enumerate(a):
        l, r = max(0, i - ai), min(i + ai + 1, n)
        a01[l] += 1
        a01[r] -= 1
    a = list(accumulate(a01))
    if all(ai == n for ai in a[:-1]):
        break
print(*a[:-1])
### BUGGY CODE ###


import bisect
n = int(input())
L = list(map(int,input().split()))
L.sort()
goukei = []
for i in range(n-1):
    for j in range(i+1,n):
        tmp = L[i] + L[j]
        tm = [tmp,j]
        goukei.append(tm)
ans = 0
for i in range(len(goukei)):
    ans+=  bisect.bisect_left(L[goukei[i][1]+1:],goukei[i][0])

print(ans)


### FIXED CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
n = ii()
l = li()

l.sort()
from bisect import bisect_left as bl

ans = 0
for i in reversed(range(2,n)):
    for k in range(1 ,i):
        ng = l[i] - l[k] + 1
        tmp = bl(l[:k],ng)
        ans += max(0,k-tmp)
print(ans)
### BUGGY CODE ###

N = int(input())
XL = []
flag = [0]*N
for i in range(N):
	xl = list(map(int,input().split()))
	XL.append(xl)
XL.sort()
for i in range(N-1):
	for j in range(i+1,N-i):
		if(flag[i] == 0 ):
			if(XL[i][0]+XL[i][1]>=XL[j][0]):
				flag[j]=1
sum = 0
for i in range(N):
	sum+=flag[i]
print(N-sum)

### FIXED CODE ###

N = int(input())
XL = []
for i in range(N):
	x,l = map(int,input().split())
	S = x + l
	T = x - l
	XL.append((S,T))
XL.sort()
#print(XL)

ans = 0

min = -float("inf")
for s,t in XL:
	if min <= t:
		ans+=1
		min = s
print(ans)
### BUGGY CODE ###

N = int(input())

divisor = []
for i in range(1 , N+1):
    if N % i == 0:
        divisor.append(i)

distance = []
for j in range(int(len(divisor))-1):
    M = (N / int(divisor[j])) + int(divisor[j])
    distance.append(M)

import math

if int(len(divisor)) == 2:
    print(N-1)
else:
    print(math.floor(min(distance))-2)

### FIXED CODE ###

import math

N = int(input())

divisor = []
for i in range(1 , math.floor(N**(1/2))+1):
    if N % i == 0:
        divisor.append(i)

distance = []
for j in range(int(len(divisor))):
    M = (N / int(divisor[j])) + int(divisor[j])
    distance.append(M)

if int(len(divisor)) == 1:
    print(N-1)
else:
    print(math.floor(min(distance))-2)
### BUGGY CODE ###

import numpy as np

N, M = [int(i) for i in input().split()]
A = np.cumsum(np.array(input().split(), dtype=int))
ans = 0

for first in range(N):
    for last in range(first, N):
        if first == last:
            if A[first] % M == 0:
                ans += 1
        else:
            if (A[last] - A[first]) % M == 0:
                ans += 1

print(ans)

### FIXED CODE ###

import numpy as np

N, M = [int(i) for i in input().split()]
A = np.cumsum(np.array(input().split(), dtype=int)) % M
ans = 0

remainder = {}
for i in A:
    if i in remainder:
        remainder[i] += 1
    else:
        remainder[i] = 1

for key in remainder:
    ans += remainder[key] * (remainder[key] - 1) / 2

ans += remainder[0] if 0 in remainder else 0
print(int(ans))
### BUGGY CODE ###

n = int(input())
x = list(map(int,input().split()))
x_sort = sorted(x)
for i in x:
    i_index = x_sort.index(i)
    x_sort.pop(i_index)
    print(x_sort[(n-2) // 2])
    x_sort.insert(i_index, i)


### FIXED CODE ###

n = int(input())
x = list(map(int,input().split()))
x_sort = sorted(x)

meds = x_sort[n//2-1:n//2+1]

for i in x:
    if i <= meds[0]:
        print(meds[1])
    else:
        print(meds[0])
### BUGGY CODE ###

import numpy as np
import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    X = []
    for _ in range(N):
        start, end, pos = map(int, input().split())
        X.append((pos, start, end))

    X = sorted(X, key=lambda x: x[0])
    positions = np.zeros(N+1, dtype=np.int)
    starts = np.zeros(N+1, dtype=np.int)
    ends = np.zeros(N+1, dtype=np.int)
    for i, (pos, start, end) in enumerate(X):
        positions[i] = pos
        starts[i] = start
        ends[i] = end

    positions[N] = -1
    starts[N] = -1
    ends[N] = 10**9

    for _ in range(Q):
        d = int(input())

        before = (positions + d) >= starts
        after = (positions + d) < ends
        check = before * after

        print(positions[check][0])


if __name__ == '__main__':
    main()


### FIXED CODE ###

# ref: https://atcoder.jp/contests/abc128/submissions/5654623

import sys
from bisect import bisect_left

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    closure = []
    for _ in range(N):
        start, end, pos = map(int, input().split())
        closure.append((pos, start, end))

    closure.sort()

    D = [int(input()) for _ in range(Q)]

    ans = [-1] * Q
    skip = [-1] * Q
    for pos, start, end in closure:
        left = bisect_left(D, start - pos)
        right = bisect_left(D, end - pos)

        while left < right:
            if skip[left] == -1:
                ans[left] = pos
                skip[left] = right
                left += 1
            else:
                left = skip[left]

    return ans


if __name__ == '__main__':
    print(*main(), sep='\n')
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

X = input_int()

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        return 2
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            return f
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
        return n
    return n

A_B = prime_factorize(X)
A = 1
while True:
    B = A - A_B
    if A**5 == B**5 + X:
        print(A, B)
        exit()
    A += 1

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

X = input_int()

for a in range(2000):
    A = a - 1000

    for b in range(2000):
        B = b - 1000
        if A ** 5 - B ** 5 == X:
            print("{} {}".format(A, B))
            exit()
### BUGGY CODE ###

from itertools import combinations

N, K = [int(x) for x in input().split()]
prices = [int(x) for x in input().split()]

min_value = 1000 * 1000
for x in combinations(prices, K):
  min_value = min(min_value, sum(x))

print(min_value)

### FIXED CODE ###

N, K = [int(x) for x in input().split()]
prices = sorted([int(x) for x in input().split()])

print(sum(prices[:K]))
### BUGGY CODE ###

#標準入力
N = int(input())
A = list(map(int, input().split()))

A = list(map(lambda x: x%(1000000000+7), A))
_sum = 0
 
for n in range(N-1):
  for i in range(n+1):
    _sum = _sum + (A[n+1] * A[i])
    _sum = _sum % (1000000000+7)
    
print(_sum)

### FIXED CODE ###

#標準入力
N = int(input())
A = list(map(int, input().split()))

#累積和
S = [0]*N
for n in range(N):
  S[n] = S[n-1] + A[n]

_sum = int(0)
for i in range(N-1):
  _sum = _sum + (A[i] * (S[-1] - S[i]))

#modulo
_sum = _sum % (1000000000+7)
  
print(_sum)
### BUGGY CODE ###

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

def func(l,x):
    return [i for i,_x in enumerate(l) if _x == x]

p = []
y = []
number = []


for i in range(m):
    a,b = map(int,input().split())
    c=1
    for j in func(p,a):
        if y[j] < b:
            c+=1
        else:
            number[j] += 1
    p.append(a)
    y.append(b)
    number.append(c)

for i in range(m):
    year=str(p[i]).zfill(6)
    num=str(number[i]).zfill(6)
    print("{0}{1}".format(year,num))



### FIXED CODE ###

import copy

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

cnt = [0]*(10**5+4)

yy = []
yp = []
for _ in range(m):
    a,b = map(int,input().split())
    a,b = b,a
    yy.append([a,0])
    yp.append([a,b])

inlist = copy.deepcopy(yp)
yp.sort()
yy = dict(yy)

for i in range(m):
    cnt[yp[i][1]]+=1
    yy[yp[i][0]] = cnt[yp[i][1]]

for key,value in inlist:
    print("{:06}{:06}".format(value,yy[key]))
### BUGGY CODE ###

H, W = map(int, input().split())
s = []
ans = 0
dp = {}
for i in range(H):
    s.append(input())

def getCount(h, w):
    if s[h][w] == '#':
        return 0
    rCnt = 0
    lCnt = 0
    uCnt = 0
    dCnt = 0
    key = str(h) + str(w)

    # to right
    rkey = key + 'r'
    if rkey in dp:
        rCnt = dp[rkey]
    else:
        for i in range(w+1, W):
            if s[h][i] == '.':
                rCnt += 1
            else:
                break
        dp[rkey] = rCnt

    # to left
    lkey = key + 'l'
    if lkey in dp:
        lCnt = dp[lkey]
    else:
        for i in reversed(range(w)):
            if s[h][i] == '.':
                lCnt += 1
            else:
                break
        dp[lkey] = lCnt

    # to down
    dkey = key + 'd'
    if dkey in dp:
        dCnt = dp[dkey]
    else:
        for i in range(h+1, H):
            if s[i][w] == '.':
                dCnt += 1
            else:
                break
        dp[dkey] = dCnt

    # to up
    ukey = key + 'u'
    if ukey in dp:
        uCnt = dp[ukey]
    else:
        for i in reversed(range(h)):
            if s[i][w] == '.':
                uCnt += 1
            else:
                break
        dp[ukey] = uCnt
    return rCnt + lCnt + uCnt + dCnt + 1

for i in reversed(range(H)):
    for j in reversed(range(W)):
        ans = max(ans, getCount(i, j))

print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
s, ans = [], 0
dpr = [[0] * W for _ in range(H)]
dpl = [[0] * W for _ in range(H)]
dpd = [[0] * W for _ in range(H)]
dpu = [[0] * W for _ in range(H)]

for i in range(H):
    s.append(input())

# to right
for i in range(H):
    for j in reversed(range(W)):
        if j == W-1 and s[i][j] == '.':
            dpr[i][j] = 1
        elif s[i][j] == '#':
            dpr[i][j] = 0
        else:
            dpr[i][j] = dpr[i][j+1] + 1

# to left
for i in range(H):
    for j in range(0, W):
        if j == 0 and s[i][j] == '.':
            dpl[i][j] = 1
        elif s[i][j] == '#':
            dpl[i][j] = 0
        else:
            dpl[i][j] = dpl[i][j-1] + 1

# to down
for i in reversed(range(H)):
    for j in range(W):
        if i == H-1 and s[i][j] == '.':
            dpd[i][j] = 1
        elif s[i][j] == '#':
            dpd[i][j] = 0
        else:
            dpd[i][j] = dpd[i+1][j] + 1

# to up
for i in range(0, H):
    for j in range(W):
        if i == 0 and s[i][j] == '.':
            dpu[i][j] = 1
        elif s[i][j] == '#':
            dpu[i][j] = 0
        else:
            dpu[i][j] = dpu[i-1][j] + 1

for i in reversed(range(H)):
    for j in reversed(range(W)):
        cnt = dpr[i][j] + dpl[i][j] + dpd[i][j] + dpu[i][j] - 3
        ans = max(ans, cnt)

print(ans)