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

s = input()
sc = s[::-1]
n = int(input())
l = [list(input().split()) for i in range(n)]

last = 1

for i in range(n):
    if l[i][0] == '1':
        last = last * -1
    elif l[i][1] == '1' and last > 0:
            s = l[i][2] + s
            sc += l[i][2]
    elif l[i][1] == '2' and last > 0:
            s += l[i][2]
            sc = l[i][2] + sc
    elif l[i][1] == '1' and last < 0:
            s += l[i][2]
            sc = l[i][2] + sc
    else:
            s = l[i][2] + s
            sc += l[i][2]

if last > 0:
    print(s)
else:
    print(sc)

### FIXED CODE ###

import copy
from collections import deque
s = deque(input())
sc = copy.deepcopy(s) 
sc.reverse()
n = int(input())
l = [list(input().split()) for i in range(n)]

for i in range(n):
    if l[i][0] == '1':
        save = s
        s = sc
        sc = save
    elif l[i][1] == '1':
        s.appendleft(l[i][2])
        sc.append(l[i][2])
        #s = l[i][2] + s
        #sc += l[i][2]
    else:
        s.append(l[i][2])
        sc.appendleft(l[i][2])
        #s += l[i][2]
        #sc = l[i][2] + sc

print(''.join(s))
### BUGGY CODE ###

def main():
    N,M = map(int, input().split())
    A = list(map(int, input().split()))
    #A.insert(0)
    use = [0,2,5,5,4,5,6,3,7,6]

    # dp[i][j] = 残りj本でできる最大の数
    dp = []
    for i in range(N//2+11):
        dp.append([-1 for j in range(N+1)])
    dp[0][N] = 0

    for i in range(1,N//2+11):
        for n in range(0,N+1):
            for a in A:
                if n + use[a] > N:
                    dp[i][n] = max(dp[i][n], dp[i-1][n])
                else:
                    dp[i][n] = max(dp[i][n], dp[i-1][n+use[a]]*10+a)
        #for n in range(0,N+1):
        #    print('%8d' % dp[i][n], end='')
        #print()
        if dp[i] == dp[i-1]:
            print(dp[i][0])
            return

main()


### FIXED CODE ###

inf = 1 << 60
N,M = map(int, input().split())
A = list(map(int, input().split()))
#A.insert(0)
use = [0,2,5,5,4,5,6,3,7,6]

# dp[i] = i本でできる最大の数
dp = [-inf for i in range(N+1)]
dp[0] = 0
for i in range(N+1):
    for a in A:
        if i < use[a]:
            continue
        dp[i] = max(dp[i], dp[i-use[a]] * 10 + a)
print(dp[N])
### BUGGY CODE ###


  
n = int(input())
if n%2==0:
  print(-1)
  exit()
#print(n_list)
seven = 7
while True:
  if n<=seven and seven%n==0:
    print(len(str(seven)))
    exit()
  seven = int(str(seven)+'7')
print(seven)
print(-1)

### FIXED CODE ###

k = int(input())

if k%2==0 or k%5==0:
  print(-1)
  exit()

mod = 7
cnt = 1
while True:
  if mod%k==0:
    print(cnt)
    exit()
    
  mod *= 10
  mod += 7
  cnt += 1
  mod %= k
### BUGGY CODE ###

n=int(input())
arr=list(map(int,input().split()))
t=1
for i in range(n):
    if arr[i]==0:
        t=0
        break
    t*=arr[i]
if t>10**18:
    t=-1
print(t)

### FIXED CODE ###

n=int(input())
arr=list(map(int,input().split()))
t=1
arr.sort()
for i in range(n):
    t*=arr[i]
    if arr[i]==0:
        t=0
        break
    elif t>10**18:
        t=-1
        break
print(t)
### BUGGY CODE ###

def main(n,ab,px):
  g=[[]for _ in range(n+1)]
  for a,b in ab:
    g[a].append(b)
    g[b].append(a)

  import sys
  sys.setrecursionlimit(10**7)
  
  # 各頂点を根とした部分木に含まれる頂点を列挙
  d={i:[i] for i in range(1,n+1)}
  def dfs(seen,i):
    ret=[i]
    seen[i-1]=1
    l=g[i]
    for li in [li for li in l if seen[li-1]==0]:
      e=dfs(seen,li)
      for ei in e:
        ret.append(ei)
    d[i]=ret
    return ret
  seen=[0]*n
  s=dfs(seen,1)
  #print(d)
  ans=[0]*n
  for p,x in px:
    for di in d[p]:
      ans[di-1]+=x
  print(' '.join(list(map(str,ans))))

if __name__=='__main__':
  import sys
  input = sys.stdin.readline
  n,q=map(int,input().split())
  ab=[list(map(int,input().split())) for _ in range(n-1)]
  px=[list(map(int,input().split())) for _ in range(q)]
  main(n,ab,px)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
def main():
    n,q=map(int,input().split())
    graph=[[] for _ in range(n+1)]
    ab=[list(map(int,input().split())) for _ in range(n-1)]
    for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
    px=[list(map(int,input().split())) for _ in range(q)]
    seen=[0]*(n+1)
    ans=[0]*(n+1)
    for p,x in px:
        ans[p]+=x
    def dfs(i):
        seen[i]=1
        for li in graph[i]:
            if seen[li]==0:
                ans[li]+=ans[i]
                dfs(li)
    dfs(1)
    print(' '.join(map(str,ans[1:])))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n,w=map(int,input().split())
W=[]
V=[]
for _ in range(n):
    a,b=map(int,input().split())
    W.append(a)
    V.append(b)
dp=[[0]*(w+1) for _ in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if j<W[i]:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j],dp[i][j-W[i]]+V[i])

print(dp[n][w])

### FIXED CODE ###

n,w=map(int,input().split())
W=[]
V=[]
for _ in range(n):
    x,y=map(int,input().split())
    W.append(x)
    V.append(y)
dp=[[0]*(w+1) for _ in range(n+1)]

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

print(dp[n][w])
### BUGGY CODE ###

s = list(input())

ans = 0

for i in range(len(s)):
    if s[i] == 'B':
        tmp = s[i:]
        ans += tmp.count('W')

print(ans)

### FIXED CODE ###

s = list(input())

ans = 0
black = 0

for i in range(len(s)):
    if s[i] == 'W':
        ans += i - black
        black += 1

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

import math
def main3():
    N, M = map(int, input().split())
    S = input()
    T = input()

    L = (N * M) // math.gcd(N, M)
    good = [-1 for i in range(4 * L)]

    idx_s = 0
    idx_t = 0

    for i in range(1, max(N, M) + 1):
        idx_s = (i - 1) * (L // N) + 1
        idx_t = (i - 1) * (L // M) + 1

        if N < M:

            if i <= N:
                good[idx_s] = S[i - 1]

            if i == 1:
                if S[i - 1] != T[i - 1]:
                    print(-1)
                    exit()
            else:
                if good[idx_t] == -1 or good[idx_t] == T[i - 1]:
                    good[idx_t] = T[i - 1]
                else:
                    print(-1)
                    exit()

        else: #N >= M

            if i <= M:
                good[idx_t] = T[i - 1]

            if i == 1:
                if T[i - 1] != S[i - 1]:
                    print(-1)
                    exit()
            else:
                if good[idx_s] == -1 or good[idx_s] == S[i - 1]:
                    good[idx_s] = S[i - 1]
                else:
                    print(-1)
                    exit()

    max_idx = max(((N - 1) * (L // N) + 1), ((M - 1) * (L // M) + 1))
    r, m = divmod(max_idx, L)

    ans = 0
    if m == 0:
        ans = r * L
    else:
        ans = (r + 1) * L

    print(ans)

if __name__ == "__main__":
    main3()

### FIXED CODE ###

import math
def main4():
    N, M = map(int, input().split())
    S = input()
    T = input()

    L = (N * M) // math.gcd(N, M)

    pair = dict()

    for i in range(1, N + 1):
        idx = (i - 1) * (L // N) + 1
        pair[idx] = S[i - 1]

    for i in range(1, M + 1):
        idx = (i - 1) * (L // M) + 1

        if idx in pair.keys():
            if pair[idx] != T[i - 1]:
                print(-1)
                exit()

    print(L)

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

N = int(input())

V = list(map(int,input().split()))
C = list(map(int,input().split()))

x = 0
y = 0
mx = 0
for i in range(2**N):
    x = 0
    y = 0
    for j in range(N):
        if (i >> j) & 1 == 1:
            x += V[j]
            y += C[j]
        mx = max(x-y,mx)
print(mx)

### FIXED CODE ###

N = int(input())

V = list(map(int,input().split()))
C = list(map(int,input().split()))

x = 0
y = 0
mx = 0
l = [V[i]-C[i] for i in range(N)]
print(sum([ i for i in l if i>0 ]))
### BUGGY CODE ###

import queue

H = int(input())

q = queue.Queue()
q.put(H)

c=0
while not q.empty():
    x = q.get()
    x = x // 2
    if x > 0:
        q.put(x)
        q.put(x)
    c+=1

print(c)

### FIXED CODE ###

def dfs(h):
    if h == 1:
        return 1
    else:
        return dfs(h//2) * 2 + 1

H = int(input())

print(dfs(H))
### BUGGY CODE ###

import sys
from collections import deque
readline = sys.stdin.readline
N = int(readline())

testimonies = [[[], []] for _ in range(N)]
for i in range(N):
    A = int(readline())
    for _ in range(A):
        x, y = map(int, readline().rstrip().split())
        testimonies[i][y].append(x-1)

def check(honest_persons):
    """矛盾がないか検証する"""
    honest_checked = set(honest_persons)  # 宛先を確認済みの正直者の人
    honest_stack = deque(honest_persons)  # 宛先を確認する正直者の人の待ち行列
    honest, liers = honest_persons, []  # 正直者の人, 不親切な人

    # 正直者の人の証言も元に、正直者の人/不親切な人を追加していく
    while len(honest_stack) > 0:
        honest_person = honest_stack.popleft()
        honest_checked.add(honest_person)
        next_honest_persons = testimonies[honest_person][1]

        # 検証済み以外の人をstackする
        for person in next_honest_persons:
            if person not in honest_checked:
                honest_stack.append(person)

        honest += testimonies[honest_person][1]
        liers += testimonies[honest_person][0]

    # 矛盾がなければOK
    if len(set(honest) & set(liers)) == 0:
        return True
    else:
        return False

def main():
    # bit全探索する
    ans = 0
    for i in range(1, 2**N):
        comb = bin(i)[2:].zfill(N)
        honest_persons = []
        for p, c in enumerate(comb):
            if c == '1':
                honest_persons.append(p)
        if check(honest_persons):
            ans = max(ans, sum(list(map(int, list(comb)))))

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
N = int(sys.stdin.readline())

testimonies = [[-1 for _ in range(N)] for _ in range(N)]
for i in range(N):
    A = int(sys.stdin.readline())
    for _ in range(A):
        x, y = map(int, sys.stdin.readline().rstrip().split())
        testimonies[i][x-1] = y

def check(honest_persons):
    flag = True
    for i in range(N):
        if honest_persons[i]:
            for j in range(N):
                if testimonies[i][j] == -1:
                    continue
                if testimonies[i][j] != honest_persons[j]:
                    flag = False
                    break
    return flag

def main():
    ans = 0
    for i in range(1, 2**N):
        honest_persons = bin(i)[2:].zfill(N)
        honest_persons = list(map(int, list(honest_persons)))

        if check(honest_persons):
            ans = max(ans, sum(honest_persons))

    print(ans)

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

n = int(input())
ans = 1

for i in range(1,n+1):
    ans *= i

print(ans%(10**9+7))


### FIXED CODE ###

n = int(input())
ans = 1

for i in range(1,n+1):
    ans = i * ans % (10**9+7)

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

import sys
import os

def file_input():
    f = open('Beginner_Contest_162/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    N=input()
    S=input()
    # print(S)

    sum=0
    for i in range(len(S)):
        # print(i)
        for j in range(i+1,len(S)):
            if S[i]!=S[j]:
                for k in range(j+1,len(S)):
                    if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i] and j-i!=k-j:
                        sum+=1
                        # print(S[i]+S[j]+S[k])
    print(sum)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os

def file_input():
    f = open('Beginner_Contest_162/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    N=int(input())
    S=input()
    # print(S)
    R=S.count('R')
    G=S.count('G')
    B=S.count('B')

    sum=R*G*B
    # print(sum)
    for i in range(N-2):
        # print(i)
        for j in range(i+1,-(-(N+i)//2)):
            k=2*j-i
            # print("i:"+str(i)+" j:"+str(j)+" k:"+str(k))
            if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
                sum-=1
                # print(S[i]+S[j]+S[k])


    print(sum)

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

*S, = map(ord, input())
*T, = map(ord, input())
LS = len(S); LT = len(T)

dp = [[-1]*(LT+2) for i in range(LS+2)]
for i in range(LS-1, -1, -1):
    X = dp[i]; Y = dp[i+1]; si = S[i]
    r = X[LT]
    for j in range(LT-1, -1, -1):
        X[j] = r = max(Y[j+1] + 1, Y[j], r) if si == T[j] else max(Y[j], r)
i = j = 0
ans = []
X = dp[0]; Y = dp[1]
while i < LS and j < LT:
    if S[i] == T[j] and X[j] == Y[j+1] + 1:
        ans.append(S[i])
        i += 1; j += 1
        X = Y; Y = dp[i+1]
    elif X[j] == Y[j]:
        i += 1
        X = Y; Y = dp[i+1]
    else:
        j += 1
print(*map(chr, ans), sep='')

### FIXED CODE ###

*S, = map(ord, input())
*T, = map(ord, input())
LS = len(S); LT = len(T)

dp = [[-1]*(LT+1) for i in range(LS+1)]
for i in range(LS-1, -1, -1):
    for j in range(LT-1, -1, -1):
        if S[i] == T[j]:
            dp[i][j] = max(dp[i+1][j+1] + 1, dp[i+1][j], dp[i][j+1])
        else:
            dp[i][j] = max(dp[i+1][j], dp[i][j+1])
i = j = 0
ans = []
while i < LS and j < LT:
    if S[i] == T[j]:
        if dp[i][j] == dp[i+1][j+1] + 1:
            ans.append(S[i])
            i += 1; j += 1
        elif dp[i][j] == dp[i+1][j]:
            i += 1
        else:
            j += 1
    else:
        if dp[i][j] == dp[i+1][j]:
            i += 1
        else:
            j += 1
print(*map(chr, ans), sep='')
### BUGGY CODE ###

mod=10**9+7
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp1=[1]*(m+1)
dp2=[1]*(m+1)
for i in range(n):
  for j in range(m):
    if s[i]==t[j]:dp1[j+1]=dp2[j+1]+dp1[j]
    else:dp1[j+1]=dp2[j+1]+dp1[j]-dp2[j]
    dp1[j+1]%=mod
  dp2=dp1.copy()
  dp1=[1]*(m+1)
print(dp2[-1])

### FIXED CODE ###

mod=10**9+7
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[(m+1)*[1]for _ in range(n+1)]
for i in range(n):
  for j in range(m):
    if s[i]==t[j]:dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]
    else:dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]-dp[i][j]
    dp[i+1][j+1]%=mod
print(dp[-1][-1])
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC139 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()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
for j in range(n**2):
    f = defaultdict(lambda : 0)
    flg,flg2 = False,False
    for i in range(n):
        if len(a[i]) == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        if f[(y,x)] == 1:
            flg = True
            f[(y,x)] = 0
        else:
            f[(x,y)] = 1
    if flg:
        ans += 1
    if not flg2:
        print(ans)
        quit()
    for k,l in f.items():
        if l > 0:
            a[k[0]-1].appendleft(k)
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(n*(n-1)//2)


### FIXED CODE ###

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

import sys
import math
import bisect
import time
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()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
s = time.time()
for j in range(n*(n-1)//2+1):
    check = [1]*n
    flg = False
    flg2 = False
    if time.time() - s > 1.6:
        print(n*(n-1)//2)
        quit()
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg:
        for i in a:
            if len(i) != 0:
                print(-1)
                quit()
    if not flg2:
        print(ans)
        quit()
### BUGGY CODE ###

s = input()
m = [1] * len(s)
for i in range(1000):
    nm = m[:]
    for j in range(len(s)):
        nm[j] -= m[j]
        if s[j] == 'R':
            nm[j+1] += m[j]
        elif s[j] == 'L':
            nm[j-1] += m[j]
    m = nm
ans = ''
for mi in m:
    ans += str(mi) + ' ' 
print(ans[:-1])

### FIXED CODE ###

s = input()
m = [1] * len(s)
ns = []
ss = 0
for i in range(len(s)-1):
    if s[i:i+2] == 'LR':
        ns.append(s[ss:i+1])
        ss = i+1
ns.append(s[ss:])
m = []
for nsi in ns:
    l = len(nsi)
    mi = [0] * l
    for j in range(l):
        if nsi[j:j+2] == 'RL':
            r = j
            break
    mi[r] = l // 2
    mi[r+1] = l // 2
    if l % 2 == 1:
        mi[r + r % 2] += 1
    m += mi
ans = ''
for mi in m:
    ans += str(mi) + ' ' 
print(ans[:-1])
### BUGGY CODE ###

base = 127
mask = (1 << 32) - 1


def calc_hash(f, pl, tl):
    dl = tl - pl
    tmp = set()

    t = 1
    for _ in range(pl):
        t = (t * base) & mask
    e = 0
    for i in range(pl):
        e = (e * base + f[i]) & mask
    for i in range(dl):
        tmp.add(e)
        e = (e * base - t * f[i] + f[i + pl]) & mask
    tmp.add(e)
    return tmp


t = [ord(c) for c in input().strip()]
tl = len(t)
q = int(input())
ps = [input().strip() for _ in range(q)]
h = dict()
c = dict()
a = []
for p in ps:
    if p in c:
        a.append(c[p])
        continue
    p = [ord(c) for c in p]
    pl = len(p)
    if pl > tl:
        a.append(0)
        continue
    bs = min(20, pl)
    keys = calc_hash(p, bs, pl)
    if bs not in h:
        h[bs] = calc_hash(t, bs, tl)
    a.append(1 if keys.issubset(h[bs]) else 0)
print('\n'.join(map(str, a)))

### FIXED CODE ###

base = 127
mask = (1 << 32) - 1


def calc_hash(f, pl, tl):
    dl = tl - pl
    tmp = set()

    t = 1
    for _ in range(pl):
        t = (t * base) & mask
    e = 0
    for i in range(pl):
        e = (e * base + f[i]) & mask
    for i in range(dl):
        tmp.add(e)
        e = (e * base - t * f[i] + f[i + pl]) & mask
    tmp.add(e)
    return tmp


t = [ord(c) for c in input().strip()]
tl = len(t)
q = int(input())
ps = [input().strip() for _ in range(q)]
h = dict()
a = []
hash_len = 19
for p in ps:
    p = [ord(c) for c in p]
    pl = len(p)
    if pl > tl:
        a.append(0)
        continue
    bs = min(hash_len, pl)
    keys = calc_hash(p, bs, pl)
    if bs not in h:
        h[bs] = calc_hash(t, bs, tl)
    a.append(1 if keys.issubset(h[bs]) else 0)
print('\n'.join(map(str, a)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import sys
sys.setrecursionlimit(10**7)
def main(n,ab,px):
  g=[[]for _ in range(n)]
  for a,b in ab:
    g[a-1].append(b-1)
    g[b-1].append(a-1)
  ans=[0 for _ in range(n)]
  for p,x in px:
    ans[p-1]+=x  
  def dfs(seen,i):
    seen[i]=1
    for li in [li for li in g[i] if seen[li]==0]:
        ans[li]+=ans[i]
        dfs(seen,li)
  seen=[0 for _ in range(n)]
  dfs(seen,0)
  print(' '.join(list(map(str,ans))))

if __name__=='__main__':
  n,q=map(int,input().split())
  ab=[list(map(int,input().split())) for _ in range(n-1)]
  px=[list(map(int,input().split())) for _ in range(q)]
  main(n,ab,px)
  

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
def main():
    n,q=map(int,input().split())
    graph=[[] for _ in range(n+1)]
    ab=[list(map(int,input().split())) for _ in range(n-1)]
    for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
    px=[list(map(int,input().split())) for _ in range(q)]
    seen=[0]*(n+1)
    ans=[0]*(n+1)
    for p,x in px:
        ans[p]+=x
    def dfs(i):
        seen[i]=1
        for li in graph[i]:
            if seen[li]==0:
                ans[li]+=ans[i]
                dfs(li)
    dfs(1)
    print(' '.join(map(str,ans[1:])))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import queue

h, w = map(int, input().split())
s, count = [], 0
for _ in range(h):
    a = input()
    count += a.count('#')
    s.append(list(a))

def cal():
    ans = float('inf')
    q = queue.Queue()
    q.put((0, 0, 1))
    while not q.empty():
        c0, c1, c2 = q.get()
        s[c0][c1] = '#'
        if c0 == h-1 and c1 == w-1:
            return h*w-count-c2
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            x, y = c0+i, c1+j
            if 0 <= x < h and 0 <= y < w:
                if s[x][y] != '#':
                    q.put((x, y, c2+1))

    return ans

ans = cal()
if ans == float('inf'):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

def cal():
    import queue
    h, w = map(int, input().split())
    s = [list(input()) for _ in range(h)]
    cost = [[-1]*w for _ in range(h)]
    INF = float('inf')
    count, ans = 0, INF
    for i in range(h):
        for j in range(w):
            if s[i][j] != '#':
                cost[i][j] = INF
            else:
                count += 1        
    q = queue.Queue()
    q.put((0, 0, 1))
    while not q.empty():
        c0, c1, c2 = q.get()
        s[c0][c1] = '#'
        if c0 == h-1 and c1 == w-1:
            return h*w-count-c2
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            x, y = c0+i, c1+j
            if 0 <= x < h and 0 <= y < w:
                if s[x][y] != '#' and cost[x][y] == INF:
                    cost[x][y] = c2+1
                    q.put((x, y, c2+1))

    return ans

ans = cal()
if ans == float('inf'):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import fractions
import numpy as np

from sys import stdin


def main():
    n = int(stdin.readline())
    a = list(map(int, stdin.readline().split()))
    sa = set(a)

    lcm = 1

    for ai in sa:
        lcm = (ai * lcm) // fractions.gcd(ai, lcm)

    ans = 0

    ans = np.sum([lcm // ai for ai in a])

    ans %= 10 ** 9 + 7

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import fractions

from sys import stdin


def main():
    n = int(stdin.readline())
    a = list(map(int, stdin.readline().split()))
    sa = set(a)

    lcm = 1

    for ai in sa:
        lcm = (ai * lcm) // fractions.gcd(ai, lcm)

    ans = 0

    for ai in a:
        ans += lcm // ai
    ans %= 10 ** 9 + 7

    print(ans)


if __name__ == "__main__":
    main()