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

from collections import deque

h,w = map(int, input().split())
A = [[s for s in input()] for _ in range(h)]

visited = [[-1]*(w) for _ in range(h)]
dq = deque()
directions = [[0,1],[1,0],[0,-1],[-1,0]]

# 初期配置の黒をキューに追加
for hi in range(h):
    for wi in range(w):
        if A[hi][wi] == '#':
            dq.append([hi,wi])
            visited[hi][wi] = 0

# キューが空になるまで
while dq:
    hi,wi = dq.popleft()
    for d in directions:
        nhi, nwi = hi+d[0],wi + d[1]
        # 場外ならスキップ
        if nhi<0 or nhi>=h or nwi<0 or nwi>=w: continue 
        # 「黒くしてない白マス」をキューに追加
        if visited[nhi][nwi] == -1 and A[nhi][nwi] == '.':
            dq.append([nhi,nwi])
            visited[nhi][nwi] = visited[hi][wi] + 1

ans = -1
for x in visited:
    ans = max(ans,max(x))
print(ans)

### FIXED CODE ###

from collections import deque

h,w = map(int, input().split())
A = [[s for s in input()] for _ in range(h)]

visited = [[-1]*(w) for _ in range(h)]
dq = deque()
directions = [[0,1],[1,0],[0,-1],[-1,0]]

# 初期配置の黒をキューに追加
for hi in range(h):
    for wi in range(w):
        if A[hi][wi] == '#':
            dq.append([hi,wi])
            visited[hi][wi] = 0

# キューが空になるまで
while dq:
    hi,wi = dq.popleft()
    for d in directions:
        nhi, nwi = hi+d[0],wi + d[1]
        # 場外ならスキップ
        if nhi<0 or nhi>=h or nwi<0 or nwi>=w: continue 
        # 「黒くしてない白マス」をキューに追加
        if visited[nhi][nwi] == -1 and A[nhi][nwi] == '.':
            dq.append([nhi,nwi])
            visited[nhi][nwi] = visited[hi][wi] + 1

ans = -1
for x in visited:
    ans = max(ans,max(x))
print(ans)
### BUGGY CODE ###

#MLE注意！ not は使わず !=
#0や1のケースに注意

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    n = input().rstrip()
    n = n[::-1]
    res = [0]*2019
    res[0] += 1
    b = 0
    for i in range(len(n)):
        a = int(n[i])
        b += a*(10**i)%2019
        b %= 2019
        res[b] += 1
    ans = 0
    for i in res:
        if i>=2:
            ans += i*(i-1)//2
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#MLE注意！ not は使わず !=
#0や1のケースに注意

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    n = input().rstrip()
    n = n[::-1]
    res = [0]*2019
    res[0] += 1
    b = 1
    c = 0
    for i in range(len(n)):
        a = int(n[i])
        c += a*b
        c %= 2019
        res[c] += 1
        b = b*10%2019
    ans = 0
    for i in res:
        if i>=2:
            ans += i*(i-1)//2
    print(ans)

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

# 2019/6/25
import sys
N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
s = set()
cur = 1
ans = 0
while not cur in s:
    if a[cur-1] == 2:
        print(ans+1)
        sys.exit()
    else:
        cur = a[cur-1]
        ans += 1
print(-1)

### FIXED CODE ###

# 2019/6/25
import sys
N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
if not 2 in a:
    print(-1)
    sys.exit()
s = set()
cur = 1
ans = 0
while not cur in s:
    if a[cur-1] == 2:
        print(ans+1)
        sys.exit()
    else:
        s.add(cur)
        cur = a[cur-1]
        ans += 1
print(-1)
### BUGGY CODE ###

S = input().split(" ")
N = int(S[0])
M = int(S[1])

S = input().split(" ")

arr =  [int(s) for s in S]
arr2 = arr.copy()
brr =  [0 for s in S]

def calculate(m,arr,brr):


    for i in range(m):
        maxValue = max(arr)
        maxIndex = arr.index(maxValue)
        arr[maxIndex] = arr[maxIndex]//2
        brr[maxIndex] = brr[maxIndex] + 1

    return brr

result = calculate(M,arr,brr)


for index,br in enumerate(brr):
    arr2[index] = arr2[index]//(2**br)

print(sum(arr2))

### FIXED CODE ###

import heapq

S = input().split(" ")
N = int(S[0])
M = int(S[1])
S = input()

arr = [-int(s) for s in S.split(" ")]

heapq.heapify(arr)

for i in range(M):
    maxValue = -heapq.heappop(arr)
    heapq.heappush(arr,-(maxValue//2))

print(-sum(arr))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from heapq import heappush,heappop,heapify
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
X,Y=[0]*N,[0]*N
dx,dy={},{}
for i in range(N):
    X[i],Y[i]=map(int,input().split())
    if X[i] in dx:
        dx[X[i]].append(i)
    else:
        dx[X[i]]=[i]
    if Y[i] in dy:
        dy[Y[i]].append(i)
    else:
        dy[Y[i]]=[i]
ux,uy=list(set(X)),list(set(Y))
ux.sort()
uy.sort()
uxi={x:i for i,x in enumerate(ux)}
uyi={y:i for i,y in enumerate(uy)}
edge=[[] for i in range(N)]
for i,(x,y) in enumerate(zip(X,Y)):
    for index in dx[x]+dy[y]:
        if index!=i:
            edge[i].append((0,index))
    if uxi[x]>=1:
        nx=ux[uxi[x]-1]
        for index in dx[nx]:
            if index!=i:
                edge[i].append((abs(nx-x),index))
                edge[index].append((abs(nx-x),i))
    if uyi[y]>=1:
        ny=uy[uyi[y]-1]
        for index in dy[ny]:
            if index!=i:
                edge[i].append((abs(ny-y),index))
                edge[index].append((abs(ny-y),i))

def prim(n,edges):
    used=[False]*n
    used[0]=True
    edgelist=[]
    for edge in edges[0]:
        heappush(edgelist,edge)
    cost=0
    while edgelist:
        minedge=heappop(edgelist)
        if used[minedge[1]]:
            continue
        v=minedge[1]
        used[v]=True
        for edge in edges[v]:
            if not used[edge[1]]:
                heappush(edgelist,edge)
        cost+=minedge[0]
    return cost

print(prim(N,edge))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from heapq import heappush,heappop,heapify
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
X,Y=[],[]
for i in range(N):
    x,y=map(int,input().split())
    X.append((y,i))
    Y.append((x,i))
X.sort(key=lambda t:t[0])
Y.sort(key=lambda t:t[0])
edge=[[] for i in range(N)]
for i in range(N-1):
    edge[X[i][1]].append((abs(X[i][0]-X[i+1][0]),X[i+1][1]))
    edge[X[i+1][1]].append((abs(X[i][0]-X[i+1][0]),X[i][1]))
    edge[Y[i][1]].append((abs(Y[i][0]-Y[i+1][0]),Y[i+1][1]))
    edge[Y[i+1][1]].append((abs(Y[i][0]-Y[i+1][0]),Y[i][1]))

def prim(n,edges):
    used=[False]*n
    used[0]=True
    edgelist=[]
    for edge in edges[0]:
        heappush(edgelist,edge)
    cost=0
    while edgelist:
        minedge=heappop(edgelist)
        if used[minedge[1]]:
            continue
        v=minedge[1]
        used[v]=True
        for edge in edges[v]:
            if not used[edge[1]]:
                heappush(edgelist,edge)
        cost+=minedge[0]
    return cost

print(prim(N,edge))
### BUGGY CODE ###

import numpy as np
s = input()
if s[-1] == "?":
    pre = [1 for i in range(10)] + [0,0,0]
else:
    pre = [0 for i in range(13)]
    pre[int(s[-1])] = 1
n = 10**9 + 7
for i in range(1, len(s)):
    t = 10**i % 13
    if s[-1*i-1] == "?":
        c = np.array(pre)
        for j in range(1,10):
            te = t*j % 13
            c[te:] += pre[:13-te]
            c[:te] += pre[13-te:]
            c %= n
        pre = c.tolist()
    else:
        te = int(s[-1*i-1])*t % 13
        pre = pre[13-te:]+pre[:13-te]
print(pre[5]%n)

### FIXED CODE ###

s = input()
pre = [1]+[0]*12
n = 10**9 + 7
tem = [[i*j%13 for i in range(10)] for j in range(13)]
t = 1
for i in range(len(s)):
    if s[-1*i-1] > "9":
        pre = [sum([pre[k-i] for i in tem[t]])%n for k in range(13)]      
    else:
        te = int(s[-1*i-1])*t % 13
        pre = [pre[i-te] for i in range(13)]
    t = t*10 % 13
print(pre[5])
### BUGGY CODE ###

N = int(input())
p = [int(x)-1 for x in input().split()]

s = N
ans = 0
for i in range(N):
    if p.index(i) < s:
        ans += 1
        s = p.index(i)
print(ans)

### FIXED CODE ###

N = int(input())
l = input().split()
p = []
for i in range(N):
    p.append((int(l[i]),i))

p.sort()

s = N
ans = 0
for i in range(N):
    (a,b) = p[i]
    if b < s:
        ans += 1
        s = b
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))

N, K = inpl()
A = inpl()
tmp = 0
S = [0]*N
Q = []
for i in range(N):
    tmp += A[i]
    S[i] = tmp
    Q.append(tmp)

tmp = 0
for i in range(1, N):
    tmp = S[i-1]
    for j in range(i, N):
        #print(i, j)
        v = S[j] -S[i-1]
        Q.append(v)

res = 0
L = len(Q)
I = len(bin(sum(A))) - 2
while True:
    ok = 0
    for i in range(I):
        num = res + 2**i
        tmp = 0
        for j in range(L):
            if num & Q[j] == num:
                tmp += 1
        if tmp >= K:
            ok = num

    I = len(bin(res - ok)) - 2
    if res < ok & ok > 0:
        res = ok
    else:
        break

print(res)

### FIXED CODE ###

# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))

N, K = inpl()
A = inpl()
tmp = 0
S = [0]*N
Q = []
for i in range(N):
    tmp += A[i]
    S[i] = tmp
    Q.append(tmp)

tmp = 0
for i in range(1, N):
    tmp = S[i-1]
    for j in range(i, N):
        #print(i, j)
        v = S[j] -S[i-1]
        Q.append(v)

res = 0
while True:
    ok = 0
    for i in range(40):
        num = res + int("1" + "0"*i, 2)
        tmp = 0
        for j in range(len(Q)):
            if num & Q[j] == num:
                tmp += 1
        if tmp >= K:
            ok = num
    if res < ok:
        res = ok
    else:
        break
print(res)
### BUGGY CODE ###

N = int(input())
S = input()

E = [0]*N
W = [0]*N

for i in range(N):
    if S[i] == "E":
        E[i] = 1
    else:
        W[i] = 1

min = N

for i in range(N):
    S = sum(W[0:i])+sum(E[i+1:N])
    if S < min:
        min = S
    
print(min)

### FIXED CODE ###

N = int(input())
S = input()

E = [0]*(N+1)
W = [0]*(N+1)

for i in range(N):
    if S[i] == "E":
        E[i+1] = E[i] + 1
        W[i+1] = W[i]
    else:
        E[i+1] = E[i]
        W[i+1] = W[i] + 1

min = N

for i in range(N):
    S = W[i]-W[0] + E[N]-E[i+1]
    if S < min:
        min = S
    
print(min)
### BUGGY CODE ###

h, n = map(int, input().split())
a, b = [0], [0]
for _ in range(n):
    s, t = map(int, input().split())
    a.append(s)
    b.append(t)
dp = [[0 for _ in range(h + max(a))] for _ in range(n + 1)]
for i in range(n + 1):
    for j in range(1, h + max(a)):
        if i == 0:
            dp[i][j] = 10 ** 9
        elif a[i] > j:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = min(dp[i - 1][j], dp[i][j - a[i]] + b[i])
ans = 10 ** 9
for i in range(h, h + max(a)):
    if ans > dp[n][i]:
        ans = dp[n][i]
print(ans)

### FIXED CODE ###

h, n = map(int, input().split())
a, b = [0], [0]
for _ in range(n):
    s, t = map(int, input().split())
    a.append(s)
    b.append(t)
dp = [[0 for _ in range(h + max(a))] for _ in range(n + 1)]
for i in range(n + 1):
    for j in range(1, h + max(a)):
        if i == 0:
            dp[i][j] = 10 ** 9
        elif a[i] > j:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = min(dp[i - 1][j], dp[i][j - a[i]] + b[i])
ans = 10 ** 9
for i in range(h, h + max(a)):
    if ans > dp[n][i]:
        ans = dp[n][i]
print(ans)
### BUGGY CODE ###

import math
N, K = map(int, input().split())

def main():
    plist = [i - 1 for i in map(int, input().split())]
    slist = list(map(int, input().split()))
    max_score = -math.inf
    for start in range(N):
        total_score_in_loop = 0
        now = start
        score_loop = []
        while True:
            now = plist[now]
            total_score_in_loop += slist[now]
            score_loop.append(slist[now])
            if now == start:
                break
        score_rem = 0
        loop_score = 0
        for index, score in enumerate(score_loop, start=1):
            score_rem += score
            if total_score_in_loop > 0:
                loop_score = total_score_in_loop * ((K-index) // len(score_loop))
            max_score = max(max_score, score_rem+loop_score)
    print(max_score)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np
from numba import njit

@njit('i8(i8,i8,i8[:],i8[:],i8)', cache=True)
def main(N, K, plist, slist, max_score):
    for start in range(N):

        total_score_in_loop = 0
        score_loop = []
        now = start
        while True:
            now = plist[now]
            total_score_in_loop += slist[now]
            score_loop.append(slist[now])
            if now == start:
                break
        
        rem_score, loop_score = 0, 0
        for idx in range(1, len(score_loop)+1):
            rem_score += score_loop[idx-1]
            if total_score_in_loop > 0:
                loop_score = ((K - idx) // len(score_loop)) * total_score_in_loop
            max_score = max(max_score, rem_score + loop_score)
    return max_score


N, K = map(int, input().split())
plist = np.array([i-1 for i in map(int, input().split())], dtype='int64')
slist = np.array([i for i in map(int, input().split())], dtype='int64')
max_score = -10**15
max_score = main(N, K, plist, slist, max_score)
print(max_score)
### BUGGY CODE ###

N=int(input())
S=input()

# Zアルゴリズムで解く

# int c = 0;
# for (int i = 1; i < S.size(); i++){
#   if (i+A[i-c] < c+A[c]) {
#     A[i] = A[i-c];
#   } else {
#     int j = max(0, c+A[c]-i);
#     while (i+j < S.size() && S[j] == S[i+j]) ++j;
#     A[i] = j;
#   }
# }
# A[0] = S.size();

c=0
max_num=0
for sub in range(len(S)):
    subS = S[sub:]

    A=[0 for i in range(len(subS))]

    for i in range(1,len(subS)):
        if i+ A[i-c] < c+A[c]:
            A[i] = A[i-c]
        else:
            j=max(0,c+A[c]-i)
            while i+j<len(subS) and subS[j]==subS[i+j]:
                j+=1
            A[i]=j
        if max_num<A[i] and i>=A[i]:
            max_num = A[i]
print(max_num)

### FIXED CODE ###

N=int(input())
S=input()

# Zアルゴリズムで解く

def z_algorithm(S):
    N=len(S)
    A = [N] + [0]*(N-1)
    
    left=1
    length=0
    
    while left < N:
        
        # prefixが同じ間length加算
        while left + length < N and S[length] == S[left+length]:
            length += 1
        
        # prefixの一致数保存
        A[left] = length
        
        # 一文字一致していなければ戻る
        if length == 0:
            left+=1
            continue
        
        # lengthの分だけleftとindexの間を埋めていく(はみ出ていないとこまで)
        k=1
        while k+left < N and k+A[k]<length:
            A[left+k] = A[k]
            k += 1
            
        left += k
        length -= k
    return A

c=0
max_num=0
for sub in range(len(S)):
    subS = S[sub:]
    A=z_algorithm(subS)
    for i,a in enumerate(A):
        if i>=a and max_num<a:
            max_num=a
print(max_num)
### BUGGY CODE ###

import fractions
from itertools import combinations
def cf(x1,x2):
    cf=[1]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf
def compromise(x1, x2):
    f = fractions.gcd(x1, x2)
    return f == 1
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

a, b = map(int, input().split())
cfs = cf(a, b)
primes = []
for c in cfs:
    primes += prime_factorize(c)
print(len(set(primes))+1)

### FIXED CODE ###

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
a, b = map(int, input().split())
apri = set(prime_factorize(a))
bpri = set(prime_factorize(b))
print(len(apri & bpri)+1)
### BUGGY CODE ###

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

    def update(self, i, v):
        while i <= self.n:
            self.tree[i] += v
            i += i & (-i)

    def query(self, i):
        v = 0
        while i:
            v += self.tree[i]
            i -= i & (-i)
        return v


N, Q = map(int, input().split())
*c, = map(int, input().split())

q = [[] for _ in range(N+1)]
for i in range(Q):
    x, y = map(int, input().split())
    q[y-1].append([i, x-1])

bit = BIT(N)
finds = [-1]*(N+1)
ans = [0]*Q
for i in range(N):
    if finds[c[i]] != -1:
        bit.update(finds[c[i]]+1, -1)

    finds[c[i]] = i
    bit.update(finds[c[i]]+1, 1)

    for j, x in q[i]:
        ans[j] = bit.query(i+1) - bit.query(x)

for a in ans:
    print(a)


### FIXED CODE ###

from operator import add, mul, sub, or_


class SegmentTree:
    '''
    セグメント木(遅延ではない)
    1-indexd セグメント木
    values : 値の配列
    op : 区間に対する関数
    ie : 初期値
    '''

    def __init__(self, values):
        self.values = values
        vlen = len(values)
        self.size = 2 ** (vlen-1).bit_length()
        self.tree = [0]*self.size + self.values + [0]*(self.size-vlen)

        for i in range(self.size-1, 0, -1):
            self.tree[i] = self.tree[i*2] + self.tree[i*2+1]

    def update(self, i, v):
        i += self.size
        self.tree[i] = v
        while i > 0:
            i //= 2
            self.tree[i] = self.tree[i*2] + self.tree[i*2+1]

    def query(self, l, r):
        l += self.size
        r += self.size
        ret = 0
        while l < r:
            if l & 1:
                ret += self.tree[l]
                l += 1
            if r & 1:
                r -= 1
                ret += self.tree[r]
            l //= 2
            r //= 2
        return ret


N, Q = map(int, input().split())
*c, = map(int, input().split())

q = [[] for _ in range(N+1)]
for i in range(Q):
    x, y = map(int, input().split())
    q[y-1].append([i, x-1])

st = SegmentTree([0]*(N+1))
finds = [-1]*(N+1)
ans = [0]*Q
for i in range(N):
    if finds[c[i]] != -1:
        st.update(finds[c[i]], 0)

    finds[c[i]] = i
    st.update(finds[c[i]], 1)

    for j, x in q[i]:
        ans[j] = st.query(x, i+1)

for a in ans:
    print(a)
### BUGGY CODE ###

#import numpy as np
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as comb_with
#from itertools import permutations as perm


N = int(input())
#H1,M1,H2,M2,K= map(int,input().split())
A = list(map(int,input().split()))
#B = list(map(int,input().split()))
#S= str(input())
c=1
for i in A:
    c*=i
if c>10**18:
    print(-1)
else:
    print(c)


### FIXED CODE ###

N = int(input())
#H1,M1,H2,M2,K= map(int,input().split())
A = list(map(int,input().split()))
#B = list(map(int,input().split()))
#S= str(input())
#prod = functools.partial(functools.reduce, operator.mul)
#c=np.array(A)
#p=np.prod(A)
c=1
if 0 in A:
    print(0)
    exit()
for i in A:
    c=c*i
    if c>10**18:
        print(-1)
        exit()
print(c)
### BUGGY CODE ###

X=int(input())
i=0
while i >=0:
    for j in range(-100,101):
        if i**5-j**5==X:
            print(str(i)+" "+str(j))
            break
    else:
        i=i+1
        continue
    break

### FIXED CODE ###

X=int(input())
for i in range(-200,201):
    for j in range(-200,201):
        if i**5-j**5==X:
            print(str(i)+" "+str(j))
            break
    else:
        continue
    break
### BUGGY CODE ###

N = int(input())
A = [list(map(int, input().split())) for i in range(N)]

INF = 10 ** 9 + 1
for i in range(N):
    A[i][i] = INF

ans = 0
for i in range(N):
    Ai = A[i]
    for j in range(i):
        Aj = A[j]
        d = INF * 2
        for k in range(N):
            d = min(d, Ai[k] + Aj[k])

        if A[i][j] > d:
            print('-1')
            exit()
        elif A[i][j] < d:
            ans += A[i][j]

print(ans)


### FIXED CODE ###

N = int(input())
A = [list(map(int, input().split())) for i in range(N)]

INF = 10 ** 9 + 1
for i in range(N):
    A[i][i] = INF

ans = 0
for i in range(N):
    Ai = A[i]
    for j in range(i):
        d = min(map(sum, zip(Ai, A[j])))

        if A[i][j] > d:
            print('-1')
            exit()
        elif A[i][j] < d:
            ans += A[i][j]

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

S = input()
Slist = [S[i] for i in range(len(S))]
Q = int(input())
Query = [list(input().split()) for i in range(Q)]
Qlen = len(Query)
cnt = 0
back = []
head = []

for idx, value in enumerate(Query):
    if int(value[0]) == 1:
        cnt +=1
    else:
        if int(value[1]) == 1:
            if cnt % 2 != 0:
                back = back + [value[2]]
            else:
                head = [value[2]] + head
        else:
            if cnt % 2 != 0:
                head = [value[2]] + head
            else:
                back = back + [value[2]]
if cnt % 2 == 0:
    print("".join(head + Slist + back))
else:
    Slist.reverse()
    head.reverse()
    back.reverse()
    print("".join(back + Slist + head))
    
# head Slist last

### FIXED CODE ###

S = input()
Slist = [S[i] for i in range(len(S))]
Q = int(input())
Query = [list(input().split()) for i in range(Q)]
Qlen = len(Query)
reverse = False
back = []
head = []

for idx, value in enumerate(Query):
    if value[0] == "1":
        reverse ^= True
        head, back = back, head
    else:
        if value[1] == "1":
            head += [value[2]]
        else:
            back += [value[2]]

if reverse == False:
    head.reverse()
    print("".join(head + Slist + back))
else:
    head.reverse()
    print("".join(head + Slist[::-1] + back))