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

def main():
  from builtins import range
  s = input()
  t = input()
  slen = len(s)
  tlen = len(t)
  dp = [[0] * (tlen + 1) for i in range(slen + 1)]
  for i in range(slen):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    si = s[i]
    for j in range(tlen):
      j1 = j + 1
      dpij = dpi[j]
      if si == t[j]:
        dpi1[j1] = dpij + 1
      else:
        if dpij > dpi[j1]:
          dpi[j1] = dpij
        if dpij > dpi1[j]:
          dpi1[j] = dpij
  result = ''
  i = slen
  j = tlen
  while i > 0 and j > 0:
    if dp[i - 1][j] == dp[i][j]:
      i -= 1
    elif dp[i][j - 1] == dp[i][j]:
      j -= 1
    else:
      result = s[i - 1] + result
      i -= 1
      j -= 1
  print(result)
main()


### FIXED CODE ###

s = input()
t = input()
slen = len(s)
tlen = len(t)
dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
for i in range(slen):
  for j in range(tlen):
    if s[i] == t[j]:
      dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
result = ''
i = slen
j = tlen
while i > 0 and j > 0:
  if dp[i - 1][j] == dp[i][j]:
    i -= 1
  elif dp[i][j - 1] == dp[i][j]:
    j -= 1
  else:
    result = s[i - 1] + result
    i -= 1
    j -= 1
print(result)
### BUGGY CODE ###

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# dp クエリには累積和を用意しておく
N = ir()
S = sr()
Q = ir()
K = lr()
dp_D = np.array([], np.int64)
dp_M = np.array([], np.int64)
cnt = np.zeros(N, np.int64)
for i in range(N):
    s = S[i]
    dp_D += 1
    dp_M += 1
    #print(s)
    if s == 'D':
        dp_D = np.append(dp_D, 0)
        #print(dp_D)
    elif s == 'M':        
        dp_M = np.concatenate([dp_M, dp_D])
    elif s == 'C':
        A = np.zeros(N, np.int64)
        #print(np.bincount(dp_M))
        B = np.bincount(dp_M)
        A[:len(B)] += B
        cnt += A

cnt_cum = cnt.cumsum()
#print(dp_D)
#print(cnt_cum)
for k in K:
    print(cnt_cum[k-1])
#

### FIXED CODE ###

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
S = np.array(list('_' + sr()))
Q = ir()
K = lr()
isD = (S == 'D')
isM = (S == 'M')
isC = (S == 'C')
cumD = isD.cumsum()
cumM = isM.cumsum()

for k in K:
    x = cumD.copy()
    x[k:] -= cumD[:-k]
    x *= isM
    x[k+1:] -= isD[1:-k] * (cumM[k:-1] - cumM[:-k-1])
    answer = (x.cumsum() * isC).sum()
    print(answer)
# 05
### BUGGY CODE ###

a,b,n=map(int,input().split())
ans=0
x=0
y=0
while(x<=n or y<=n):
    ans=max(ans,((a*x)//b - a*(x//b)),((a*y)//b - a*(y//b)))
    x+=b
    y=-(-x//a)
print(ans)


### FIXED CODE ###

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

def f(x):
    return (a*x)//b - a*(x//b)

print(f(min(b-1,n)))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n,k=map(int,input().split())
    A=list(map(int,input().split()))+[0]

    from itertools import accumulate

    for i in range(k):
        B=[0]*(n+1)

        for j in range(n):
            val=A[j]
            #if val==0: continue
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        
        for k in range(n):
            B[k+1]+=B[k]
        A=B

        if A==[n]*n:
            break
    
    

    print(*A[:-1])    
    
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n,k=map(int,input().split())
    A=list(map(int,input().split()))

    for i in range(k):
        B=[0]*(n+1)

        for j in range(n):
            val=A[j]
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        
        for k in range(n):
            B[k+1]+=B[k]
        A=B[:-1]

        if A==[n]*(n):
            break
    
    

    print(*A)    
    
resolve()
### BUGGY CODE ###

K = int(input())
 
def gcd(x, y):
  if y == 0: return x
  else: return gcd(y, x % y)

s = 0
for a in range(1, K+1):
  for b in range(1, K+1):
    d = gcd(a, b)
    for c in range(1, K+1):
      s += gcd(d, c)
      
print(s)

### FIXED CODE ###

import math
K = int(input())
 
s = 0
for a in range(1, K+1):
  for b in range(1, K+1):
    d = math.gcd(a, b)
    for c in range(1, K+1):
      s += math.gcd(d, c)
      
print(s)
### BUGGY CODE ###

import fractions
from functools import reduce

def gcd(*numbers):
   return reduce(fractions.gcd, numbers)

n=int(input())
al=input().split()
al_i = [int(s) for s in al]
m = max(al_i)
gm = 0

for x in range(n):
   t = al_i[x]
   al_i[x] = m
   g = gcd(*al_i)
   al_i[x] = t
   if g>gm:
      gm = g
print(gm)


### FIXED CODE ###

import sys

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

n=int(input())
al=input().split()
al_i = [int(s) for s in al]

if (n == 2):
   print(max(al_i[0],al_i[1]))
   sys.exit()

fg = [0] * n
bg = [0] * n

for x in range(n):
   if (x == 0):
       fg[0] = al_i[0]
       y = 1
   else:
      while y <= x:
         fg[y] = gcd(fg[y-1], al_i[y])
         y += 1

for x in range(n):
   if (x == 0):
      bg[0] = al_i[n-1]
      y = 1
   else:
      while y <= x:
         bg[y] = gcd(bg[y-1], al_i[n-1-y])
         y += 1

m = 0
gm = 0

for x in range(n):
   if (x == 0):
      g = bg[n-2]
   elif (x == n-1):
      g = fg[n-2]
   else:
      g = gcd(fg[x-1],bg[n-2-x])
   if (g > gm):
      gm = g

print(gm)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
ans = 0
now = 1

sum = np.zeros(60,dtype=int)
for i in a:
    aa = np.array(list(map(int,list(str(format(i,'060b'))))))
    
    sum += aa

for i in range(60):
    k = (sum[59-i]*(n-sum[59-i]))%mod
    ans = (ans+(k*now)%mod)%mod
    now = (now*2)%mod

print(ans)

### FIXED CODE ###

#https://atcoder.jp/contests/abc147/submissions/12994515を見た

import numpy as np
n = int(input())
a = np.array(input().split(),dtype=int)
mod = 10**9+7
m2 = [1 for i in range(60)]
for i in range(1,60):
    m2[i] = (m2[i-1]*2)%mod

ans = 0
for i in range(60):
    ni = np.count_nonzero(a&1)
    ans = (ans+ni*(n-ni)%mod*m2[i])%mod
    a >>= 1

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

import sys    
sys.setrecursionlimit(10**5+10)
def flog1(n):
    if A[n] != 0:
        return A[n]
    if n == 0:
        a = 0
    elif n == 1:
        a = abs(h[0] - h[1])
    else:
        a = min(flog1(n - 1) + abs(h[n - 1] - h[n]),flog1(n -2) + abs(h[n - 2] - h[n]))
    A[n] = a
    return a

N = int(input())
h = list(map(int,input().split()))
A = [0] * N
print(flog1(N - 1))

### FIXED CODE ###

N = int(input())
h = list(map(int,input().split()))
dp = [0] * N
dp[1] = abs(h[1] - h[0])
for i in range(N - 2):
    dp[i + 2] = min(dp[i] + abs(h[i] - h[i + 2]),dp[i + 1] + abs(h[i + 1] - h[i + 2]))
print(dp[N - 1])
### BUGGY CODE ###

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

x = list(map(int,input().split()))
y = list(map(int,input().split()))

sum = 0
for i in range(n-1):
  for j in range(i+1,n):
    for k in range(m-1):
      for l in range(k+1,m):
        h = x[j] - x[i]
        v = y[l] - y[k]
        
        sum += h*v

mod = 10 ** 9 + 7
print(sum % mod)

### FIXED CODE ###

mod = 10 ** 9 + 7

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

x = list(map(int,input().split()))
y = list(map(int,input().split()))

sum_h = 0
sum_v = 0
for i in range(n-1):
  sum_h += (x[i+1] - x[i])*(i+1)*(n-i-1)
sum_h = sum_h % mod

for j in range(m-1):
  sum_v += (y[j+1] - y[j])*(j+1)*(m-j-1)
sum_v = sum_v % mod

sum = (sum_h * sum_v) % mod

#print(sum_h,sum_v)
print(sum)
### BUGGY CODE ###

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

Sim = [sum(Pi[0:i]) for i in range(N+1)]
MAX = max(Sim[i+K] - Sim[i] for i in range(N+1-K))

print((MAX+K)/2)




### FIXED CODE ###

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

Sim = [0]
for i in range(0,N):
  Sim.append(Sim[i]+Pi[i])
MAX = max(Sim[i+K] - Sim[i] for i in range(N+1-K))

print((MAX+K)/2)
### BUGGY CODE ###

import sys
import numpy as np

input = sys.stdin.readline

N, W = map(int, input().split())
Weight, V = [], []
for i in range(N):
    w, v = map(int, input().split())
    Weight.append(w)
    V.append(v)

dp = np.zeros((N+1, W+1))

maximum = 0
for i in range(N):
    for w in range(W+1):
        if w >= Weight[i]:
            dp[i+1, w] = dp[i, w - Weight[i]] + V[i]
            maximum = max(maximum, dp[i+1, w])
        else:
            dp[i+1, w] = dp[i, w]
        
print(int(maximum))


### FIXED CODE ###

N, W = map(int, input().split())
#i個目の品物までで重さw以下のときの価値の最大値 
dp = [[0]*(W+1) for _ in range(N+1)]
"""
dp[i, wi:W+1] = max(i番目の重さwiの品物を入れた場合, 入れなかった場合)
         = np.max(dp[i-1, :W-wi+1] + v, dp[i-1, wi:W+1])
"""

for i in range(1, N+1):
    w, v = map(int, input().split())

    for j in range(W+1):
        if j - w >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
        else:
            dp[i][j] = dp[i-1][j]

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

import sys

n, k = map(int, input().split())
s = [int(s) for s in list(input())]
count = 0
tmp = 1
c = []
ans = 0

for i in s:
    if i == tmp:
        count += 1
    else:
        c.append(count)
        tmp = i
        count = 1

c.append(count)
if s[-1] == 0:
    c.append(0)

# kが十分大きいなら
if len(c) <= 2*k+1:
    print(sum(c))
    sys.exit()

for i in range(0, len(c)-2*k, 2):
    ans = max(ans, sum(c[i:i+2*k+1]))

print(ans)


### FIXED CODE ###

import sys

n, k = map(int, input().split())
s = [int(s) for s in list(input())]
count = 0
tmp = 1
c = []
ans = 0

for i in s:
    if i == tmp:
        count += 1
    else:
        c.append(count)
        tmp = i
        count = 1

c.append(count)
if s[-1] == 0:
    c.append(0)

# kが十分大きいなら
if len(c) <= 2*k+1:
    print(sum(c))
    sys.exit()
# TLEしたから尺取りにしたい
# for i in range(0, len(c)-2*k, 2):
#     ans = max(ans, sum(c[i:i+2*k+1]))
ans = total = sum(c[:2*k+1])
for i in range(0, len(c)-2*k-2, 2):
    total = total + c[i+2*k+1] + c[i+2*k+2] - c[i] - c[i+1]
    ans = max(ans, total)

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

k,s=map(int,input().split())
count=0
for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if i+j+l==s:
                count+=1
print(count)

### FIXED CODE ###

k,s=map(int,input().split())
count=0
for i in range(k+1):
    for j in range(k+1):
        if i+j<=s:
            if i+j+k>=s:
                count+=1
print(count)
### BUGGY CODE ###

import sys
f = sys.stdin

_, d = map(int, f.readline().split())

x,y,b = [],[],set()
for line in f:
    xi, yi, bi = map(int, line.split())
    x.append((xi,bi))
    y.append((yi,bi))
    b.update([bi])    
x = sorted(x)
y = sorted(y)
b = sorted(b)


def search(target,bmin,bmax):
    tmax,tmin = None,None
    for i in range(len(target)):
        if bmin <= target[i][1] <= bmax:
            tmin = target[i][0]
            break
    for i in range(len(target) - 1, -1, -1):
        if bmin <= target[i][1] <= bmax:
            tmax = target[i][0]
            break
    return tmax,tmin
    

max_size = i = j = 0
while j < len(b) - 1:
    for k in range(j,-1,-1):
        if b[k] + d < b[j]:
            break
        i = k
    for k in range(i,len(b)):
        if b[i] + d < b[k]:
            break
        j = k

    xmax,xmin = search(x,b[i],b[j])
    ymax,ymin = search(y,b[i],b[j])
    
    max_size = max(max_size,(xmax - xmin) * (ymax - ymin))
    j+=1
    
print(max_size)

### FIXED CODE ###

import math
def segmentTree(dat, f, sentinel):
        pad = 2 ** math.ceil(math.log(len(dat),2))
        dat = [0] * pad + dat + [sentinel] * (pad - len(dat))
        for i in range(pad - 1, 0, -1):
            dat[i] = f(dat[i * 2],dat[i * 2 + 1])
        return dat

def get_lr(b,d):
    l = r = 0
    while r < len(b):
        while b[l] + d < b[r]:
            l += 1
        for r in range(r,len(b)):
            if b[l] + d < b[r]:
                r -= 1
                break
        r += 1
        yield l,r
        l += 1
    
import sys
f = sys.stdin

_, d = map(int, f.readline().split())

xyb = []
for line in f:
    xyb.append(tuple(map(int, line.split())))
from operator import itemgetter
xyb.sort(key=itemgetter(2))

x = [xybi[0] for xybi in xyb]
y = [xybi[1] for xybi in xyb]
b = [xybi[2] for xybi in xyb]

xmax = segmentTree(x,max,sentinel = 0)
xmin = segmentTree(x,min,sentinel = 2000000)
ymax = segmentTree(y,max,sentinel = 0)
ymin = segmentTree(y,min,sentinel = 2000000)


pad = len(xmax) // 2
max_size = 0
def create_index(l,r):
    index = []
    ia = index.append
    while l < r:
        if r & 1:
            r -= 1
            ia(r)
        if l & 1:
            ia(l)
            l += 1
        l >>= 1
        r >>= 1
    return index

for l,r in get_lr(b,d):
    l += pad 
    r += pad
    index = create_index(l,r)

    now_xmax = max(xmax[i] for i in index)
    now_ymax = max(ymax[i] for i in index)
    if max_size < now_xmax * now_ymax:
        max_size = max(max_size,((now_xmax - min(xmin[i] for i in index)) * (now_ymax - min(ymin[i] for i in index))))
print(max_size)
### BUGGY CODE ###

S=input()
Q=int(input())


for i in range(Q):
    Qq=input()
    
    if(Qq.count(' ')>0):
        ti,fi,ci=Qq.split()
        if(fi=='1'):
            S=str(ci)+S
        else:
            S=S+str(ci)
    else:
        S=S[::-1]
print(S)

### FIXED CODE ###

S=input()
Q=int(input())

flip=0
fr=''
ba=''
for i in range(Q):
    Qq=input()
    
    if(Qq.count(' ')>0):
        ti,fi,ci=Qq.split()
        if( flip%2==0   ):
            if(fi=='1'):
                fr=str(ci)+fr
            else:
                ba=ba+str(ci)
        else:
            if(fi=='1'):
                ba=ba+str(ci)
            else:
                fr=str(ci)+fr
    else:
        flip+=1
if(flip%2==0):
    print(fr+S+ba)
else:
    print(ba[::-1]+S[::-1]+fr[::-1])
### BUGGY CODE ###

N=range(int(input()))
S=input()
ans=0
for x in N:
  for y in N:
    for z in N:
      if x-y!=y-z and x<y<z:
        if S[x]!=S[y]!=S[z]!=S[x]:
          ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
S=input()
all=S.count("R")*S.count("G")*S.count("B")

for i in range(N-1):
  for j in range(i,N):
    if 0<=2*i-j<N:
      if S[2*i-j]!=S[i]!=S[j]!=S[2*i-j]:
        all-=1
print(all)
### BUGGY CODE ###

import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
x=input()
m=int(x,2)
c=x.count("1")
for i in range(n):
    che=1
    p=1
    if x[i]=="1":
        p=-1
    if (c+p)==0:
        print(0)
        continue
    nex=(m+p*(2**(n-i-1)))%(c+p)
    while nex!=0:
        nex=nex%str(bin(nex)).count("1")
        che+=1
    print(che)

### FIXED CODE ###

import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
x=input()
m=int(x,2)
c=x.count("1")
l=[1]*(2*10**5+2)
for i in range(1,2*10**5+1):
    l[i]=l[i%str(bin(i)).count("1")]+1
deka=0
for i in range(n):
    if x[i]=="1":
        deka+=pow(2,n-i-1,c+1)
        deka%=c+1
tiisa=0
if c!=1:
    for i in range(n):
        if x[i]=="1":
            tiisa+=pow(2,n-i-1,c-1)
            tiisa%=c-1

for i in range(n):
    if x[i]=="0":
        nex=(deka+pow(2,n-i-1,c+1))%(c+1)
    else:
        if c-1==0:
            nex=-1
        else:
            nex=(tiisa-pow(2,n-i-1,c-1))%(c-1)
    if nex==0:
        print(1)
    elif nex==-1:
        print(0)
    else:
        print(l[nex])
### BUGGY CODE ###

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

if k>100:
    ans=[n]*n
    print(*ans)
    exit()

for _ in range(k):
    pre_cum = [0]*(n+1)
    for i,ai in enumerate(a):
        if i-ai>=0:
            pre_cum[i-ai]+=1
        else:
            pre_cum[0]+=1
        if i+ai<n-1:
            pre_cum[i+ai+1]-=1
        else:
            pre_cum[n]-=1
    a=[]
    tmp=0
    for i in range(n):
        tmp+=pre_cum[i]
        a.append(tmp)

print(*a)


### FIXED CODE ###

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

if k>100:
    ans=[n]*n
    print(*ans)
    exit()

for _ in range(k):
    pre_cum = [0]*(n+1)
    for i,ai in enumerate(a):
        if i-ai>=0:
            pre_cum[i-ai]+=1
        else:
            pre_cum[0]+=1
        if i+ai<n-1:
            pre_cum[i+ai+1]-=1
        else:
            pre_cum[n]-=1
    a=[]
    tmp=0
    for i in range(n):
        tmp+=pre_cum[i]
        a.append(tmp)

print(*a)
### BUGGY CODE ###

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

k = 1000000007

ans = 0
for s in range(len(A)-1):
    ans += A[s]*sum(A[s+1:])

print(ans%k)


### FIXED CODE ###

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

k = 1000000007

sm = sum(A)

ans = 0
for s in range(len(A)-1):
    #ans += A[s]*sum(A[s+1:])
    sm -= A[s]
    ans += A[s]*sm

if ans>1000000007:
    print(ans%k)
else:
    print(ans)
### BUGGY CODE ###

import sys
import numpy as np

input = sys.stdin.readline

N, W = map(int, input().split())

def knapsack(N, W):
    dp = np.zeros((N+1, W+1))
    maximum = 0
    for i in range(N):
        weight, val = map(int, input().split())
        for w in range(W+1):
            if w >= weight:
                dp[i+1, w] = dp[i, w - weight] + val
                maximum = max(maximum, dp[i+1, w])
            else:
                dp[i+1, w] = dp[i, w]
            
    print(int(maximum))

knapsack(N, W)


### FIXED CODE ###

N, W = map(int, input().split())
#i個目の品物までで重さw以下のときの価値の最大値 
dp = [[0]*(W+1) for _ in range(N+1)]
"""
dp[i, wi:W+1] = max(i番目の重さwiの品物を入れた場合, 入れなかった場合)
         = np.max(dp[i-1, :W-wi+1] + v, dp[i-1, wi:W+1])
"""

for i in range(1, N+1):
    w, v = map(int, input().split())

    for j in range(W+1):
        if j - w >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
        else:
            dp[i][j] = dp[i-1][j]

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

import itertools
x = int(input())
l = [0,1,2,3,4,5]
k = x%100
n = x//100
ans = '0'
if n*5>=k:
    c = list(itertools.combinations_with_replacement(l,n))
    for i in c:
        if sum(i)==k:
            ans = '1'
            break
print(ans)

### FIXED CODE ###

import itertools
x = int(input())
k = x%100
n = x//100
ans = 0
if n*5>=k and n!=0:
    ans = 1
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
from collections import deque
a = []
for _ in range(n):
    a.append(list(input()))

count = 0
for x in a:
    count += x.count("#")
#print(count)

b = [[100000 for i in range(m)] for i in range(n)]
#print(a)

x = [0, 0, -1, 1]
y = [-1, 1, 0, 0]

queue = deque([[0,0]])
b[0][0] = 1
while queue:
    now = queue.popleft()

    for i in range(4):
        if now[0] + y[i] < 0 or now[0] + y[i] >= n or now[1] + x[i] < 0 or now[1] + x[i] >= m:
            continue
        if a[now[0]+y[i]][now[1]+x[i]] == '.':
            queue.append([now[0]+y[i],now[1]+x[i]])
            b[now[0]+y[i]][now[1]+x[i]] = min(b[now[0]][now[1]] + 1, b[now[0]+y[i]][now[1]+x[i]])
    a[now[0]][now[1]] = "#"

if b[n-1][m-1] == 100000:
    print(-1)
    exit()

ans = n * m - (b[n-1][m-1] + count)
print(ans)



### FIXED CODE ###

n,m = map(int,input().split())
from collections import deque
a = []
for _ in range(n):
    a.append(list(input()))

count = 0
for x in a:
    count += x.count("#")
#print(count)

b = [[-1 for i in range(m)] for i in range(n)]
#print(a)

x = [0, 0, -1, 1]
y = [-1, 1, 0, 0]
queue = deque([[0,0]])
b[0][0] = 1
while queue:
    now = queue.popleft()
    if now == [n-1,m-1]:
        print(n * m - (b[n-1][m-1] + count))
        exit()
    a[now[0]][now[1]] = "#"
    for i in range(4):
        if 0 <= now[0] + y[i] < n and 0 <= now[1] + x[i] < m and b[now[0]+y[i]][now[1]+x[i]] == -1:
            if a[now[0]+y[i]][now[1]+x[i]] == '.':
                queue.append([now[0]+y[i],now[1]+x[i]])
                b[now[0]+y[i]][now[1]+x[i]] = b[now[0]][now[1]] + 1

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

N, Y = map(int, input().split())
# i: man, j: gosen, k: sen
output_flag=0
for i in range(0, N+1):
    while output_flag==0:
        for j in range(0, N+1-i):
            k = N-i-j
            if 10000*i+5000*j+1000*k==Y:
                print(i, j, k)
                not_output_flag=1
                break
    if output_flag==1:
        break
if output_flag==0:
    print(-1, -1, -1)

### FIXED CODE ###

N, Y = map(int, input().split())
man = -1
gosen = -1
sen = -1
for i in range(0, N+1):
    for j in range(0, N+1-i):
        k = N-i-j
        total = 10000*i+5000*j+1000*k
        if total==Y:
            man = i
            gosen = j
            sen = k
print(man, gosen, sen)
### BUGGY CODE ###

while 1:
  h,w=map(int,raw_input().split())
  if h==w==0: break
  a=[0]*w
  F=[]
  for _ in [0]*h:
    b=raw_input()
    f=[0]*w
    for i in range(w):
      f[i]=[a[i]+1,0][b[i]=="*"]
    F.append(f)
    a=f

  s=0
  for i in range(h):
    f=F[i]
    for j in range(w):
      m=1e9
      for k in range(j+1,w+1):
        m=min(f[j:k])
        s=max(s,m*(k-j))
  print s

### FIXED CODE ###

while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  M = [0]*(h+1)
  a=[0]*w
  for i in range(h):
    x = raw_input()
    b=[0]*w
    sp=-1
    C = [-1]*(h+1)
    for j in range(w):
      if x[j]=="*": c=0
      else: c=a[j]+1
      b[j]=c
      dw=c-sp
      if dw>0: C[sp+1:c+1]=[j]*dw
      elif dw<0:
        for k in range(c+1,sp+1): M[k]=max(M[k],j-C[k])
        C[c+1:sp+1]=[-1]*(-dw)
      sp=c
    for k in range(1,sp+1):
      if C[k]>=0: M[k]=max(M[k],w-C[k])
    a=b
  s=max([a*b for a,b in zip(M, range(h+1))])
  print s
### BUGGY CODE ###

h, w = map(int, raw_input().split())
S = [[c for c in raw_input()] for i in range(h)]
Gh = [[0]*w for i in range(h)]
Gw = [[0]*w for i in range(h)]

for i in range(h):
    ps = 0
    s = S[i]
    for j in range(w):
        if w == j or s[j] == "#":
            ps = 0
        else:
            ps += 1
            Gh[i][j] = ps

for j in range(w):
    ps = 0
    for i in range(h):
        if i == h or S[i][j] == "#":
            ps = 0
        else:
            ps += 1
            Gw[i][j] = ps

for i in range(h-1, -1, -1):
    ps = 0
    for j in range(w-1, -1, -1):
        if S[i][j] == "#":
            ps = 0
        else:
            ps = max(ps, Gh[i][j])
            Gh[i][j] = ps
for j in range(w-1, -1, -1):
    ps = 0
    for i in range(h-1, -1, -1):
        if S[i][j] == "#":
            ps = 0
        else:
            ps = max(ps, Gw[i][j])
            Gw[i][j] = ps
maxLight = 0
for i in range(h):
    for j in range(w):
        maxLight = max(maxLight, Gh[i][j] + Gw[i][j]-1)
print maxLight


### FIXED CODE ###

h, w = map(int, raw_input().split())
S = [[0 if c == "." else 1 for c in raw_input()] for i in range(h)]
L = [[0]*w for i in range(h)]
R = [[0]*w for i in range(h)]
U = [[0]*w for i in range(h)]
D = [[0]*w for i in range(h)]

for i in xrange(h):
    ps = 0
    for j in xrange(w):
        if S[i][j] == 1:
            ps = 0
        else:
            ps += 1
            L[i][j] = ps

for j in xrange(w):
    ps = 0
    for i in xrange(h):
        if S[i][j] == 1:
            ps = 0
        else:
            ps += 1
            U[i][j] = ps

for i in xrange(h-1, -1, -1):
    ps = 0
    for j in xrange(w-1, -1, -1):
        if S[i][j] == 1:
            ps = 0
        else:
            ps += 1
            R[i][j] = ps
for j in xrange(w-1, -1, -1):
    ps = 0
    for i in xrange(h-1, -1, -1):
        if S[i][j] == 1:
            ps = 0
        else:
            ps += 1
            D[i][j] = ps
maxLight = 0
for i in xrange(h):
    for j in xrange(w):
        maxLight = max(maxLight, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)
print maxLight