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

s = str(input())
q = int(input())
b = 1
for i in range(q):
  la = input()
  if la == "1":
    b ^= 1
  else:
    a,f,c = la.split()
    if f == "1":
      s = c+s if b==1 else s+c
    else:
      s = s+c if b==1 else c+s
      
print(s if b==1 else s[::-1])

### FIXED CODE ###

s = str(input())
q = int(input())
b = 1
x=''
y=''
for i in range(q):
  la = input()
  if la == "1":
    b ^= 1
  else:
    a,f,c=la.split()
    if f == "1":
      if b==1:x=c+x
      else:y=y+c
    else:
      if b==1:y=y+c
      else:x=c+x
s = x+s+y      
print(s if b==1 else s[::-1])
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin
from itertools import count, combinations

for case in count(1):
    W = int(stdin.readline().strip())
    if not W:
        break

    N = int(stdin.readline().strip())
    data = []
    for _ in xrange(N):
        data.append([int(s) for s in stdin.readline().strip().split(',')])

    value, weight = 0, W
    for i in xrange(1, N+1):
        for cmb in combinations(data, i):
            tv, tw = 0, 0
            for v, w in cmb:
                tv += v
                tw += w
            if W >= tw and (tv > value) or (tv == value and tw < weight):
                value, weight = tv, tw

    print('Case {}:\n{}\n{}'.format(case, value, weight))

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin
from itertools import count

def douteki(limit, data):
    V = [[0 for w in xrange(limit+1)] for i in xrange(len(data)+1)]
    W = [[0 for w in xrange(limit+1)] for i in xrange(len(data)+1)]
    for i in xrange(len(data)+1):
        for w in xrange(limit+1):
            diff = w - data[i-1][1]
            if i - 1 >= 0 and diff >= 0:
                v1 = V[i-1][diff] + data[i-1][0]
                w1 = W[i-1][diff] + data[i-1][1]
            else:
                v1 = 0
                w1 = 0
            v2 = V[i-1][w]
            w2 = W[i-1][w]

            V[i][w], W[i][w] = (v1, w1) if v1 >= v2 else (v2, w2)
    return V[-1][-1], W[-1][-1]

for case in count(1):
    W = int(stdin.readline())
    if not W:
        break

    N = int(stdin.readline())
    data = []
    for _ in xrange(N):
        data.append([int(s) for s in stdin.readline().split(',')])

    value, weight = douteki(W, data)
    print('Case {}:\n{}\n{}'.format(case, value, weight))
### BUGGY CODE ###

n,a,b = map(int,input().split())
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
v = int(pow(2,n,10**9+7)-1-cmb(n,a,10**9+7)-cmb(n,b,10**9+7))
if v >= 0:
    print(v)
else:
    print(v+10**9+7)

### FIXED CODE ###

n,a,b = map(int,input().split())
def cmb(n, r, mod):
    x = 1 
    y = 1
    for i in range(r):
        x = x*(n-i)%(mod)
    for i in range(1,r+1):
        y = y*i%(mod)
    return x * pow(y,mod-2,mod) %mod

v = int(pow(2,n,10**9+7)-1-cmb(n,a,10**9+7)-cmb(n,b,10**9+7))
if v >= 0:
    print(v)
else:
    if v+10**9+7 >= 0:
        print(v+10**9+7)
    else:
        print(v+2*(10**9+7))
### BUGGY CODE ###

import math

x = int(input())


def check(x):
    i = 1
    while True:
        for j in range(1, i + 1):
            if (i == j):
                continue
            elif (x % (i - j) == 0) and (x == ((i ** 5) - (j ** 5))):
                print(i, j)
                return
            elif (x % (i + j) == 0) and ( x == ((i ** 5) + (j ** 5))):
                print(i, -j)
                return
        i = i + 1

check(x)

### FIXED CODE ###

import math

x = int(input())


def check(x):
    i = 1
    while True:
        for j in range(i):
            if (i == j):
                continue
            elif (x % (i - j) == 0) and (x == ((i ** 5) - (j ** 5))):
                print(i, j)
                return
            elif (x % (i + j) == 0) and ( x == ((i ** 5) + (j ** 5))):
                print(i, -j)
                return
        i = i + 1

check(x)
### BUGGY CODE ###

N = int(input())
A = (input().split())
B = []
C = 0
for i in range(N + 1):
  B.append(A.count(str(i)))
  C += int(B[i] * (B[i] - 1) / 2)
for j in range(N):
  print(0 if B[int(A[j])] < 2 else C + 1 - B[int(A[j])])

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
B = collections.Counter(A)
L = {key:(B[key] * (B[key] - 1) // 2) for key in B}
total = sum(L.values())
#print(f"A = {A}\nB = {B}\nL = {L}\ntotal = {total}")
[print(total if L[i] == 0 else total - L[i] + ((B[i] - 1) * (B[i] - 2) // 2)) for i in A]
### BUGGY CODE ###

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

for i in range(Q):
  q = input().split()
  
  if int(q[0])==1:
    S = S[::-1]
  else:
    if int(q[1])==1:
      S = q[2]+S
    else:
      S = S+q[2]

print(S)

### FIXED CODE ###

S = input()
Q = int(input())
T = ""

for q in range(Q):
  que = input().split()
  if que[0]=="1":
        S,T = T,S
  else:
    if que[1]=="1":
      T+=que[2]
    else:
      S+=que[2]

print(T[::-1]+S)
### BUGGY CODE ###

N = int(input())

tmp = []
counter = 0
for i in range(N):
    new_str = ''.join(list(sorted(str(input()))))
    tmp.append(new_str)
    for j in range(i):
        if str(new_str) == str(tmp[j]):
            counter += 1

print(counter)

### FIXED CODE ###

N = int(input())

tmp = []
counter = 0
for i in range(N):
    new_str = ''.join(sorted(str(input())))
    
    #if i != 0:
    #    counter += tmp.count(new_str)
    tmp.append(new_str)

import collections
c = collections.Counter(tmp)

#new_str_list = [i for i in new_str = ''.join(list(sorted(str(input()))))]
#print(new_str_list)

    #for j in range(i):
    #    if str(new_str) == str(tmp[j]):
    #        counter += 1
value = list(c.values())
#print(value)

for j in value:
    for k in range(j):
        counter += k

print(counter)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
sys.setrecursionlimit(10 ** 6)

def main():
    n = int(input())
    adj_list = [[] for i in range(n)]
    for i in range(n - 1):
        a1, b1 = map(int, input().split())
        adj_list[a1 - 1].append(b1 - 1)
        adj_list[b1 - 1].append(a1 - 1)
    path = dfs(0, -1, adj_list, n)
    assert len(path) >= 2
    fpath = len(path) - len(path) // 2
    cut = path[fpath - 1:fpath + 1]
    f = dfs2(0, -1, adj_list, n, cut)
    s = dfs2(n - 1, -1, adj_list, n, cut)
    assert f + s == n
    print("Fennec" if f > s else "Snuke")

def dfs(now, prev, adj_list, n):
    if now == n - 1:
        return [now]
    for next in adj_list[now]:
        if next == prev:
            continue
        p = dfs(next, now, adj_list, n)
        if p is not None:
            return [now] + p

def dfs2(now, prev, adj_list, n, cut):
    size = 1
    for next in adj_list[now]:
        if next == prev:
            continue
        if {now, next} == set(cut):
            continue
        s = dfs2(next, now, adj_list, n, cut)
        size += s
    return size

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

import sys
sys.setrecursionlimit(10 ** 6)

def main():
    n = int(input())
    adj_list = [[] for i in range(n)]
    for i in range(n - 1):
        a1, b1 = map(int, sys.stdin.readline().split())
        adj_list[a1 - 1].append(b1 - 1)
        adj_list[b1 - 1].append(a1 - 1)
    path = list(reversed(dfs(0, -1, adj_list, n)))
    assert len(path) >= 2
    fpath = len(path) - len(path) // 2
    cut = set(path[fpath - 1:fpath + 1])
    f = dfs2(0, -1, adj_list, n, cut)
    s = dfs2(n - 1, -1, adj_list, n, cut)
    assert f + s == n
    print("Fennec" if f > s else "Snuke")

def dfs(now, prev, adj_list, n):
    if now == n - 1:
        return [now]
    for next in adj_list[now]:
        if next == prev:
            continue
        p = dfs(next, now, adj_list, n)
        if p is not None:
            p.append(now)
            return p

def dfs2(now, prev, adj_list, n, cut):
    size = 1
    for next in adj_list[now]:
        if next == prev:
            continue
        if {now, next} == cut:
            continue
        s = dfs2(next, now, adj_list, n, cut)
        size += s
    return size

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

n = int(input())
m = str(input())

red = []
white = []
for i in range(n):
    if m[i] == 'R':
        red.insert(0, i)
    else:
        white.append(i);

re = len(red)
wh = len(white)
if re == 0 or wh == 0:
    print(0);
else:
    k = 0;
    for j in range(min(re,wh)):
        if red[j] > white[j]:
            k += 1;

    print(k);

### FIXED CODE ###

n = int(input())
m = str(input())

red = m.count('R')

con = 0;

for i in range(red):
    if m[i] == 'W':
        con += 1
print(con);
### BUGGY CODE ###

R,G,B,N=(int(i) for i in input().split())
import math
answer=0
for r in range(0,math.floor(N/R)+1):
    for g in range(math.floor(N/G)+1):
        if R*r+G*g>N:
            break
        if (N-R*r-G*g)%B==0:
            answer+=1

print(answer)




### FIXED CODE ###

R,G,B,N=(int(i) for i in input().split())
import math
answer=0
for r in range(0,math.floor(N/R)+1):
    for g in range(math.floor(N/G)+1):
        sss=R*r+G*g
        if sss>N:
            break
        if (N-sss)%B==0:
            answer+=1
print(answer)
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    if 0 in A:
        print(0)
        return
    prod = 1
    for a in A:
        prod *= a
    if prod > 1000000000000000000:
        print(-1)
        return
    print(prod)
main()

### 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 *= i
    if ans > 10**18:
        print(-1)
        exit()
 
print(ans)
### BUGGY CODE ###

import numpy as np
n, m = map(int, input().split())
money = []
for i in range(n):
  a, b = map(int, input().split())
  money += [a] * b

money.sort()
print(np.sum(money[0:m]))

### FIXED CODE ###

n, m = map(int, input().split())
money = []
for i in range(n):
  a, b = map(int, input().split())
  money.append({"a":a, "b":b})

bsum = 0
money.sort(key=lambda x: x["a"])
for i in range(n):
  bsum0 = bsum
  bsum += money[i]["b"]
  if m <= bsum:
    num = i
    break

ans = 0
for j in range(num):
  ans += money[j]["a"] * money[j]["b"]
ans += (m-bsum0) * money[num]["a"]
print(ans)
### BUGGY CODE ###

S = input()
ans = 0
for i in range(len(S)):
    for j in range(i,len(S)):
        s = int(S[i:j+1])
        # print(s)
        if s%2019==0:
            ans += 1
print(ans)

### FIXED CODE ###

S = input()
dp = [0 for i in range(2019)]
dp[0] = 1

num = 0
for i,j in enumerate(S[::-1]):
    num += int(j)*(pow(10,i,2019))
    dp[num%2019] += 1

ans = 0
for m in dp:
    if m >= 2:
        ans += int(m*(m-1)/2)
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
from collections import defaultdict 
d=defaultdict(list)
for i in range(m):
    a,b=map(int,input().split())
    a-=1 
    b-=1 
    d[a].append(b)
    d[b].append(a)
q=[0]
dist=[0]*n 
vis=[0]*n 
vis[0]=1 
while q:
    t=q.pop(0)
    for i in d[t]:
        if not vis[i]:
            vis[i]=1 
            dist[i]=dist[t]+1 
            q.append(i)
print('POSSIBLE' if dist[n-1]==2 else 'IMPOSSIBLE')

### FIXED CODE ###

n,m=map(int,input().split())
from collections import defaultdict 
d=defaultdict(list)
from collections import deque 
for i in range(m):
    a,b=map(int,input().split())
    a-=1 
    b-=1 
    d[a].append(b)
    d[b].append(a)
q=[0]
dist=[0]*n 
vis=[0]*n 
vis[0]=1 
q=deque() 
q.append(0)
while q:
    t=q.popleft()
    for i in d[t]:
        if not vis[i]:
            vis[i]=1 
            dist[i]=dist[t]+1 
            q.append(i)
print('POSSIBLE' if dist[n-1]==2 else 'IMPOSSIBLE')
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b = a[:]
s1 = s2 = 0
for i in range(n):
  c = sum(a[0:i+1])
  if (i % 2 == 0 and c <= 0):
    s1 += abs(c) + 1
    a[i] += abs(c) + 1
  elif(i % 2 == 1 and c >= 0):
    s1 += abs(c) + 1
    a[i] -= abs(c) + 1
for i in range(n):
  c = sum(b[0:i+1])
  if (i % 2 == 0 and c >= 0):
    s2 += abs(c) + 1
    b[i] -= abs(c) + 1
  elif (i % 2 == 1 and c <= 0):
    s2 += abs(c) + 1
    b[i] += abs(c) + 1
print(min(s1,s2))

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
s1 = s2 = su = 0
for i in range(n):
  su += a[i]
  if (i % 2 == 0 and su <= 0):
    s1 += abs(su) + 1
    su = 1
  elif(i % 2 == 1 and su >= 0):
    s1 += abs(su) + 1
    su = -1
su = 0
for i in range(n):
  su += a[i]
  if (i % 2 == 0 and su >= 0):
    s2 += abs(su) + 1
    su = -1
  elif (i % 2 == 1 and su <= 0):
    s2 += abs(su) + 1
    su = 1
print(min(s1,s2))
### BUGGY CODE ###

S = input()
N = len(S)

ans = 0
cnt = [0] * 2019
for i in range(N):
    cnt[int(S[i:]) % 2019] += 1
ans+=cnt[0]
for i in range(1, 2019):
    if cnt[i]>=2:   
        ans += cnt[i] * (cnt[i] - 1) // 2
print(ans)


### FIXED CODE ###

S = list(input())
N = len(S)

ans = 0
cnt = [0] * 2019
a = 1
s = 0

for i in range(N)[::-1]:
    s = int(S[i]) * a + s
    a *= 10
    a = a % 2019
    cnt[s % 2019] += 1
    s = s % 2019

ans += cnt[0]
for i in range(2019):
    ans += cnt[i] * (cnt[i] - 1) // 2
print(ans)
### BUGGY CODE ###

N=int(input())
S=[input() for i in range(N)]

s=set(S)

D={}
for i in s:
    total=0
    for j in S:
        if i==j:
            total+=1
    D[i]=total

V=[]
for value in D.values():
       V.append(value)
m=max(V)

A=[]
for i in D.keys():
    if D[i]==m:
        A.append(i)

B=sorted(A)
for i in B:
    print(i)

### FIXED CODE ###

N=int(input())
S=[input() for i in range(N)]

D={}
for i in range(N):
    try:
        if D[S[i]]>=1:
            D[S[i]]+=1
    except:
        D[S[i]]=1
E=sorted(D.items(),key=lambda x:x[1])
m=E[-1][1]
ans=[]
for i in E:
    if i[1]==m:
        ans.append(i[0])
for i in sorted(ans):
    print(i)
### BUGGY CODE ###

a = list(map(int, input().split()))
b = [list(map(int, input().split())) for i in range(a[0])]

result = []

max_weight = a[1]

def calc(i, queue):
    if len(b) <= i:
        return

    current = b[i]
    # print(queue)
    # print(i - 1)
    prev = queue[-1] if 0 < len(queue) else [0, 0] 
    
    if current[0] + prev[0] <= max_weight:
        result.append(prev[1] + current[1])
    
    next_queue = queue[:]
    next_queue.append([prev[0] + current[0], prev[1] + current[1]])
    # print(next_queue)
    # print(queue)
    calc(i + 1, next_queue)
    calc(i + 1, queue)

calc(0, [])

print(max(result))

### FIXED CODE ###

a = list(map(int, input().split()))
b = [list(map(int, input().split())) for i in range(a[0])]

max_index = a[0]
max_weight = a[1]

dp = [ [0] * (max_weight + 1) for j in range(max_index + 1)]

def solve():
    for i in range(max_index - 1, -1, -1):
        for j in range(max_weight + 1):
            if (j < b[i][0]):
                dp[i][j] = dp[i + 1][j]
            else:
                dp[i][j] = max([dp[i + 1][j], dp[i + 1][j - b[i][0]] + b[i][1]])
    print(dp[0][max_weight])

solve()
### BUGGY CODE ###

n=int(input())
ln=[0]*n
i=0
for a  in range(n):
    while a %2 ==0:
        a/=2
        i+=1
    ln[a-1]=i
print(ln.index(max(ln)))

### FIXED CODE ###

n=int(input())
ans=0
for i in range(7):
    if 2**i<=n:
        ans=2**i
print(ans)
### BUGGY CODE ###

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

count = 0

for i in range(N):
    for j in range(i + 1):
        if Ps[i] > Ps[j]:
            break
        if i == j:
            count+=1

print(count)

### FIXED CODE ###

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

count = 0

minimum = Ps[0]

for i in range(N):
    if minimum >= Ps[i]:
        minimum = Ps[i]
        count+=1

print(count)
### BUGGY CODE ###

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

A.sort()
a=1
b=False
for i in range(N):
    a=a*A[i]
    if a>10**18:
        b=True
        continue

if b==False:
    print(a)
else:
    print(-1)

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    if 0 in A:
        print(0)
        return
    prod = 1
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1)
            return
    print(prod)
    
main()
### BUGGY CODE ###

n = int(input())
monster = sorted(list(map(int,input().split())))
while True:
  tmp = int(monster[-1]/monster[-2])
  monster[-1]-=monster[-2]*tmp
  if monster[-1]<=0:
    monster.pop(-1)
  monster = sorted(monster)
  if len(monster)==1:
    print(monster[0])
    exit()


### FIXED CODE ###

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

n = int(input())
monster = sorted(list(map(int,input().split())))
ans = []
for i in range(n-1):
  g = gcd(monster[i], monster[i+1])
  ans.append(g)
print(min(ans))
### BUGGY CODE ###

n, m = map(int,input().split())
a = [int(input()) for i in range(m)]
dp = [0]*(n+1)
dp[0] = 1
for i in range(1, n+1):
    dp[i] = (dp[i-1]+dp[i-2]) % (10**9+7)
    if i in a:
        dp[i] = 0
print(dp[n])


### FIXED CODE ###

n,m=map(int,input().split())
a=set([int(input()) for i in range(m)])
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:dp[i]=0
print(dp[n])
### BUGGY CODE ###

from collections import Counter
N = int(input())
S = input()
ans = 0
D = Counter(S)
id = 0
dic = {}
for k in D.keys():
    dic[k] = id
    id += 1
m = 0
OB = [-1]*N
for i in range(N):
    if D[S[i]]<=1:
        pass
    else:
        OB[i] = dic[S[i]]
        m = max(m,dic[S[i]])
SSS = []
for j in range(m+1):
    SS = [i for i in range(N) if OB[i]==j]
    SSS.append(SS)
for n in range(len(SSS)):
    lss = len(SSS[n])
    for i in range(lss):
        for j in range(lss):
            if i==j or ans>SSS[n][j]-SSS[n][i] or ans>N-SSS[n][j]:
                continue
            id = 0
            while True:

                if SSS[n][i]+id>=N or SSS[n][j]+id>=N or SSS[n][i]+id>=SSS[n][j]:
                    break
                if S[SSS[n][i]+id]==S[SSS[n][j]+id]:
                    id += 1
                else:
                    break
            ans = max(ans,id)


print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = 0
right = 0
for left in range(N):
    while S[left:right + 1] in S[right + 1:]:
        ans = max(ans, right + 1 - left)
        right += 1
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
H = [int(i) for i in input().split()]

dp = [float("inf") for i in range(N)]
dp[0] = 0
for i in range(N):
    for j in range(1,K+1):
        if i+j >= N:
            break
        dp[i+j] = min(dp[i+j],dp[i]+abs(H[i]-H[i+j]))
    

print(dp[-1])

### FIXED CODE ###

def main():
    n,k = map(int,input().split())
    h = [int(i) for i in input().split()]
    INF =  float('inf')
    dp = [INF for i in range(n)]
    dp[0] = 0
    dp[1] = abs(h[0]-h[1])
    for i in range(2,n):
        dp[i] = min(dp[i-j]+abs(h[i-j]-h[i]) for j in range(1,min(i,k)+1))
    print(dp[n-1])

main()
### BUGGY CODE ###

def prime_factorize(n):
    """Calculate prime factorization and return unique numbers and 1.
    """
    ans = set()
    ans_add = ans.add
    ans_add(1)
    while n % 2 == 0:
        ans_add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            ans_add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        ans_add(n)
    return ans


def main():
    x = int(input())
    # 素因数分解してユニークな因数を取る。
    insu = prime_factorize(x)
    # a^5 - b^5 も a - b も，ある因数の倍数となる。
    # ここは a >= b と仮定すると，a は正でなくては，xが負になっちゃう。

    b_min = -int(x ** (1 / 5))
    for n in insu:
        b = b_min
        while 1:
            a = b
            while 1:
                a += n
                if a < 0:
                    continue
                cand = a ** 5 - b ** 5
                if cand == x:
                    return f'{a} {b}'
                elif cand > x:
                    break
            b += 1


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

def prime_factorize(n):
    """Calculate prime factorization and return unique numbers and 1.
    """
    ans = set()
    ans_add = ans.add
    ans_add(1)
    while n % 2 == 0:
        ans_add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            ans_add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        ans_add(n)
    return ans


def main():
    x = int(input())
    # 素因数分解してユニークな因数を取る。
    insu = prime_factorize(x)
    # a^5 - b^5 も a - b も，ある因数の倍数となる。
    # ここは a >= b と仮定すると，a は正でなくては，xが負になっちゃう。

    b_min = -int(x ** (1 / 5))
    for n in insu:
        b = b_min
        while 1:
            a = b
            while 1:
                a += n
                if a < 0:
                    continue
                cand = a ** 5 - b ** 5
                if cand == x:
                    return f'{a} {b}'
                elif cand > x:
                    break
            b += 1
            if (b + n) ** 5 - b ** 5 > x:
                break


if __name__ == '__main__':
    print(main())
### BUGGY CODE ###

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

G = []
for _ in range(H):
    G.append(list(input()))

L, R, U, B = [], [], [], []
for y in range(H):
    targets = [L, R]
    ranges = [range(W), range(W-1, -1, -1)]
    for target, rng in zip(targets, ranges):
        row = [0] * W
        c = -1
        for x in rng:
            if G[y][x] == "#":
                c = -1
            else:
                c += 1
            row[x] = c
        target.append(row)
for x in range(W):
    targets = [U, B]
    ranges = [range(H), range(H-1, -1, -1)]
    for target, rng in zip(targets, ranges):
        col = [0] * H
        c = -1
        for y in rng:
            if G[y][x] == "#":
                c = -1
            else:
                c += 1
            col[y] = c
        target.append(col)

max_light = 0
for y in range(H):
    row = [0] * W
    for x in range(W):
        light = L[y][x] + R[y][x] + U[x][y] + B[x][y] + 1
        max_light = max(light, max_light)
print(max_light)


### FIXED CODE ###

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

G = []
for _ in range(H):
    G.append(list(input()))

L, R, U, B = [], [], [], []
for y in range(H):
    targets = [L, R]
    ranges = [range(W), range(W-1, -1, -1)]
    for target, rng in zip(targets, ranges):
        row = [0] * W
        c = -1
        for x in rng:
            if G[y][x] == "#":
                c = -1
            else:
                c += 1
            row[x] = c
        target.append(row)
for x in range(W):
    targets = [U, B]
    ranges = [range(H), range(H-1, -1, -1)]
    for target, rng in zip(targets, ranges):
        col = [0] * H
        c = -1
        for y in rng:
            if G[y][x] == "#":
                c = -1
            else:
                c += 1
            col[y] = c
        target.append(col)

max_light = 0
for y in range(H):
    for x in range(W):
        light = L[y][x] + R[y][x] + U[x][y] + B[x][y] + 1
        max_light = max(light, max_light)
print(max_light)