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

s = input()
n = int(input())
for i in range(n):
    qs = input()
    if len(qs) == 1:
        s = s[::-1]
    else:
        if int(qs[1:-2]) == 1:
            s = qs[-1] + s
        else:
            s = s + qs[-1]

print(s)

### FIXED CODE ###


#import numpy as np
s = input()
n = int(input())
#qt = np.ones((n),dtype=np.int32)
#qf = np.zeros((n),dtype=np.int64)
#qc = [''] * n

mode = False
#mode = True : f1->s=c+s,f2->s=s+c
#mode = False : f1->s=s+c,f2->s=c+s

front = ''
back = ''
for i in range(n):
    qs = input()
    if len(qs) == 1:
        mode = not mode
        #s = s[::-1]
        #pass
    else:
        #qt[i] = 2
        #qf[i] = int(qs[1:-2])
        #qc[i] = qs[-1]
        if not mode:
            if int(qs[2]) == 1:
                front += qs[4]
                #s = qs[4] + s
            else:
                back += qs[4]
                #s = s + qs[4]
        else:
            if int(qs[2]) == 1:
                back += qs[4]
                #s = s + qs[4]
            else:
                front += qs[4]
                #s = qs[4] + s


#print(mode,front,back)
#hanten
if mode:
    print(back[::-1] + s[::-1] + front)
#no hanten
else:
    print(front[::-1] + s + back)
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = input()
### ローリングハッシュ rolling hash
import random
# M = 10**9+7
# M = 1<<63 - 1
M = 9007199254740997

b = random.choice(range(1,M))
def rhash_list(s):
    l = [chr(v) for v in range(ord("a"), ord("z")+1)]
    d = {c:i+2 for i,c in enumerate(l)}
    ans = 0
    v = 1
    l = [0]
    for item in s:
        ans += d[item]*v
        v *= b
        ans %= M
        v %= M
        l.append(ans)
    return l
l = rhash_list(s)
if len(set(s))==n:
    ans = 0
else:
    binv = pow(b,M-2,M)
    pows = [None]*(n+1)
    v = 1
    for j in range(n+1):
        pows[j] = v
        v *= binv
        v%= M
#         pow(binv,j,M)
    ans = 0
    from collections import defaultdict
    for i in range(n//2, 0, -1):
        d = defaultdict(list)
        for j in range(n-i+1):
            d[((l[j+i]-l[j])*pows[j])%M].append(j)
        for k,v in d.items():
            if v[0]+i<=v[-1]:
                ans = i
        if ans>0:
            break
print(ans)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = input()
### ローリングハッシュ rolling hash
import random
# M = 10**9+7
# M = 1<<63 - 1
M = 92709568269121

b = random.choice(range(1,M))
def rhash_list(s):
    l = [chr(v) for v in range(ord("a"), ord("z")+1)]
    d = {c:i+2 for i,c in enumerate(l)}
    ans = 0
    v = 1
    l = [0]
    for item in s:
        ans += d[item]*v
        v *= b
        ans %= M
        v %= M
        l.append(ans)
    return l
l = rhash_list(s)
if len(set(s))==n:
    ans = 0
else:
    binv = pow(b,M-2,M)
    pows = [None]*(n+1)
    v = 1
    for j in range(n+1):
        pows[j] = v
        v *= binv
        v %= M
#         pow(binv,j,M)
    ans = 0
    from collections import defaultdict
    for i in range(n//2, 0, -1):
        d = defaultdict(list)
        for j in range(n-i+1):
            d[((l[j+i]-l[j])*pows[j])%M].append(j)
        for v in d.values():
            if v[0]+i<=v[-1]:
                ans = i
        if ans>0:
            break
print(ans)
### BUGGY CODE ###

n = int(input())

string = []
count = 0

for i in range(n):
    string.append(sorted(input()))

for i in range(n):
    for j in range(i+1, n):
        if string[i] == string[j]:
            count += 1

print(count)

### FIXED CODE ###

n = int(input())
 
string = {}
count = 0

for i in range(n):
    base = sorted(input())

    if string.get("".join(base)) != None:
        count += int(string["".join(base)])
        string["".join(base)] += 1
    else:
        string["".join(base)] = 1

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

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

def max_pop(ary):
  max = 0
  ind = 0
  for i,a in enumerate(ary):
    if max < a:
      max = a
      ind = i
  del ary[i]
  return ary

def sum_ary(ary):
  total = 0
  for a in ary:
    total += a
  return total

if n >= len(a):
  print(0)
  exit()
for _ in range(n):
  a = max_pop(a)
print(sum_ary(a))


### FIXED CODE ###

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

a = sorted(a, reverse=True)

def sum_ary(ary):
  total = 0
  for a in ary:
    total += a
  return total

if n >= len(a):
  print(0)
  exit()
del a[:n]
print(sum_ary(a))
### BUGGY CODE ###

import copy
N = int(input())

A, B, C, D, E = [int(input()) for i in range(5)]
Xs = [N, 0, 0, 0, 0, 0]
Fs = [A, B, C, D, E]
Fmin = min(Fs)
c = 0
while True:
    #print(Xs)
    nXs = copy.copy(Xs)
    for i in range(len(Fs)):
        if Xs[i] - Fs[i] > 0:
            nXs[i] -= Fs[i]
            nXs[i+1] += Fs[i]
        else:
            nXs[i] -= Xs[i]
            nXs[i+1] += Xs[i]
        #print(nXs)
    Xs = nXs
    c+=1
    if Xs[1:5] == [Fmin, Fmin, Fmin, Fmin]:
        c+=Xs[0]//Fmin
        Xs[0]%=Fmin
    if sum(Xs[0:5]) == 0:
        break

print(c)

### FIXED CODE ###

N = int(input())
min_ = min([int(input()) for i in range(5)])

suf = 1 if N%min_ != 0 else 0
print(N//min_+4+suf)
### BUGGY CODE ###

N = int(input())
S = input()
S2 = [s == 'W' for s in S]

min_num = N
for i in range(N):
    min_num = min([min_num, sum(S2[:i]) + N - i - sum(S2[i + 1:]) - 1])

print(min_num)


### FIXED CODE ###

N = int(input())
S = input()
total = [0] * (N + 1)
for i in range(N):
    if S[i] == 'W':
        total[i + 1] = total[i] + 1
    else:
        total[i + 1] = total[i]

min_num = min(total[i] + (N - i - 1) - (total[N] - total[i + 1]) for i in range(N))

print(min_num)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
N = int(input())

match = [[-1] * (N) for _ in range(N)]
c = 0
for i in range(N):
    for j in range(i+1, N):
        match[i][j] = c
        c += 1
# print(match)


def get_id(i, j):
    if i > j:
        i, j = j, i
    return match[i][j]


G = {k: [] for k in range(c)}
for i in range(N):
    L = map(int, input().split())
    pid = -1
    for l in L:
        id = get_id(i, l-1)
        if pid != -1:
            G[id].append(pid)
        pid = id

visited = [False]*c
calculated = [False]*c
dp = [-1]*c


def dfs(v):
    if dp[v] >= 0:
        return dp[v]
    visited[v] = True
    dp[v] = 1
    for nxt in G[v]:
        if visited[nxt] is True and calculated[nxt] is False:
            print(-1)
            exit()
        dp[v] = max(dp[v], dfs(nxt)+1)
    calculated[v] = True
    return dp[v]


ans = 0
for i in range(c):
    res = dfs(i)
    ans = max(ans, res)
print(ans)


### FIXED CODE ###

from collections import deque

N = int(input())
L = [deque([int(i)-1 for i in input().split()]) for i in range(N)]

q = deque(range(N))
d = [0 for i in range(N)]
pairs = [-1 for i in range(N)]
while q:
    a = q.popleft()  # qの左端の選手のindexをpopleft
    if len(L[a]) == 0:
        continue
    b = L[a].popleft()

    if pairs[b] == a:  # bのリクエストがaなら
        d[a] = d[b] = max(d[a], d[b]) + 1
        q.append(a)
        q.append(b)
    else:
        pairs[a] = b
print(max(d) if not any(L) else -1)
### BUGGY CODE ###

def main():
  _max = max
  h, w = map(int, input().split())
  s = [input() for _ in range(h)]

  rt = [[-1] * w for _ in range(h + 1)]

  tstart = [-1] * (w)
  for i in range(h):
    si = s[i]
    rti = rt[i]
    ystart = -1
    for j in range(w):
      tj = tstart[j]
      if si[j] == '#':
        if ystart != -1:
          jy = j - ystart
          for k in range(ystart, j):
            rti[k] += jy
          ystart = -1
        if tj != -1:
          itj = i - tj
          for k in range(tj, i):
            rt[k][j] += itj
          tstart[j] = -1
      else:
        if ystart == -1:
          ystart = j
        if tj == -1:
          tstart[j] = i

    if ystart != -1:
      jy = w - ystart
      for k in range(ystart, w):
        rti[k] += jy

  for j in range(w):
    tj = tstart[j]
    if tj != -1:
      itj = h - tj
      for k in range(tj, h):
        rt[k][j] += itj
      tstart[j] = -1

  print(_max(_max(l) for l in rt))

main()

### FIXED CODE ###

h, w = map(int, input().split())
s = [input() + '#' for _ in range(h)]
s.append('#' * w)

yoko = [[0] * w for _ in range(h)]
for i in range(h):
  if s[i][0] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, w + 1):
    if s[i][j] == '#':
      if start != -1:
        for k in range(start, j):
          yoko[i][k] = j - start
        start = -1
    else:
      if start == -1:
        start = j

tate = [[0] * w for _ in range(h)]
for i in range(w):
  if s[0][i] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, h + 1):
    if s[j][i] == '#':
      if start != -1:
        for k in range(start, j):
          tate[k][i] = j - start
        start = -1
    else:
      if start == -1:
        start = j
result = 0
for i in range(h):
  for j in range(w):
    t = yoko[i][j] + tate[i][j] - 1
    if t > result:
      result = t

print(result)
### BUGGY CODE ###

N=int(input())
H = list(map(int, input().split()))
I=[H[i]-H[i+1] for i in range(N-1)]
K=[]
for j in range(N-1):
  if I[j]>=0:
    K.append("a")
  else:
    K.append("b")
S = ''.join(K)
i=0
while "a"*(i+1) in S:
  i+=1
print(i)

### FIXED CODE ###

N=int(input())
H = list(map(int, input().split()))
I=[H[i]-H[i+1] for i in range(N-1)]
a=0
n=0
j=0
while j<N-1:
  if I[j]>=0:
    j+=1
    n+=1
  else:
    j+=1
    a=max(n,a)
    n=0
a=max(n,a)
print(a)
### BUGGY CODE ###

def carriable_baggage(baggage, baggage_num, truck_capacity, truck_num):
    """Return the number of baggae which trucks can carry."""
    laden_baggage = 0
    for i in range(truck_num):
        laden_weight = 0
        while laden_weight + baggage[laden_baggage] <= truck_capacity:
            laden_weight += baggage[laden_baggage]
            laden_baggage += 1
            if laden_baggage == baggage_num:
                return baggage_num
    return laden_baggage

def min_capacity(baggage, baggage_num, truck_num):
    """Return the minimum value of maximum load capacity of trucks."""
    heaviest_baggage = max(baggage)
    average_capacity = sum(baggage) // truck_num
    capacity = max(heaviest_baggage, average_capacity)
    while carriable_baggage(baggage, baggage_num, capacity, truck_num) < baggage_num:
        capacity += 1
    return capacity


import sys

baggage_num, truck_num = map(int, sys.stdin.readline().split())

baggage = list(map(int, sys.stdin))

capacity = min_capacity(baggage, baggage_num, truck_num)

print(capacity)

### FIXED CODE ###

def carriable_baggage(baggage, baggage_num, truck_capacity, truck_num):
    """Return the number of baggae which trucks can carry."""
    laden_baggage = 0
    for i in range(truck_num):
        laden_weight = 0
        while laden_weight + baggage[laden_baggage] <= truck_capacity:
            laden_weight += baggage[laden_baggage]
            laden_baggage += 1
            if laden_baggage == baggage_num:
                return baggage_num
    return laden_baggage

def min_capacity(baggage, baggage_num, truck_num):
    """Return the minimum value of maximum load capacity of trucks."""
    left = 0
    right = 1000000000
    while right - left > 1:
        mid = (left + right) // 2
        v = carriable_baggage(baggage, baggage_num, mid, truck_num)
        if v >= baggage_num:
            right = mid
        else:
            left = mid
    return right


import sys

n, k = map(int, sys.stdin.readline().split())

T = list(map(int, sys.stdin))

P = min_capacity(T, n, k)

print(P)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
from collections import defaultdict

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,Q=MAP()
S=input()

D=defaultdict(lambda: [])
golems=[1]*N

for i in range(N):
    D[S[i]].append(i)

for i in range(Q):
    t,d=input().split()
    if d=='L':
        for j in D[t]:
            if j!=0:
                golems[j-1]+=golems[j]
            golems[j]=0   
    elif d=='R':
        for j in reversed(D[t]):
            if j!=N-1:
                golems[j+1]+=golems[j]
            golems[j]=0

print(sum(golems))


### FIXED CODE ###

# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/exawizards2019/editorial.pdf
・二分探索
"""

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,Q=MAP()
S=input()
TD=[input().split() for i in range(Q)]

# ある位置にいるゴーレムを動かして、左端から外に出ないか判定する
def calc1(m):
    if m==-1:
        return False
    if m==N:
        return True
    idx=m
    s=S[idx]
    for i in range(Q):
        t,d=TD[i]
        if t==s:
            if d=='L':
                idx-=1
            elif d=='R':
                idx+=1
        if idx<0:
            return False
        if idx>=N:
            return True
        s=S[idx]
    return True

# ある位置にいるゴーレムを動かして、右端から外に出ないか判定する
def calc2(m):
    if m==-1:
        return True
    if m==N:
        return False
    idx=m
    s=S[idx]
    for i in range(Q):
        t,d=TD[i]
        if t==s:
            if d=='L':
                idx-=1
            elif d=='R':
                idx+=1
        if idx>=N:
            return False
        if idx<0:
            return True
        s=S[idx]
    return True

low=-1
hi=N
while low+1<hi:
    mid=(hi+low)//2
    if calc1(mid):
        hi=mid
    else:
        low=mid
# 左端にたどり着かない(生き残る)ゴーレムのうち、初期位置が最も左のもの
lowest=hi

low=-1
hi=N
while low+1<hi:
    mid=(hi+low)//2
    if calc2(mid):
        low=mid
    else:
        hi=mid
# 右端にたどり着かない(生き残る)ゴーレムのうち、初期位置が最も右のもの
highest=low

print(max(highest-lowest+1, 0))
### BUGGY CODE ###

from functools import reduce
# python > pypy
MOD = 10**9 + 7
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(x, y):
    return (x * y) // gcd(x, y)

def gcd_list(numbers):
    return reduce(gcd, numbers)

def lcm_list(numbers):
    return reduce(lcm, numbers)

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

lcm_ = lcm_list(a)
b = list(map(lambda x: lcm_//x, a))
ans = 0
for i in range(len(b)):
    ans += b[i]
    ans %= MOD
print(ans)


### FIXED CODE ###

MAX = 1000001

mod = 1000000007

prime = [0 for i in range(MAX)]

max_map = dict()

# function to return a^n

def power(a, n):

    if n == 0:
        return 1
    p = power(a, n // 2) % mod
    p = (p * p) % mod

    if n & 1:
        p = (p * a) % mod
    return p

# function to find the smallest prime
# factors of numbers upto MAX


def sieve():
    prime[0], prime[1] = 1, 1
    for i in range(2, MAX):
        if prime[i] == 0:
            for j in range(i * 2, MAX, i):
                if prime[j] == 0:
                    prime[j] = i
            prime[i] = i

# function to return the LCM modulo M


def lcmModuloM(arr, n):

    for i in range(n):
        num = arr[i]

        temp = dict()

        # temp stores mapping of prime factors
        # to its power for the current element
        while num > 1:

            # factor is the smallest prime
            # factor of num
            factor = prime[num]

            # Increase count of factor in temp
            if factor in temp.keys():
                temp[factor] += 1
            else:
                temp[factor] = 1

            # Reduce num by its prime factor
            num = num // factor

        for i in temp:
            # store the higest power of every prime
            # found till now in a new map max_map
            if i in max_map.keys():
                max_map[i] = max(max_map[i], temp[i])
            else:
                max_map[i] = temp[i]

    ans = 1

    for i in max_map:

        # LCM is product of primes to their
        # higest powers modulo M
        ans = (ans * power(i, max_map[i])) % mod
    return ans


def rep_sqr(base, k, mod):
    if k == 0:
        return 1
    elif k % 2 == 0:
        return (rep_sqr(base, k / 2, mod) ** 2) % mod
    else:
        return (rep_sqr(base, k - 1, mod) * base) % mod

# a^(-1) == a^(m-2)


def flt(a, mod):
    return rep_sqr(a, mod-2, mod)

# Driver code
sieve()

# python > pypy
MOD = 10**9 + 7

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

lcm_ = lcmModuloM(a, n)

b = list(map(lambda x: lcm_ * flt(x, mod), a))
ans = 0
for i in range(len(b)):
    ans += b[i]
    ans %= MOD
print(ans)
### BUGGY CODE ###

n = int(input())
v = [int(i) for i in input().split()]
if len(set(v)) == 1:
    print(int(n / 2))
else:
    v1 = v[0::2]
    v2 = v[1::2]
    v1b = set(v1)
    stop1 = len(v1b)
    A1 = []
    for i in v1b:
        num = v1.count(i)
        A1.append(num)
    A1.sort()
    ans1 = sum(A1[:stop1-1])
    v2b = set(v2)
    stop2 = len(v2b)
    A2 = []
    for t in v2b:
        num = v2.count(t)
        A2.append(num)
    A2.sort()
    ans2 = sum(A2[:stop2-1])
    print(ans1 + ans2)

### FIXED CODE ###

import collections
n = int(input())
v_ = list(map(int,input().split()))
setv = set(v_)
if len(setv) == 1:
    print(n//2)
else: 
    v1 = v_[::2]
    v2 = v_[1::2]
    v1com = collections.Counter(v1)
    v2com = collections.Counter(v2)
    v1com = v1com.most_common()
    v2com = v2com.most_common()
    if v1com[0][0] != v2com[0][0]:
        print(n-v1com[0][1]-v2com[0][1])
    else:
        print(n-v1com[0][1]-max(v1com[1][1],v2com[1][1]))
### BUGGY CODE ###

def binary_search(data, value):
    left = 0            # 探索する範囲の左端を設定
    right = len(data) - 1            # 探索する範囲の右端を設定
    while left <= right:
        mid = (left + right) // 2            # 探索する範囲の中央を計算
        if data[mid] == value:
            # 中央の値と一致した場合は位置を返す
            return mid
        elif data[mid] < value:
            # 中央の値より大きい場合は探索範囲の左を変える
            left = mid + 1
        else:
            # 中央の値より小さい場合は探索範囲の右を変える
            right = mid - 1
    return -1            # 見つからなかった場合

import heapq

n,x,mod = map(int,input().split())
c = []
heapq.heapify(c)
cc = []
sisu = 1
count = 0
while True:
    num = pow(x, sisu, mod)
    if binary_search(c, num) != -1:
        b = cc.index(num)
        l = count - b
        cycle = cc[b:]
        startl = b
        start = cc[:b]
        break
    count += 1
    sisu *= 2
    heapq.heappush(c, num)
    cc.append(num)

# print(cc)
# print(cycle,l)
# print(start,startl)
ans = 0
if n <= startl:
    for i in range(n):
        ans += start[i]
    print(ans)
else:
    ans += sum(start)
    n -= startl
    # print(n)
    syo = n // l
    amari = n % l
    s = [0]*(l+1)
    for i in range(1,l+1):
        s[i] = s[i-1] + cycle[i-1]
    ans += s[l]*syo + s[amari]
    print(ans)

### FIXED CODE ###

def binary_search(data, value):
    left = 0            # 探索する範囲の左端を設定
    right = len(data) - 1            # 探索する範囲の右端を設定
    while left <= right:
        mid = (left + right) // 2            # 探索する範囲の中央を計算
        if data[mid] == value:
            # 中央の値と一致した場合は位置を返す
            return mid
        elif data[mid] < value:
            # 中央の値より大きい場合は探索範囲の左を変える
            left = mid + 1
        else:
            # 中央の値より小さい場合は探索範囲の右を変える
            right = mid - 1
    return -1            # 見つからなかった場合

import heapq

n,x,mod = map(int,input().split())
c = [x]
heapq.heapify(c)
cc = [x]
num = x
count = 1
while True:
    num = pow(num, 2, mod)
    if binary_search(c, num) != -1:
        b = cc.index(num)
        l = count - b
        cycle = cc[b:]
        startl = b
        start = cc[:b]
        break
    count += 1
    heapq.heappush(c, num)
    cc.append(num)

# print(cc)
# print(cycle,l)
# print(start,startl)
ans = 0
if n <= startl:
    for i in range(n):
        ans += start[i]
    print(ans)
else:
    ans += sum(start)
    n -= startl
    # print(n)
    syo = n // l
    amari = n % l
    s = [0]*(l+1)
    for i in range(1,l+1):
        s[i] = s[i-1] + cycle[i-1]
    ans += s[l]*syo + s[amari]
    print(ans)
### BUGGY CODE ###

n,c = map(int, input().split())
x = [0]
xr = [0]
va = [0]
fa_clock = [0]
fa_reclock = [0]

prev = 0
vb = [0 for _ in range(n+1)]
for i in range(n):
    xi,vi = map(int, input().split())
    x.append(xi)
    xr.append(c - xi)
    va.append(vi + prev)
    fa_clock.append(vi + prev - xi)
    fa_reclock.append(vi + prev - xi*2)
    prev += vi
    for j in range(i+1):
        vb[j] += vi
vb.reverse()

maxcal = 0
for ib in range(n+1):
    clock = max(fa_clock[:n+1-ib]) + vb[ib] - 2*xr[-ib]
    reclock = max(fa_reclock[:n+1-ib]) + vb[ib] - xr[-ib]
    ans = max(clock, reclock)
    if maxcal < ans: maxcal = ans
print(maxcal)


### FIXED CODE ###

n,c = map(int, input().split())
x = []
x_r = []
v = []
for i in range(n):
    xi,vi = map(int, input().split())
    x.append(xi)
    x_r.append(c - xi)
    v.append(vi)
x_r.reverse()
x.insert(0, 0)
x_r.insert(0, 0)

score = [0]
score_r = [0]
tmp = 0
for i, vi in enumerate(v):
    tmp += vi
    score.append(tmp - x[i+1])
tmp = 0
for i, vi in enumerate(v[::-1]):
    tmp += vi
    score_r.append(tmp - x_r[i+1])

maxscore = []
maxscore_r = []
tmp = 0
for i, si in enumerate(score):
    tmp = max(tmp, si)
    maxscore.append(tmp)
tmp = 0
for i, si in enumerate(score_r):
    tmp = max(tmp, si)
    maxscore_r.append(tmp)

ans = 0
for i, si in enumerate(score):
    ans = max(si + maxscore_r[n-i] - x[i], ans)
for i, si in enumerate(score_r):
    ans = max(si + maxscore[n-i] - x_r[i], ans)

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

H,W = map(int, input().split())
a = [['#'] * (W+2) for i in range(H+2)]

for h in range(1,H+1):
    ai = input()
    for w in range(1,W+1):
        a[h][w] = ai[w-1]


cnt = 0
for h in range(1,H+1):
    for w in range(1,W+1):
        if a[h][w] == '#':
            cnt += 1


dxy = ([1,0],[0,1],[-1,0],[0,-1])
ans = 0
while cnt < H*W:
    ans +=1
    A = [['#'] * (W+2) for i in range(H+2)]
    for h in range(1,H+1):
        for w in range(1,W+1):
            A[h][w] = a[h][w]
    #print(a)
    for h in range(1,H+1):
        for w in range(1,W+1):
            if a[h][w] == '#':
                for dx,dy in dxy:
                    if A[h+dx][w+dy] == '.':
                        A[h+dx][w+dy] = '#'
                        #print(cnt,A)
                        cnt += 1
    for h in range(1,H+1):
        for w in range(1,W+1):
            a[h][w] = A[h][w]

print(ans)

### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
#a = [['#'] * (W+2) for i in range(H+2)]
cnt = [[-5] * (W+2) for i in range(H+2)]
c = 0
fin = 0
st = deque()
sts = deque()
push, pop = st.append, st.pop
pushs, pops = sts.append, sts.pop
for h in range(1,H+1):
    ai = input()
    for w in range(1,W+1):
        #a[h][w] = ai[w-1]
        if ai[w-1] == '#':
            cnt[h][w] = c
            push([h,w])
            fin += 1
        else:
            cnt[h][w] = -1


dxy = ([1,0],[0,1],[-1,0],[0,-1])

while fin < H*W:
    while st:
        [h,w] = pop()
        for dx,dy in dxy:
            if cnt[h+dx][w+dy] == -1:
                #print(c,fin)
                cnt[h+dx][w+dy] = c+1
                pushs([h+dx,w+dy])
                fin += 1
    c += 1
    while sts:
        [h,w] = pops()
        push([h,w])


print(c)