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

n=int(input())
x=list(map(int,input().split()))
t=x
for i in range(n):
    x=x[:i]+x[i+1:]
    x.sort()
    #print(x)
    print(x[(n-1)//2])
    x=t
  

### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
t=sorted(x)
m=n//2
a=t[m-1];b=t[m]
#print(a,b)
for i in range(n):
    if x[i]<=a:
        print(b)
    else:
        print(a)
### BUGGY CODE ###

S=input()
N=len(S)

m=[0]*(N+1)

for i in range(1,N+1):
  m[i]=int(S[i-1:N]) % 2019

dic={}
for i in range(1,N+1):
  if m[i] in dic:
    dic[m[i]].append(i)
  else:
    dic[m[i]]=[i]

c=0
for k,v in dic.items():
  if k == 0:
    c+=len(v)
  else:
    c+=int(len(v)*(len(v)-1)/2)
print(c)

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

import sys
from itertools import permutations, combinations

N=input()
d=[ [ float("inf") for j in range(N+1) ] for i in range(N+1) ] 

hen=[ [ 0 for j in range(N+1) ] for i in range(N+1) ] 
ans=0
for i in range(N):
	L=map(int, sys.stdin.readline().split())
	d[i][i]=0
	for j in range(i+1,N):
		lengh=L[j]
		d[i+1][j+1]=lengh
		d[j+1][i+1]=lengh
		hen[i+1][j+1]=lengh
		ans+=lengh

d[N][N]=0

P=list( permutations(range(1,N+1),3) )

for i,j,k in P:
	a=d[i][j]
	b=d[j][k]
	c=d[i][k]	
	if a+b<c:
		print -1
		quit()
	if a+b==c and hen[i][k]!=0:
		ans-=c
		hen[i][k]=0
		hen[k][i]=0

print ans


### FIXED CODE ###

import numpy as np
N = input()
A = [np.array(map(int,raw_input().split()), dtype=np.int64) for _ in [0]*N]
inf = 10**10
for i in range(N):
    A[i][i] = inf
#print A


result = 0
for i in range(N-1):
    for j, d1 in enumerate(A[i][i+1:], start=i+1):
	#print i,j,A[i], A[j], np.min(A[i]+A[j]),d1
        d2 = np.min(A[i]+A[j])
        if d1 >= d2:
            if d1 > d2:
                print(-1)
                exit()
        else:
            result += d1
print(result)
### BUGGY CODE ###

N,K = list(map(int,input().split()))
p = list(map(int,input().split()))
ans = 0
A = []
B = 0
C = [-1]*10000
for i in range(len(p)-K+1):
    P = p[i:i+K]
    if ans < sum(P):
        ans2 = P
    ans = max(ans,sum(ans2)) 
for j in range(len(ans2)):
  if C[ans2[j]] == -1:
      for k in range(1,ans2[j]+1):
          A.append(k)
      B += sum(A)/ans2[j]
      C[ans2[j]] = sum(A)/ans2[j]
      A = []
  else:
      B += C[ans2[j]]
print(B)

### FIXED CODE ###

from itertools import accumulate
N,K = list(map(int,input().split()))
P = list(map(int,input().split()))
for i in range(N):
    P[i] = 1+(P[i]-1)/2
ruiseki = list(accumulate([0]+P))
ans = 0
for i in range(N-K+1):
    ans = max(ans,ruiseki[i+K]-ruiseki[i])
print(ans)
### BUGGY CODE ###

#d
s=input()
n=len(s)
mod=10**9+7

dp=[[0]*13 for _ in range(n)]
if s[-1]=="?":
    dp[0]=[1,1,1,1,1,1,1,1,1,1,0,0,0]
else:
    dp[0][int(s[-1])]=1

for i in range(1,n):
    ss=s[n-i-1:n]
    ss0=ss[0]
    if ss0!="?":
        for j in range(13):
            dp[i][j] = dp[i-1][(j-int(ss0)*10**i)%13] %mod
    else:
        for j in range(13):
            dp[i][j] = sum( dp[i-1][(j-k*10**i)%13] for k in range(10)) %mod
print(dp[-1][5])

### FIXED CODE ###

#d
def main():
    s=input()
    n=len(s)
    mod=10**9+7
    
    if s[-1]=="?":
        dp=[1,1,1,1,1,1,1,1,1,1,0,0,0]
    else:
        dp=[0]*13
        dp[int(s[-1])]=1
    
    for i in range(1,n):
        imod=10**(i %12)
        ss0=s[n-i-1]
        if ss0!="?":
            dpnew = [ dp[(j-int(ss0)*imod)%13] %mod for j in range(13)]
        else:
            dpnew = [sum( dp[(j-k*imod)%13] for k in range(10)) %mod for j in range(13) ]
        dp=dpnew[:]
    print(dp[5])
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import math
import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,s = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    mod = 998244353
    two = [1]*(n+1)
    for i in range(n):
        two[i+1] = two[i]*2%mod
    dp = np.zeros((n+1,s+1),dtype = int)
    for i,ai in enumerate(a):
        if ai > s:
            continue
        dp1 = np.zeros((n+1,ai),dtype=int)
        dp2 = np.zeros((1,s+1-ai),dtype=int)
        dp3 = np.array([l[:s+1-ai] for l in dp[:-1]])
        dp4 = np.block([[dp2],[dp3]])
        dp5 = np.block([dp1,dp4])
        dp += dp5
        dp[1][ai] += 1
    ans = 0
    for i in range(n+1):
        dpi = dp[i]
        ans = (ans+(dpi[s]*two[n-i])%mod)%mod
    print(ans)
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,s = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    mod = 998244353
    two = [1]*(n+1)
    for i in range(n):
        two[i+1] = two[i]*2%mod
    dp = np.zeros(3010,dtype = int)
    dp[0] = 1
    for i,ai in enumerate(a):
        ndp = dp*2
        ndp[ai:] += dp[:-ai]
        ndp %= mod
        dp = ndp
    print(dp[s])
    return

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

N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
A.reverse()
ansl = []
counter = 0
B = []
for i in range(M):
    BN,CN = map(int,input().split())
    B.append([CN,BN])
B.sort()
for i in A:
    for j in range(len(B)):
        if B[-1][0] > i:
            ansl += [B[-1][0]]*B[-1][1]
            counter += B[-1][1]
            B.pop(-1)
        else:
            break
    ansl.append(i)
    counter += 1
    if counter > N:
        break
ans = 0
for i in range(N):
    ans += ansl[i]
print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
A.reverse()
counter = 0
ans = 0
B = []
for i in range(M):
    BN,CN = map(int,input().split())
    B.append([CN,BN])
B.sort()
for i in A:
    for j in range(len(B)):
        if B[-1][0] > i:
            if counter <= N - B[-1][1]:
                ans += B[-1][0] * B[-1][1]
                counter += B[-1][1]
                B.pop(-1)
            else:
                ans += B[-1][0] * (N - counter)
                counter = N
        else:
            break
    if counter == N:
        break
    else:
        counter += 1
        ans += i
print(ans)
### BUGGY CODE ###

N = int(input())
As = [[int(input()), False] for _ in range(N)]

flag = True
count = 0
while flag:
    flag = False
    prev = -1
    count += 1
    for i, (a, visited) in enumerate(As):
        if visited:
            continue
        if prev < a:
            prev = a
            As[i][1] = True
        else:
            flag = True

print(count)

### FIXED CODE ###

from bisect import bisect_left
from collections import deque

N = int(input())
As = [int(input()) for _ in range(N)]

list_ = deque([As[0]])
for a in As[1:]:
    i = bisect_left(list_, a) - 1
    if i < 0:
        list_.appendleft(a)
    else:
        list_[i] = a
print(len(list_))
### BUGGY CODE ###

# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
S = input().rstrip()
T = input().rstrip()

alpha = 'abcdefghijklmnopqrstuvwxyz'
f = [False]*26
f2 = [False]*26
for i in range(len(S)):
    f[alpha.index(S[i])] = True
for i in range(len(T)):
    f2[alpha.index(T[i])] = True
for i in range(26):
    if not f[i] and f2[i]:
        print(-1)
        sys.exit()


idx = S.index(T[0])
ans = idx+1
for i in range(1,len(T)):
    S = S[idx+1:] + S[:idx+1]
    idx = S.index(T[i])
    ans += idx+1

print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
#ABC138 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

s = input()
t = input()
n = len(s)
m = len(t)
f = [False]*26
f2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(n):
    f[alpha.index(s[i])] = True
for i in range(m):
    f2[alpha.index(t[i])] = True
for i in range(26):
    if not f[i] and f2[i]:
        print(-1)
        quit()
ans = 0
inde = s.index(t[0])
ans += inde+1
for i in range(1,m):
    s = s[inde+1:] + s[:inde+1]
    inde = s.index(t[i])
    ans += inde+1
print(ans)
### BUGGY CODE ###

import numpy as np
N = int(input())
a = list(map(int, input().split()))
b = []
c = np.zeros(N)
ans = 0
for i in reversed(range(1, N+1)):
    j = 2
    count = 0
    while True:
        if i*j <= N:
            count += c[i*j-1]
            j += 1
        else:
            break
    if (a[i-1] % 2 == 0 and count%2 == 1) or (a[i-1] % 2 == 1 and count%2 == 0):
        b.append(i)
        ans += 1
        c[i-1] = 1

print(ans)
if ans != 0:
    print(*b)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

b=[]
M = 0
count = [0 for _ in range(N+1)]
for i in reversed(range(1,N+1)):
    if count[i]%2 == a[i-1]: continue
    else:
        for j in range(1,int(i**0.5)+1):
            if i%j==0:
                count[j]+=1
                if j!=i//j:
                    count[i//j]+=1
        M+=1
        b.append(i)
print(M)
if M!=0:
    print(*b)
### BUGGY CODE ###

X=int(input())
n=0
while n<10**9:
    A=X+(n**5)
    check=(A**0.2)
    if(check==int(check)):
        AnsA=check
        AnsB=n
        print(str(int(AnsA))+" "+str(int(AnsB)))
        break
    else:
        n=n+1

### FIXED CODE ###

X=int(input())

for A in range(-1000,1000):
    for B in range (-1000,1000):
        if(A**5-B**5==X):
            print(A,B)
            break
    else:
        continue
    break
### BUGGY CODE ###

N, M, K = map(int, input().split())
ppp = 10**9 + 7

def expo_div_p(a: int,n: int,p: int):
    if n == 1:
        d = a
    elif n % 2 == 0:
        d = expo_div_p(a, n//2, p)**2 % p
    else:
        d = a * expo_div_p(a, n//2, p)**2 % p
    return d

def combi(x, y, p):
    c = 1
    for i in range(1,y+1):
        c *= (x-i+1) * expo_div_p(i, p-2, p)
        c %= p
    return c

ans = 0
C = combi(N*M-2, K-2, ppp)

for i in range(1,N):
    ans += C * i * (N-i) * M**2
for j in range(1,M):
    ans += C * j * (M-j) * N**2

#print(C)
print(ans % ppp)


### FIXED CODE ###

N, M, K = map(int, input().split())
ppp = 10**9 + 7

#def expo_div_p(a: int,n: int,p: int):
#    if n == 1:
#        d = a
#    elif n % 2 == 0:
#        d = expo_div_p(a, n//2, p)**2 % p
#    else:
#        d = a * expo_div_p(a, n//2, p)**2 % p
#    return d
#
def combi(x, y, p):
    c = 1
    for i in range(1,y+1):
        c *= (x-i+1) * pow(i, p-2, p)
        c %= p
    return c


ans = 0
C = combi(N*M-2, K-2, ppp)

for i in range(1,N):
    ans += C * i * (N-i) * M**2
for j in range(1,M):
    ans += C * j * (M-j) * N**2

#print(C)
print(ans % ppp)
### BUGGY CODE ###


H,W=map(int, input().split())
d = [ [ 100000 for _ in range(W+2)] for _ in range(H+2)]
S = []
S.append('#' * (W+2))
for i in range(H):
    S.append('#'+ input() + '#')
S.append('#' * (W+2))

def SUB(x,y,n):
    d[y][x] = n
    if (S[y-1][x] == '.') and (d[y-1][x] > n+1): SUB(x,y-1,n+1)
    if (S[y][x-1] == '.') and (d[y][x-1] > n+1): SUB(x-1,y,n+1)
    if (S[y+1][x] == '.') and (d[y+1][x] > n+1): SUB(x,y+1,n+1)
    if (S[y][x+1] == '.') and (d[y][x+1] > n+1): SUB(x+1,y,n+1)

dmax = 0
for y in range(1,H+1):
    for x in range(1,W+1):
        if S[y][x] == '.':
            for iy in range(1,H+1):
                for ix in range(1,W+1):
                    d[iy][ix] = 100000
            SUB(x,y,0)
            for iy in range(1,H+1):
                for ix in range(1,W+1):
                    if d[iy][ix] != 100000:
                        if dmax < d[iy][ix]:
                            dmax = d[iy][ix]
print(dmax)





### FIXED CODE ###

from collections import deque

def mk_idx(y,x):
    return y*22+x

H,W=map(int, input().split())
DINF = 100000
S = []
S.append('#' * (W+2))
for i in range(H):
    S.append('#'+ input() + '#')
S.append('#' * (W+2))
dmax = 0
G = [ [] for _ in range( mk_idx(22,22) ) ]
for y in range(1,H+1):
    for x in range(1,W+1):
        if (S[y][x] == '.'):
            if (S[y-1][x] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y-1,x) )
            if (S[y][x-1] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y,x-1) )
            if (S[y+1][x] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y+1,x) )
            if (S[y][x+1] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y,x+1) )

for y in range(1,H+1):
    for x in range(1,W+1):
        if S[y][x] == '.':
            d = [ DINF for _ in range( mk_idx(22,22) ) ]
            d[ mk_idx(y,x) ] = 0
            q = deque( [mk_idx(y,x)] )
            while len(q) != 0:
                v = q.popleft()
                n = d[v];
                dmax = max(dmax, n)
                for nv in G[v]:
                    if d[ nv ] <= n+1 :
                        continue
                    d[ nv ] = n+1
                    q.append(nv)
print(dmax)
### BUGGY CODE ###

N,K,Q=map(int,input().split())
players=[K for _ in range(N)]
for _ in range(Q):
    i=int(input())-1
    players[i]+=1
    for i in range(len(players)):
        players[i]-=1
for num,p in enumerate(players):
    if p<=0:print('No')
    else: print('Yes')

### FIXED CODE ###

N,K,Q=map(int,input().split())
players=[K-Q]*N
for _ in range(Q):
    i=int(input())-1
    players[i]+=1
for num,p in enumerate(players):
    if p<=0:print('No')
    else: print('Yes')
### BUGGY CODE ###

## dijkstraで解く

from collections import deque
import heapq

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

fs = []
for i in range(H):
    r = list(input())
    fs.append(r)

walks = [(-1,0),(1,0),(0,1),(0,-1)]
magics = []
for i in range(-2,3):
    for j in range(-2,3):
        if i==j==0:continue
        if (i,j) not in walks:
            magics.append((i,j))

INF = 1 << 50
N = 10**4
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
q = []
heapq.heappush(q,(0, (ch-1)*N+(cw-1)))
while len(q)>0:
    cnt, n  = heapq.heappop(q)
    h,w = divmod(n, N)
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    # 歩いた
    for dh, dw in walks:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                heapq.heappush(q, (cnt, hn*N+wn))
    # 魔法
    for dh, dw in magics:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                heapq.heappush(q, (cnt+1, hn*N+wn))

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

fs = []
for i in range(H):
    r = list(input())
    fs.append(r)

walks = [(-1,0),(1,0),(0,1),(0,-1)]
magics = []
for i in range(-2,3):
    for j in range(-2,3):
        if i==j==0:continue
        if (i,j) not in walks:
            magics.append((i,j))

INF = 1 << 50
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
q = deque([])
q.appendleft((ch-1,cw-1,0))
while len(q)>0:
    h,w,cnt = q.popleft()
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    for dh, dw in walks:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                q.appendleft((hn, wn, cnt))
    for dh, dw in magics:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                q.append((hn, wn, cnt+1))

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import itertools
import collections
from itertools import accumulate
import math
INF = float("inf")


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def inversion(a):
    "転倒してない数を求める"
    d = {av: i+1 for i, av in enumerate(sorted(a))}
    b = Bit(len(a))
    ans = 0
    for i, av in enumerate(a):
        b.add(d[av], 1)
        ans += b.sum(d[av])
    return ans


def solve(N: int, a: "List[int]"):

    left = 0
    right = max(a)+1
    while right - left > 1:
        mid = (right + left)//2
        acc = [1 if aa >= mid else -1 for aa in a]
        acc = list(accumulate(acc))
        invs = inversion(acc)
        if invs < (N*(N+1)//4 + 1):
            right = mid
        else:
            left = mid
    print(left)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from itertools import accumulate
INF = float("inf")


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def inversion(a):
    "転倒していない組(l, r)の個数を求める"
    d = {av: i+1 for i, av in enumerate(sorted(a))}
    b = Bit(len(a))
    ans = 0
    for i, av in enumerate(a):
        ans += b.sum(d[av])
        b.add(d[av], 1)
    return ans


def solve(N: int, a: "List[int]"):

    def isOK(y):
        acc = (1 if aa >= y else -1 for aa in a)
        acc = tuple([0]) + tuple(accumulate(acc))
        invs = inversion(acc)
        if acc[0] == -1:
            invs -= 1
        return invs < (N*(N+1))//4

    def binary_search(x):

        ng = -1
        ok = len(x)+1

        while abs(ok - ng) > 1:
            mid = (ok + ng)//2
            if isOK(mid):
                ok = mid
            else:
                ng = mid
        return ng, ok

    ng, ok = binary_search(range(max(a)))
    print(ng)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


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

from sys import stdin
import fractions

A, B = [int(x) for x in stdin.readline().rstrip().split()]
gcd = fractions.gcd(A, B)

x = 2
ans = 1
g = 1

while gcd > 1:
    if gcd % x == 0:
        gcd //= x
        if g != x:
            ans += 1
        g = x
    else:
        x += 1

print(ans)


### FIXED CODE ###

from sys import stdin
import fractions

A, B = [int(x) for x in stdin.readline().rstrip().split()]
gcd = fractions.gcd(A, B)
C = []
y = 1
while y ** 2 <= gcd:
    if gcd % y == 0:
        if y >= 2:
            C.append(y)
        if y ** 2 != gcd:
            C.append(gcd // y)
    y += 1

ans = 1
g = 1
C.sort()
for c in C:
    while gcd % c == 0:
        gcd //= c
        if g != c:
            ans += 1
        g = c

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

from collections import deque
d=deque()
for _ in range(int(input())):
  a=int(input())
  try:
    d.remove(a)
  except ValueError:
    d.append(a)
print(len(d))

### FIXED CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
dict = {}
for i in A:
  if i not in dict:
    dict[i] = 1
  else:
    dict[i] += 1
print(len([1 for i in dict.values() if i%2!=0]))
### BUGGY CODE ###

import sys
from bisect import bisect_left
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

h, w = lmi()
s = [input() for i in range(h)]

a = [[] for i in range(h)]
al = [[] for i in range(h)]
b = [[] for i in range(w)]
bl = [[] for i in range(w)]
for i in range(h):
    k = 0
    for j in range(w):
        if s[i][j] == '.':
            k += 1
            if j == w-1:
                a[i].append(k)
                al[i].append(j)
        elif j != 0 and s[i][j-1] == '.':
            a[i].append(k)
            al[i].append(j-1)
            k = 0

for i in range(w):
    k = 0
    for j in range(h):
        if s[j][i] == '.':
            k += 1
            if j == h-1:
                b[i].append(k)
                bl[i].append(j)
        elif j != 0 and s[j-1][i] == '.':
            b[i].append(k)
            bl[i].append(j-1)
            k = 0
'''
print(a)
print(al)
print(b)
print(bl)
'''

ans = 0
for i in range(h):
    k = 0
    c = -1
    for j in range(w):
        if s[i][j] == '.':
            c = a[i][k]
            d = b[j][bisect_left(bl[j], i)]
            #print(c,d)
            ans = max(ans, c+d-1)
        elif j != 0 and s[i][j-1] == '.' and c != -1:
                k += 1
print(ans)


### FIXED CODE ###

import sys
from bisect import bisect_left
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

h, w = lmi()
s = [input() for i in range(h)]

a = [[] for i in range(h)]
al = [[] for i in range(h)]
b = [[] for i in range(w)]
bl = [[] for i in range(w)]
for i in range(h):
    k = 0
    for j in range(w):
        if s[i][j] == '.':
            k += 1
            if j == w-1:
                a[i].append(k)
                al[i].append(j)
        elif j != 0 and s[i][j-1] == '.':
            a[i].append(k)
            al[i].append(j-1)
            k = 0

for i in range(w):
    k = 0
    for j in range(h):
        if s[j][i] == '.':
            k += 1
            if j == h-1:
                b[i].append(k)
                bl[i].append(j)
        elif j != 0 and s[j-1][i] == '.':
            b[i].append(k)
            bl[i].append(j-1)
            k = 0
'''
print(a)
print(al)
print(b)
print(bl)
'''

ans = 0
for i in range(h):
    k = 0
    c = -1
    for j in range(w):
        if s[i][j] == '.':
            c = a[i][k]
            d = b[j][bisect_left(bl[j], i)]
            #print(c,d)
            ans = max(ans, c+d-1)
        elif j != 0 and s[i][j-1] == '.' and c != -1:
                k += 1
print(ans)
### BUGGY CODE ###

import math
H,N=map(int,input().split())
A=[0 for i in range(N)]
B=[0 for i in range(N)]
dp=[[0 for j in range(H)] for i in range(N)]
for i in range(N):
    A[i],B[i]=map(int,input().split())

for i in range(N):
    for j in range(H):
        if i==0:
            dp[i][j]=B[i]*math.ceil((j+1)/A[i])
        elif j+1<=A[i]:
            dp[i][j]=min(dp[i-1][j],B[i])
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][j-A[i]]+B[i])

print(dp[N-1][H-1])

### FIXED CODE ###

import math
H,N=map(int,input().split())
A=[0 for i in range(N)]
B=[0 for i in range(N)]
dp=[[0 for j in range(H)] for i in range(N)]
for i in range(N):
    A[i],B[i]=map(int,input().split())

for i in range(N):
    for j in range(H):
        if i==0:
            dp[i][j]=B[i]*math.ceil((j+1)/A[i])
        elif j+1<=A[i]:
            dp[i][j]=min(dp[i-1][j],B[i])
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][j-A[i]]+B[i])

print(dp[N-1][H-1])