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

l=lambda:[int(x) for x in input().split()]
H,W=l()
CH,CW=l()
DH,DW=l()
S=[[x=='#' for x in list(input())] for _ in range(H)]
d={(CH-1,CW-1):0}
q=[(CH-1,CW-1,0)]
def check(h,w,c):
    if h < 0 or h >= H or w < 0 or w >= W:
        return False
    key=(h,w)
    if key in d:
        if d[key] <= c:
            return False
    if S[h][w]:
        return False
    q.append((h,w,c))
    d[key]=c
    return True
while q:
    h,w,c=q.pop()
    # walk
    check(h-1,w-0,c)
    check(h-0,w-1,c)
    check(h+1,w+0,c)
    check(h+0,w+1,c)
    # warp
    check(h-1,w-1,c+1)
    check(h+1,w+1,c+1)
    for i in [-2,+2]:
        for j in range(-2,3):
            check(h+i,w+j,c+1)
    for i in range(-2,3):
        for j in [-2,+2]:
            check(h+i,w+j,c+1)
key=(DH-1,DW-1)
if key in d:
    print(d[key])
else:
    print(-1)

### FIXED CODE ###

def l():
    return [int(x) for x in input().split()]
def main():
    H,W=l()
    ch,cw=l()
    dh,dw=l()
    ch-=1
    cw-=1
    dw-=1
    dh-=1
    s=[[-2 if x=='#' else -1 for x in list(input())] for _ in range(H)]
    pad1=[-2,-2]
    pad2=[[-2]*(W+4)]*2
    s=pad2+[pad1+x+pad1 for x in s]+pad2
    move1=[(-1,0),(1,0),(0,-1),(0,1)]
    move2=list(set([(i,j) for i in range(-2,3) for j in range(-2,3)])-set(move1)-set([(0,0)]))
    q1=[(0,ch+2,cw+2)]
    q2=[]
    s[ch+2][cw+2]=0
    def mark(c,h,w):
        #if 0<=h<H and 0<=w<W and s[h][w]==-1:
        if s[h][w]==-1:
            s[h][w]=c
            q1.append((c,h,w))
    while q1:
        #print(q1)
        c,h,w=q1.pop()
        for i,j in move1:
            mark(c,h+i,w+j)
        q2.append((c+1,h,w))
        if not q1:
            for c,h,w in q2:
                for i,j in move2:
                    mark(c,h+i,w+j)
            q2=[]
    ans=s[dh+2][dw+2]
    if ans>=0:
        print(ans)
    else:
        print(-1)
main()
### BUGGY CODE ###

a=int(input())
b=list(map(int,input().split()))
ans=0
for i in range(1,len(b)+2):
    for j in range(len(b)):
        if i==b[j]:
            ans+=1
    print(ans)
    ans=0

### FIXED CODE ###

a=int(input())
b=[0]*a
c=list(map(int,input().split()))
for i in c:
    b[i-1]+=1
print(*b,sep="\n")
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
#a = int(input())
# スペース区切りの整数の入力
#b, c = map(int, input().split())
# 文字列の入力
#s = input()
# 出力
#print("{} {}".format(a+b+c, s))

import numpy as np

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

ab=[[0]*2 for i in range(n)]
maxa=0

for i in range(0,n):
  ab[i][0], ab[i][1] = map(int, input().split())

sab=sorted(ab)
maxl = 2*10**8
maxa=sab[len(sab)-1][0]
maxi = h+sab[len(sab)-1][0]
ans = [maxl]*maxi
ans[0] = 0

for i in range(1,maxi):
  for j in range(0,n):
    if i < sab[j][0]:
      break
    ans[i] = min(ans[i-sab[j][0]]+sab[j][1], ans[i])

#print(sab)
#print(ans)
print(min(ans[h:]))

### FIXED CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
#a = int(input())
# スペース区切りの整数の入力
#b, c = map(int, input().split())
# 文字列の入力
#s = input()
# 出力
#print("{} {}".format(a+b+c, s))

import numpy as np

h, n = map(int, input().split())
inf=2*10**9
a = np.full(n,inf, int)
b = np.full(n,inf, int)
for i in range(0, n):
  a[i], b[i] = map(int, input().split())

dp=np.full(10001,0,int)
dp[0]=0

for i in range(1,h+1):
  dp[i]=(dp[i-a]+b).min()

print(dp[h])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(S: str):
    ans = 0
    N = len(S)
    while True:
        S = S.replace('10', '').replace('01', '')
        if S.count('10') == 0 and S.count('01') == 0:
            break
    ans = N - len(S)
    print(ans)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    S = str(input())
    solve(S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(S: str):
    stack = []
    N = len(S)
    for i, s in enumerate(S):
        if i == 0:
            stack.append(s)
        else:
            if len(stack) == 0:
                stack.append(s)
            else:
                if s != stack[-1]:
                    tmp = stack.pop()
                else:
                    stack.append(s)
    print(N - len(stack))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    S = str(input())
    solve(S)

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

def cmb(a,b,c):
    b = min(b,a-b)
    num = 1
    for i in range(b):
        num = num*(a-i) % c
    den = 1
    for i in range(b):
        den = den*(i+1) % c
    return num * pow(den,c-2,c) % c

mod = 10**9+7
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
ans = 0
c = cmb(n-1,k-1,mod)
if k == 1:
    print(0)
    exit()
for i in range(n-k+1):
    ans -= a[i] * c
    ans += a[-i-1] * c
    ans %= mod
    c = c * (n-k-i) * pow(n-i-1,mod-2,mod)
if ans < 0:
    ans += mod
print(ans)


### FIXED CODE ###

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

M = 10**9+7

def pow(a,b,M):
    if b == 0:
        return 1
    elif b % 2 == 0:
        return pow((a**2)%M,b//2,M) % M
    else:
        return ((a % M) * pow((a**2)%M,b//2,M)) % M

def inv(a,p):
    return pow(a,p-2,p)

ans,comb = 0,1
#i番目ではcomb = (K-1-i)_C_(K-1)
#max,min以外での選ぶ個数は常にK-1であることに注目すればcomb関数はいらなかった
for i in range(N-K+1):
    if i > 0:
        comb = (comb * (K-1+i) * inv(i,M)) % M
    ans = (ans + comb*((A[K-1+i]-A[N-K-i]) % M)) % M
print(ans)
### BUGGY CODE ###

class DisjointSet:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0]*size
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        
        if self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        elif self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif xr != yr:
            self.parent[yr] = xr
            self.rank[xr] += 1

from collections import defaultdict
from itertools import chain

N = int(input())
points = tuple(tuple(map(int,input().split())) for _ in range(N))

ds = DisjointSet(N)

x_bin = defaultdict(list)
y_bin = defaultdict(list)
for i,(x,y) in enumerate(points):
    x_bin[x].append(i)
    y_bin[y].append(i)

for L in x_bin.values():
    for i,j in zip(L, L[1:]):
        ds.union(i,j)

for L in y_bin.values():
    for i,j in zip(L, L[1:]):
        ds.union(i,j)

X = sorted(x_bin.keys())
Y = sorted(y_bin.keys())
deltas = sorted(
        chain(
            ((x1-x0,x0,x1, True) for x0, x1 in zip(X,X[1:])),
            ((y1-y0,y0,y1, False) for y0, y1 in zip(Y,Y[1:])),
        )
    )

res = 0
for d,v0,v1,xy in deltas:
    b = x_bin if xy else y_bin
    if ds.find(b[v0][0]) != ds.find(b[v1][0]):
        ds.union(b[v0][0],b[v1][0])
        res += d

print(res)

### FIXED CODE ###

class DisjointSet:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0]*size
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        
        if self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        elif self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif xr != yr:
            self.parent[yr] = xr
            self.rank[xr] += 1

from itertools import chain

N = int(input())
points = tuple(tuple(map(int,input().split())) for _ in range(N))
ds = DisjointSet(N)

x_i = sorted((x,i) for i,(x,y) in enumerate(points))
y_i = sorted((y,i) for i,(x,y) in enumerate(points))

xr = [x_i[0]]
yr = [y_i[0]]

for (x0,i0),(x1,i1) in zip(x_i,x_i[1:]):
    if x0 == x1:
        ds.union(i0,i1)
    else:
        xr.append((x1,i1))

for (y0,i0),(y1,i1) in zip(y_i,y_i[1:]):
    if y0 == y1:
        ds.union(i0,i1)
    else:
        yr.append((y1,i1))

deltas = sorted(
        chain(
            ((x1-x0,i0,i1) for (x0,i0), (x1,i1) in zip(xr,xr[1:])),
            ((y1-y0,i0,i1) for (y0,i0), (y1,i1) in zip(yr,yr[1:])),
        )
    )


def it():
    for d,i0,i1 in deltas:
        if ds.find(i0) != ds.find(i1):
            ds.union(i0,i1)
            yield d
print(sum(it()))
### BUGGY CODE ###

#!/usr/bin/python3

import sys
from bisect import bisect_left

sys.setrecursionlimit(1000000)

n = int(input())
a = [int(i) for i in input().split()]

nbs = [ [] for _ in range(n) ]

for _ in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen = {}
dp = [ float('inf')  for i in range(n) ]

def getmlen(cur, p, ctail):
    for ch in nbs[cur]:
        if ch == p:
            continue

        idx = bisect_left(dp, a[ch])
        ov = dp[idx]

        ntail = max(ctail, idx)
        dp[idx] = a[ch]
        mlen[ch] = ntail + 1
        getmlen(ch, cur, ntail)
        dp[idx] = ov

        

dp[0] = a[0]
mlen[0] = 1
getmlen(0, -1, 0)

for i in range(n):
    print(mlen[i])


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from bisect import bisect_left
 
N = int(input())
a = [int(i) for i in input().split()]
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  u, v = map(int, input().split())
  vec[u - 1].append(v - 1)
  vec[v - 1].append(u - 1)
 
lis = [a[0]]
ret = [0] * N
def dfs(cur, pre) :
  for nex in vec[cur] :
    if nex == pre : continue
    if a[nex] > lis[-1] :
      lis.append(a[nex])
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis.pop()
    else :
      pos = bisect_left(lis, a[nex])
      v = lis[pos]
      lis[pos] = a[nex]
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis[pos] = v
 
dfs(0, -1)
 
ret[0] = 1
for i in range(N) :
  print(ret[i])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
for i in a:
  ans*=i

if ans>10**18:print(-1)
else:print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
if 0 in a:
  flag=True
else:
  flag=False
for i in a:
  if flag:ans=0;break
  ans*=i
  if ans>10**18:
    ans=-1
    break
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
X = list(map(int, input().split()))

points = X[:]
points.sort()

if M<=N:
    ans = 0
else:
    import sys
    INT_MAX = sys.maxsize
    ans = INT_MAX

    import itertools
    for v in itertools.combinations(list(range(1, M)),N-1):
        v = [0] + list(v)
        #v.insert(0,0)
        v.append(M)
        #print(v)
        cost_sum = 0
        for i in range(1, len(v)):
            sub_p = points[v[i-1]:v[i]]
            cost = sub_p[-1] - sub_p[0]
            #print(sub_p, cost)
            cost_sum += cost
            if cost_sum >= ans:
                break
        ans = min(ans, cost_sum)

print(ans)





    




### FIXED CODE ###

N, M = map(int, input().split())
X = list(map(int, input().split()))

if M <= N:
    ans = 0
else:
    points = X[:]
    points.sort()

    diff_p = []
    for i in range(1, len(points)):
        diff_p.append(points[i] - points[i-1])

    diff_p.sort()
    #print(diff_p)

    ans = sum(diff_p[:M-N])
print(ans)
### BUGGY CODE ###

import numpy as np
N = int(input())
edges = []
count = np.zeros(N)
for _ in range(N-1):
  a, b = map(int, input().split())
  edges.append([a, b])
  count[a-1] += 1
  count[b-1] += 1
  
MAX = int(np.max(count))

color = [0 for _ in range(N-1)]
used = [set() for _ in range(N)]
resolved = set()

for _ in range(N-1):
  id = np.argmax(count)
  count[id] = 0
  id += 1
  for k, [i,j] in enumerate(edges):
    if k in resolved or (i != id and j != id):
      continue
    for l in range(MAX):
      c = l+1
      if c in used[i-1] or c in used[j-1]:
        continue
      used[i-1].add(c)
      used[j-1].add(c)
      color[k] = c
      resolved.add(k)
      break

print(MAX)
for i in color:
  print(i)


### FIXED CODE ###

N = int(input())
edges = []
node = [[] for _ in range(N)]
for _ in range(N-1):
  a, b = map(int, input().split())
  edges += (a-1, b-1),
  node[a-1] += b-1,
  node[b-1] += a-1,

stuck = [(0,0)]
f = [1]+[0]*N
color_dic = dict()
while stuck:
  v, color = stuck.pop()
  i = 0
  for w in node[v]:
    if f[w]:
      continue
    f[w] = 1
    i += 1
    if i == color:
      i += 1
    stuck += (w,i),
    color_dic[v,w] = i

ans = []
for a,b in edges:
  if (a,b) in color_dic:
    ans += color_dic[a,b],
  else:
    ans += color_dic[b,a],

print(max(ans))
for i in ans:
  print(i)
### BUGGY CODE ###

import queue
h, w = map(int, input().split())
a = [[] for i in range(h)]
for i in range(h):
    a[i] = list(input())

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

que = queue.Queue()

# スタート地点をqueueに追加
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            que.put([i,j])

count = 0
while not que.empty():
    count += 1
    loop = que.qsize()
    for i in range(loop):
        p = que.get()
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and a[ny][nx] == ".":
                a[ny][nx] = "x"
                que.put([ny, nx])


print(count - 1)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
a = [[] for i in range(h)]
for i in range(h):
    a[i] = list(input())

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

que = deque()

white = h * w

# スタート地点をqueueに追加
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            que.append([i, j])
            white -= 1

count = 0
while 1:
    if white == 0:
        break
    count += 1
    loop = len(que)
    for i in range(loop):
        p = que.popleft()
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and a[ny][nx] == ".":
                a[ny][nx] = "#"
                white -= 1
                que.append([ny, nx])


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

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
for i in range(M):
    B, C = list(map(int, input().split()))
    A.extend([C] * B)
A.sort(reverse=True)
print(sum(A[:N]))

### FIXED CODE ###

from collections import Counter

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
a = set(A)
A = Counter(A)

for i in range(M):
    B, C = list(map(int, input().split()))
    A[C] += B
    a.add(C)
a = sorted(list(a), reverse=True)

ans = 0

for i in a:
    ans += i * min(A[i], N)
    N -= A[i]
    if N <= 0:
        break
print(ans)
### BUGGY CODE ###

H,W = (int(i) for i in input().split())
s = [[-1] * (W + 2) for i in range(H+2)]
t = [[-1] * (W + 2) for i in range(H+2)]
 
for i in range(1, H+1):
    SS = input()
    for j in range(W):
        if SS[j] == "#":
            s[i][j+1] = -1
            t[i][j+1] = -1
        else:
            s[i][j+1] = 0
            t[i][j+1] = 0
 
tmp = []
num = 0
for i in range(1, H+1):
    for j in range(1, W+2):
        if s[i][j] == -1 :
            if num != 0:
                for tp in tmp:
                    s[i][tp] = num
                tmp = []
                num =0
        else:
            tmp.append(j)
            num += 1
 
tmp = []
num = 0
for j in range(1, W+1):
    for i in range(1, H+2):
        if t[i][j] == -1 :
            if num != 0:
                for tp in tmp:
                    t[tp][j] = num
                tmp = []
                num =0
        else:
            tmp.append(i)
            num += 1
 
ref = 0
for i in range(H+2):
    for j in range(W+2):
        ref = max(s[i][j] + t[i][j], ref)
 
print(ref-1)

### FIXED CODE ###

H,W = (int(i) for i in input().split())
s = [[-1] * (W + 2) for i in range(H+2)]
t = [[-1] * (W + 2) for i in range(H+2)]

for i in range(1, H+1):
    SS = input()
    for j in range(W):
        if SS[j] == "#":
            s[i][j+1] = -1
            t[i][j+1] = -1
        else:
            s[i][j+1] = 0
            t[i][j+1] = 0

tmp = []
num = 0
for i in range(1, H+1):
    for j in range(1, W+2):
        if s[i][j] == -1 :
            if num != 0:
                for tp in tmp:
                    s[i][tp] = num
                tmp = []
                num =0
        else:
            tmp.append(j)
            num += 1

tmp = []
num = 0
for j in range(1, W+1):
    for i in range(1, H+2):
        if t[i][j] == -1 :
            if num != 0:
                for tp in tmp:
                    t[tp][j] = num
                tmp = []
                num =0
        else:
            tmp.append(i)
            num += 1

ref = 0
for i in range(H+2):
    for j in range(W+2):
        ref = max(s[i][j] + t[i][j], ref)

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

N = int(input())
A = [int(hoge) for hoge in input().split()]
A.sort()
dp = [False] * (max(A) + 1)
ans = 0
prev = -1
for a in A:
    if dp[a] == False:
        for j in range(2,1 + (max(A) // a)):
            dp[a*j] = True
        if a != prev:
            ans += 1
        else:
            dp[a] = True
            ans -= 1
    prev = a
print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
ok=[0]*(a[-1]+1)
for i in range(n):
  ok[a[i]]+=1
for i in range(n):
  if ok[a[i]]>1:
    ok[a[i]]=0
  elif ok[a[i]]==0:
    continue
  j=a[i]
  while 1:
    j += a[i]
    if j > a[-1]:
      break
    ok[j]=0
    
print(sum(ok))
### BUGGY CODE ###

import numpy as np
H,W = map(int,input().split())
# H,W = 2000,2000

S = np.zeros((H,W),dtype=np.int)
for h in range(H):
    l = input()
    for w in range(W):
        if l[w]=="#":
            S[h,w] = 0
        else:
            S[h,w] = 1

Sh = np.zeros((H,W),dtype=np.int)


for h in range(H):
    se = []
    cnt = 0
    for w,val in enumerate(S[h]):
        if val == 1:
            cnt += 1
            se.append(w)
        else:
            for ww in se:
                Sh[h,ww] = cnt
            cnt = 0
            se = []
    for ww in se:
        Sh[h,ww] = cnt

Sw = np.zeros((H,W),dtype=np.int)

for w in range(W):
    se = []
    cnt = 0
    for h,val in enumerate(S[:,w]):
        if val == 1:
            cnt += 1
            se.append(h)
        else:
            for hh in se:
                Sw[hh,w] = cnt
            cnt = 0
            se = []
    for hh in se:
        Sw[hh,w] = cnt


print(max((Sh+Sw).max()-1,0))


### FIXED CODE ###

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

S = [[0 for w in range(W)] for h in range(H)]
for h in range(H):
    l = input()
    for w in range(W):
        if l[w]=="#":
            S[h][w] = 0
        else:
            S[h][w] = 1

Sh = [[0 for w in range(W)] for h in range(H)]

for h in range(H):
    se = []
    cnt = 0
    for w,val in enumerate(S[h]):
        if val == 1:
            cnt += 1
            se.append(w)
        else:
            for ww in se:
                Sh[h][ww] = cnt
            cnt = 0
            se = []
    for ww in se:
        Sh[h][ww] = cnt

Sw = [[0 for w in range(W)] for h in range(H)]

for w in range(W):
    se = []
    cnt = 0
    for h in range(H):
        val = S[h][w]
        if val == 1:
            cnt += 1
            se.append(h)
        else:
            for hh in se:
                Sw[hh][w] = cnt
            cnt = 0
            se = []
    for hh in se:
        Sw[hh][w] = cnt


mx = 0
for h in range(H):
    for w in range(W):
        mx = max(Sh[h][w] + Sw[h][w], mx)

print(max((mx-1,0)))
### BUGGY CODE ###

NM = [int(x) for x in input().split()]
H = [int(x) for x in input().split()]
AB=[]
for i in range(NM[1]):
  AB.append([int(x) for x in input().split()])
X=[]
n=0
x=0
for i in range(NM[0]):
  X.append(1)
  for j1 in AB:
    for j2 in j1:
      if j2==i+1:
        if j1.index(j2)==0:
          n=j1[1]
        else:
          n=j1[0]
        if H[i]<=H[n-1]:
          X[i]=0
          break
    if X[i]==0:
      break
  if X[i]==1:
    x+=1
print(x)

"""
6 5
8 6 9 1 2 1
1 3
4 2
4 3
4 6
4 6

3
"""

### FIXED CODE ###

import numpy as np
NM = [int(x) for x in input().split()]
H = [int(x) for x in input().split()]
X=np.ones(NM[0])
AB=[]
for i in range(NM[1]):
  AB.append([int(x) for x in input().split()])
  if H[AB[i][0]-1]>H[AB[i][1]-1]:
    X[AB[i][1]-1]=0
  elif H[AB[i][0]-1]<H[AB[i][1]-1]:
    X[AB[i][0]-1]=0
  else:
    X[AB[i][1]-1]=0
    X[AB[i][0]-1]=0
x=0
for i in range(NM[0]):
  if X[i]==1:
    x+=1
print(x)

"""
6 5
8 6 9 1 2 1
1 3
4 2
4 3
4 6
4 6

3
"""
### BUGGY CODE ###

import bisect
N = int(input())
L = list(map(int, input().split()))
L = sorted(L)
ans = 0

for i in range(N-1):
    a = L[i]
    for j in range(i+1, N):
        b = L[j]
        r = bisect.bisect_left(L, a+b)
        l = max(i, j) + 1
        ans += max(0, r-l)
print(ans)


### FIXED CODE ###

import bisect
N = int(input())
L = list(map(int, input().split()))
L = sorted(L)
ans = 0

for i in range(N-2):
    for j in range(i+1, N-1):
        ans += bisect.bisect_left(L, L[i]+L[j]) - (j+1)

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

from heapq import *
import sys
input=sys.stdin.readline
def main():
  N,M=map(int,input().split())
  G=[set() for i in range(N)]
  for i in range(M):
      u,v=map(int,input().split())
      u,v=u-1,v-1
      G[u].add(v)
  S,T=map(int,input().split())
  A=[set() for i in range(N)]
  for i in range(N):
      for v in G[i]:
          A[i]=A[i].union(G[v])
  B=[set() for i in range(N)]
  for i in range(N):
      for v in G[i]:
          B[i]=B[i].union(A[v])
  INF=10**9+7
  def dijkstra(G,s):

    d=[INF]*N
    d[s]=0
    visited={s}
    que=[(0,s)]
    while(que):
      p=heappop(que)
      v=p[1]
      visited.add(v)
      for node in G[v]:
        cost=1
        if (node not in visited) and d[node]>d[v]+cost:
          d[node]=d[v]+cost
          heappush(que,(d[node],node))
    return d
  d=dijkstra(B,S-1)
  if d[T-1]==INF:
    print(-1)
  else:
    print(d[T-1])
if __name__=='__main__':#おまじない
  main()


### FIXED CODE ###

from heapq import *
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
G=[[] for i in range(3*N)]
for i in range(M):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    G[3*u+0].append([3*v+1,0])
    G[3*u+1].append([3*v+2,0])
    G[3*u+2].append([3*v+0,1])
S,T=map(int,input().split())
INF=10**9+7
def dijkstra(G,s):

  d=[INF]*(3*N)
  d[s]=0
  visited={s}
  que=[(0,s)]
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,(d[node],node))
  return d
d=dijkstra(G,(S-1)*3)
if d[(T-1)*3]==INF:
  print(-1)
else:
  print(d[(T-1)*3])
### BUGGY CODE ###

def check() -> int:
    n = int(input())
    n_l = list(map(int, input().split()))

    VORDER = 10 ** 18
    ans = n_l[0]

    for i in range(1, n):
        if 0 in n_l:
            ans = 0
            break
        ans = n_l[i] * ans
        if ans > VORDER:
            ans = -1
            break

    return ans


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

### FIXED CODE ###

def check() -> int:
    n = int(input())
    n_l = list(map(int, input().split()))

    VORDER = 10 ** 18
    ans = 1

    if 0 in n_l:
        ans = 0
    else:
        for i in n_l:
            ans = i * ans
            if ans > VORDER:
                ans = -1
                break
    return ans


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

s = input()
q = int(input())

for i in range(q):
  query = input()
  if query[0] == '1':
    s = s[::-1]
  else:
    t, f, c = query.split()
    if f == '1':
      s = c + s
    else:
      s = s + c

print(s)

### FIXED CODE ###

s = input()
q = int(input())

start = ''
end = ''

rvs = False

for i in range(q):
  query = input()
  if query[0] == '1':
    if rvs == False:
      rvs = True
    else:
      rvs = False
  else:
    t, f, c = query.split()
    if f == '1':
      if rvs == False:
        start = c + start
      else:
        end = end + c
    else:
      if rvs == False:
        end = end + c
      else:
        start = c + start

if rvs == False:
  print(start + s + end)
else:
  ans = start + s + end
  print(ans[::-1])