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

from collections import deque
q = deque([])

def get_root(i):
    while True:
        if parent[i] == -1:
            return i
        i = parent[i]

def bfs(i):
    global l
    c = 0
    q.append(i)
    while True:
        if len(q) == 0:
            break
        p = q.popleft()
        l.append(p)
        c += 1
        if not children[p] == -1:
            for j in children[p]:
                q.append(j)
    return c

n, m = map(int, input().split())
p = list(map(int, input().split()))
parent = [-1] * n
children = [-1] * n
d = [0] * n
root = []
rank = []
num = ["a"] * n
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    if num[x] == "a":
        num[x] = [y]
    else:
        num[x].append(y)
    if num[y] == "a":
        num[y] = [x]
    else:
        num[y].append(x)
    if d[x] == d[y] == 0:
        root.append(x)
        rank.append(1)
        children[x] = [y]
        parent[y] = x
        d[x] = 1
        d[y] = 1
    elif d[x] == 1 and d[y] == 0:
        r = get_root(x)
        children[r].append(y)
        parent[y] = r
        d[y] = 1
    elif d[x] == 0 and d[y] == 1:
        r = get_root(y)
        children[r].append(x)
        parent[x] = r
        d[x] = 1
    else:
        s = get_root(x)
        t = get_root(y)
        if not s == t:
            i = rank[root.index(s)]
            j = rank[root.index(t)]
            if i >= j:
                parent[t] = s
                children[s].append(t)
                if i == j:
                    rank[root.index(s)] += 1
            else:
                parent[s] = t
                children[t].append(s)

ans = 0
for i in range(n):
    if parent[i] == -1 and children[i] != -1:
        l = []
        bfs(i)
        p0 = list(l)
        for j in l:
            pp = p[j] - 1
            p0.append(pp)
        k = len(p0)
        ans += k - len(set(p0))
    elif parent[i] == -1:
        if p[i] - 1 == i:
            ans += 1
print(ans)

### FIXED CODE ###

def get_root(s):
    if s != root[s]:
        root[s] = get_root(root[s])
        return root[s]
    return s

def unite(s, t):
    root_s = get_root(s)
    root_t = get_root(t)
    if not root_s == root_t:
        if rank[s] == rank[t]:
            root[root_t] = root_s
            rank[root_s] += 1
        elif rank[s] > rank[t]:
            root[root_t] = root_s
        else:
            root[root_s] = root_t

def same(s, t):
    if get_root(s) == get_root(t):
        return True
    else:
        return False

n, m = map(int, input().split())
p = list(map(int, input().split()))
root = [i for i in range(n)]
rank = [1 for _ in range(n)]
for _ in range(m):
    x, y = map(int, input().split())
    unite(x - 1, y - 1)
ans = 0
for i in range(n):
    if get_root(i) == get_root(p[i] - 1):
        ans += 1
print(ans)
### BUGGY CODE ###

import heapq
N, M = map(int, input().split())
S = [[0] for _ in range(M)]
for _ in range(N):
    a, b = map(int, input().split())
    if M < a:
        continue
    heapq.heappush(S[M-a], -b)

ans = heapq.heappop(S[M-1])
for i in range(M-2, -1, -1):
    for num in S[i+1]:
        heapq.heappush(S[i], num)
    ans += heapq.heappop(S[i])
print(-ans)

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
S = list()
A = [list() for _ in range(M+1)]
for _ in range(N):
    a, b = map(int, input().split())
    if M < a:
        continue
    heapq.heappush(A[a], -b)

ans = 0
for i in range(1, M+1):
    for num in A[i]:
        heapq.heappush(S, num)
    if S == []:
        continue
    ans -= heapq.heappop(S)
print(ans)
### BUGGY CODE ###

from operator import itemgetter
from collections import deque
import sys

def main():
    n = int(input())  
    keys = map(lambda i:(map(int,sys.stdin.readline().split())+[i]),xrange(n))

    keys.sort(key=itemgetter(0))
    id_m = len(keys)/2
    root = Node(keys[id_m][:2],keys[id_m][2])
    if id_m != 0:
        recursive_add_Node(root,keys[:id_m],1)
    if id_m+1 != len(keys):
        recursive_add_Node(root,keys[id_m+1:],1)

    q = int(input())
    for i in xrange(q):
        sx, tx, sy, ty = map(int,raw_input().split())
        nums = deque()
        find(root,[sx,sy],[tx,ty],0,nums)
        nums = list(nums)
        nums.sort()
        map(lambda i:sys.stdout.write("{}\n".format(i)), nums)
        print ("")

def find(z,s,t,d,nums):
    if(s[0]<=z.key[0]<=t[0])and(s[1]<=z.key[1]<=t[1]):
        nums.append(z.num)
    d += 1
    xy = d%2
    if (z.left != None)and(z.key[xy]>=s[xy]):
        find(z.left,s,t,d,nums)    
    if (z.right != None)and(z.key[xy]<=t[xy]):
        find(z.right,s,t,d,nums)

def add_Node(root,k,n):
    y = None
    x = root
    d = 0
    xy = 0
    while(x != None):
        d += 1
        xy = d%2
        y = x
        if x.key[xy] > k[xy]:
            x = x.left
        else:
            x = x.right
    
    z = Node(k,n)

    if y.key[xy] > k[xy]:
        y.left = z
    else:
        y.right = z
        
def recursive_add_Node(root,k,d):
    k.sort(key=itemgetter(d%2))
    len_k = len(k)
    id_m = len_k/2
    add_Node(root,k[id_m][:2],k[id_m][2])
   
    if id_m != 0:
        recursive_add_Node(root,k[:id_m],d+1)
    if id_m+1 != len_k:
        recursive_add_Node(root,k[id_m+1:],d+1)

class Node():
    def __init__(self,k,n):
        self.key   = k
        self.num   = n
        self.left  = None
        self.right = None
    


if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin,stdout
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = stdin.readline
 
def main():
    n = int(input())
    keys = map(lambda i: map(int,readline().split())+[i], xrange(n))
    keys.sort()

    root = int(math.sqrt(len(keys)))
 
    low = [x for x, y, i in keys[::root]]
    high = [x for x, y, i in keys[root - 1::root]] + [float('inf')]
 
    keys = [sorted(keys[i:i+root], key=itemgetter(1)) for i in range(0,len(keys),root)]
    keys_y = map(lambda k:[y for x,y,i in k], keys)

    q = int(input())
    for i in xrange(q):
        sx,tx,sy,ty = map(int,readline().split())
        
        nums = []
        for i in range(bisect_left(high, sx), bisect_right(low, tx)):
            y = keys_y[i]
            for j in range(bisect_left(y, sy), bisect_right(y, ty)):
                if sx <= keys[i][j][0] <= tx:
                    nums.append(keys[i][j][2])
        if nums:
            nums.sort()
            map(lambda n:stdout.write("{}\n".format(n)), nums)
        print("")

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

import heapq
h,w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
ch -= 1
cw -= 1
dh -= 1
dw -= 1
vec5 = []
vec = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for i in range(-2, 3):
    for j in range(-2, 3):
        if abs(i) + abs(j) < 2:
            continue
        vec5 += [(i,j)]
q = [(0, (ch, cw))]
heapq.heapify(q)
while len(q) > 0:
    c, (i,j) = heapq.heappop(q)
    if s[i][j] != '.' and s[i][j] <= c:
        continue
    s[i][j] = c
    for v in vec:
        ii = i + v[0]
        jj = j + v[1]
        if 0 <= ii < h and 0 <= jj < w and s[ii][jj] == '.':
            heapq.heappush(q, (c, (ii, jj)))
    for v in vec5:
        ii = i+v[0]
        jj = j+v[1]
        if 0 <= ii < h and 0 <= jj < w and s[ii][jj] == '.':
            heapq.heappush(q, (c+1, (ii, jj)))
if s[dh][dw] == '.':
    print(-1)
else:
    print(s[dh][dw])

### FIXED CODE ###

h,w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
ch -= 1
cw -= 1
dh -= 1
dw -= 1
vec5 = []
vec = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for i in range(-2, 3):
    for j in range(-2, 3):
        if abs(i) + abs(j) < 2:
            continue
        vec5 += [(i,j)]

c = 0
q = [(ch, cw)]
while len(q) > 0:
    nq = []
    while len(q) > 0:
        i, j = q.pop()
        s[i][j] = c
        nq += [(i,j)]
        for v in vec:
            ii = i + v[0]
            jj = j + v[1]
            if 0 <= ii < h and 0 <= jj < w and s[ii][jj] == '.':
                q += [(ii, jj)]


    while len(nq) > 0:
        i, j = nq.pop()
        for v in vec5:
            ii = i+v[0]
            jj = j+v[1]
            if 0 <= ii < h and 0 <= jj < w and s[ii][jj] == '.':
                q += [(ii, jj)]
    c += 1
if s[dh][dw] == '.':
    print(-1)
else:
    print(s[dh][dw])
### BUGGY CODE ###

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 ###

int(input())
A=list(map(str,input().split()))
ans=1
if '0' in A:
  print('0')
  exit()
for i in A:
  ans*=int(i)
  if ans>10**18:
    print('-1')
    exit()
print(ans)
### BUGGY CODE ###

import sys
N = int(input())


def query(num):
    print(num)
    return int(input())


result = [-1] * (N + 1)
result[0] = query(0)
result[N] = result[0]
edge = [0, N]
if result[0] == 2:
    sys.stdout.flush()
else:
    for i in range(30):
        idx = int(abs(edge[0] - edge[1]) / 2) + min(edge)
        result[idx] = query(idx)
        if result[idx] == 2:
            sys.stdout.flush()
            break
        for i in range(2):
            r = result[edge[i]]
            if abs(edge[i] - idx) % 2 == 0:
                if r != result[idx]:
                    if i == 0:
                        edge[1] = idx
                        break
                    else:
                        edge[0] = idx
                        break
            elif abs(edge[i] - idx) % 2 == 1:
                if r == result[idx]:
                    if i == 0:
                        edge[1] = idx
                        break
                    else:
                        edge[0] = idx
                        break
    sys.stdout.flush()


### FIXED CODE ###

import sys
N = int(input())


def query(num):
    print(num)
    return input()


result = [-1] * (N + 1)
result[0] = query(0)
result[N] = result[0]
edge = [0, N]
if result[0] == "Vacant":
    sys.stdout.flush()
else:
    for i in range(30):
        idx = int(abs(edge[0] - edge[1]) / 2) + min(edge)
        result[idx] = query(idx)
        if result[idx] == "Vacant":
            sys.stdout.flush()
            break
        for i in range(2):
            r = result[edge[i]]
            if abs(edge[i] - idx) % 2 == 0:
                if r != result[idx]:
                    if i == 0:
                        edge[1] = idx
                        break
                    else:
                        edge[0] = idx
                        break
            elif abs(edge[i] - idx) % 2 == 1:
                if r == result[idx]:
                    if i == 0:
                        edge[1] = idx
                        break
                    else:
                        edge[0] = idx
                        break
    sys.stdout.flush()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
# import math
# import numpy as np
# from functools import lru_cache

args = sys.argv
if len(args) == 2:
  from IPython import embed
  em = True
else:
  em = False

# sys.setrecursionlimit(10000)

#### input
N = int(input())
# a, b = map(int, input().split())
# a = list(map(int, input().split()))
# a = list(map(lambda x: int(x)*(-1), a))  # 各要素を-1倍


# n = int(input())
# t = [int(input()) for i in range(n)]
if em: sys.stdin = open('/dev/tty')

#### function
# @lru_cache(maxsize=10000)

#### process
I = [i for i in range(1, N+1)]
P = [i for i in range(2, N+1)]
P.append(1)

rems = [I[i] % P[i] for i in range(0, len(I))]
print(sum(rems))
# if em: embed()

## heapsort, O(NlogN)
# import heapq
# heapq.heapify(A)
# min = heapq.heappop(A)
# heapq.heappush(A, new_element)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
# import math
# import numpy as np
# from functools import lru_cache

args = sys.argv
if len(args) == 2:
  from IPython import embed
  em = True
else:
  em = False

# sys.setrecursionlimit(10000)

#### input
N = int(input())
# a, b = map(int, input().split())
# a = list(map(int, input().split()))
# a = list(map(lambda x: int(x)*(-1), a))  # 各要素を-1倍


# n = int(input())
# t = [int(input()) for i in range(n)]
if em: sys.stdin = open('/dev/tty')

#### function
# @lru_cache(maxsize=10000)

#### process

if N % 2 == 0:
  tmp = int(N/2)
  print(int(tmp*(N-1)))
else:
  tmp = int((N-1)/2)
  print(int(tmp*N))

# I = [i for i in range(1, N+1)]
# P = [i for i in range(2, N+1)]
# P.append(1)

# rems = [I[i] % P[i] for i in range(0, len(I))]
# print(sum(rems))

# if em: embed()

## heapsort, O(NlogN)
# import heapq
# heapq.heapify(A)
# min = heapq.heappop(A)
# heapq.heappush(A, new_element)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
Ans = []
temp = [0]*(N+1)

def factor(num):
    sqrt = num**0.5
    for i in range(1,int(num**0.5)+1):
        if i == sqrt:
            temp[i] += 1
        elif num%i == 0:
            temp[i] += 1
            temp[num//i] += 1
    return


for a,i in zip(A[::-1],range(N-1,-1,-1)):
    if a == 1 and temp[i+1] == 0:
        factor(i+1)
        Ans.append(i+1)
    elif temp[i+1]%2 != a:
        factor(i+1)
        Ans.append(i+1)
if len(Ans) == 0:
    print(0)
else:
    print(len(Ans))
    print(*Ans,sep = " ")

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Ans = []
temp = [0]*(N+1)

def factor(num):
    sqrt = num**0.5
    for i in range(1,int(num**0.5)+1):
        if i == sqrt:
            temp[i] += 1
        elif num%i == 0:
            temp[i] += 1
            temp[num//i] += 1
    return


for a,i in zip(A[::-1],range(N-1,-1,-1)):
    if a == 1 and temp[i+1] == 0:
        factor(i+1)
        Ans.append(i+1)
    elif temp[i+1]%2 != a:
        factor(i+1)
        Ans.append(i+1)
if len(Ans) == 0:
    print(0)
else:
    print(len(Ans))
    print(*Ans,sep = " ")
### BUGGY CODE ###

def getIndex(l, x, default=-1):
    return l.index(x) if x in l else default

def getLastIndex(l, x, default=-1):
    l = list(reversed(l))
    return len(l) - l.index(x) - 1 if x in l else default

N = int(input())
c = list(input())
ans = 0
while(True):
    indexW = getIndex(c, 'W')
    indexR = getLastIndex(c, 'R')
    if indexR < indexW or indexW == -1 or indexR == -1:
        break
    c[indexW] = 'R'
    c[indexR] = 'W'
    ans += 1
print(ans)


### FIXED CODE ###

W = "W"
R = "R"

N = int(input())
C = list(input())
numR = C.count(R)
result = 0
for i in range(numR):
    if C[i] == W:
        result += 1
print(result)
### BUGGY CODE ###

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

fl = True
check = []
cnt = 0
while True:
    tmp = len(check)
    for i in range(1,N):
        if H[i]-H[i-1]<0 and not i-1 in check:
            H[i-1] -= 1
            check.append(i-1)
    if cnt==3:
        break
    cnt += 1

for i in range(1,N):
    if H[i]-H[i-1]<0:
        fl = False
        break

print('Yes') if fl else print('No')

### FIXED CODE ###

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

fl = True
for i in range(1,N):
    if H[i]-H[i-1]>0:
        H[i] -= 1

for i in range(1,N):
    if H[i]-H[i-1]<0:
        fl = False
        break

print('Yes') if fl else print('No')
### BUGGY CODE ###

import collections

def factorization(n):
    pf_cnt = {1:1}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i == 0:
            cnt = 0
            while temp%i == 0:
                cnt += 1
                temp //= i
            pf_cnt[i] = cnt

    if temp != 1: pf_cnt[temp] = 1
    if not pf_cnt: pf_cnt[n] = 1

    return pf_cnt



def main():
    n = int(input())
    al = list(map(int, input().split()))

    al_not_multi = []
    dels = []
    cnt = collections.Counter(al)
    for i,v in cnt.items():
        if v == 1:
            al_not_multi.append(i)
        else:
            dels.append(i)

    if not al_not_multi:
        print(0)
        return

    al_not_multi.sort()
    primes = []
    for a in al_not_multi:
        for prime in primes + dels:
            if a%prime == 0: break
        else:
            primes.append(a)
    # print(primes)
    print(len(primes))


    # primes = {}
    # for a in al:
    #     fac = factorization(a)
    #     for prime,cnt in fac:
    #         primes.setdefault(prime,10000)
    #         primes[prime] = min(cnt, primes[prime])




if __name__ == "__main__":
    main()

### FIXED CODE ###

import collections


def main():
    n = int(input())
    al = list(map(int, input().split()))
    al.sort()

    dp = [1]*(10**6+1) 
    for a in al:
        if dp[a] >= 0:
            dp[a] -= 1
            for i in range(2,10**6//a + 1):
                dp[a*i] -= 2
    
    ans = 0
    for a in al:
        if dp[a] >= 0: ans+=1
    print(ans)


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

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

l.sort(reverse=True)
ans=0

for i in range(0,n-1):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      if l[i]+l[j]>l[k] and l[i]+l[k]>l[j] and l[k]+l[j]>l[i]:
        ans+=1
        #print(l[i],l[j],l[k])
print(ans)
    

### FIXED CODE ###

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

l.sort(reverse=True)
ans=0

for i in range(0,n-2):
  for j in range(i+1,n-1):
    left = j
    right = n
    while right-left>1:
      mid = (left + right)//2
      
      if l[i]+l[j]>l[mid] and l[i]+l[mid]>l[j] and l[mid]+l[j]>l[i]:
        left = mid
      else:
        right = mid
    #print(i,j,left)
    ans+=(left-j)
      
print(ans)
### BUGGY CODE ###

N=int(input())
if N<=10:
  if N==7 or N==9 or N==10:
    print(1)
    exit()
  else:
    print(0)
    exit()
if N%2==0:
  A=[2]
else:
  A=[1]
i=A[0]+2
while i<=N:
  A.append(i)
  i+=2
a=0
m=1
while len(A)!=0:
    A=[A[i] for i in range(len(A)) if A[i]%(5**m)==0]
    a+=len(A)
    m+=1
print(a)


### FIXED CODE ###

N=int(input())
if N%2==1:
  print(0)
  exit()
m=10
a=0
while m<=N:
  a+=N//m
  m=m*5
print(a)
### BUGGY CODE ###

INF = 10**9

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
dp = [INF for i in range(H+1)]

dp[0] = 0

for i in range(N):
    a = AB[i][0]
    b = AB[i][1]
    for j in range(H+1):
        next_j = min(j+a, H)
        dp[next_j] = min(dp[next_j], dp[j]+b)

print(dp[H])


### FIXED CODE ###

INF = 10**9

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
dp = [INF for i in range(H+1)]

dp[0] = 0

for i in range(N):
    a = AB[i][0]
    b = AB[i][1]
    for j in range(H+1):
        next_j = min(j+a, H)
        dp[next_j] = min(dp[next_j], dp[j]+b)

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

H,N = list(map(int,input().split()))
dp = [float("inf")] * (H+1)

for i in range(N):
  a,b = list(map(int,input().split()))

  for h in range(1, H+1):
    if h - a <= 0:
      dp[h] = min(dp[h], b)
    else:
      dp[h] = min(dp[h], b + dp[h - a])

print(dp[-1])

### FIXED CODE ###

H,N = list(map(int,input().split()))
dp = [float("inf")] * (H+1)

for i in range(N):
  a,b = list(map(int,input().split()))

  for h in range(1, H+1):
    if h - a <= 0:
      dp[h] = min(dp[h], b)
    else:
      dp[h] = min(dp[h], b + dp[h - a])

print(dp[-1])
### BUGGY CODE ###

input_profit = []
for x in xrange(input()):
    input_profit.append(input())
max_profit=input_profit[1]-input_profit[0]
for i in xrange(len(input_profit)-1):
    min_profit = input_profit[i]
    candidate = max(input_profit[i+1:])-min_profit
    if candidate>max_profit:
        max_profit=candidate
print max_profit

### FIXED CODE ###

input_n = input()
price1  = input()
price2  = input()
min_price = min(price1,price2)
max_profit = price2-price1
for i in xrange(input_n-2):
    input_profit = input()
    tmp = input_profit-min_price
    if max_profit<tmp:
        max_profit = tmp
    if min_price>input_profit:
        min_price = input_profit
print max_profit
### BUGGY CODE ###

import heapq
t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    # x to lowest coin
    cheapest = set()
    # (coin, x)
    search = [(d, 1, 0, 0, 0, 0)]
    first = True

    while 1:
        coin, x, add, f2, f3, f5 = heapq.heappop(search)
#         print(f'coin: {coin}, x: {x}, add: {add}, f2: {f2}, f3: {f3}, f5: {f5}')
        if (x > 1 or first) and x not in cheapest:
            first = False
            if x == n:
                print(coin)
                break
            cheapest.add(x)

            if add >=0:
                heapq.heappush(search, (coin + d, x + 1, add + 1, 0, 0, 0))
            if x - 1 > 1 and add <= 0:
                heapq.heappush(search, (coin + d, x - 1, add - 1, 0, 0, 0))
                
            if 2 * x <= 2 * n:
                heapq.heappush(search, (coin + a, 2 * x, 0, f2 + 1, f3, f5))
            if 3 * x <= 2 * n and f2 == 0:
                heapq.heappush(search, (coin + b, 3 * x, 0, f2, f3 + 1, f5))
            if 5 * x <= 2 * n and f2 == 0 and f3 == 0:
                heapq.heappush(search, (coin + c, 5 * x, 0, f2, f3, f5 + 1))
                

### FIXED CODE ###

t = int(input())

import sys
sys.setrecursionlimit(10 ** 6)

def calc(x):
    if x in dp:
        return dp[x]
    
    divs = [5, 3, 2]
    costs = [c, b, a]
    res = d * x
    for div, cost in zip(divs, costs):
        dived = x//div
        res = min(res, calc(dived) + cost + abs(x-dived*div) * d)
        if x > div:
            dived = x//div+1
            res = min(res, calc(dived) + cost + abs(x-dived*div) * d)
    dp[x] = res
    return res

for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    dp = {}
    dp[0] = 0
    dp[1] = d
    print(calc(n))
### BUGGY CODE ###

#n = int(input())
#l = list(map(int, input().split()))

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

import sys
input = sys.stdin.readline

s = input().rstrip("\n")
q= int(input())
han=0
for i in range(q):
    que=input().split()
    if len(s)==1 and que[0]=="1":
        continue

    if que[0]=="1":
        han+=1
        #print(han, s, que)
    else:
        if han%2==0:#反転なし
            if que[1]=="1":
                s=que[2]+s
            else:
                s+=que[2]
        else:#あり
            if que[1] == "1":
                s+=que[2]
            else:
                s=que[2]+s
        #print(han, s, que)

if han%2==0:
    print(s)
else:
    print(s[::-1])


### FIXED CODE ###

#n = int(input())
#l = list(map(int, input().split()))

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''


def main():
    import sys
    input = sys.stdin.readline
    s = input().rstrip("\n")
    q = int(input())
    
    qq = [input().split() for i in range(q)]
    cnt=0
    r=""
    l=""
    #print(qq)
    for que in qq:
        if que[0] == "1":
            #print("a")
            r,l=l,r
            cnt+=1
            #print(r,l,cnt)
        else:
            if que[1] == "1":
                l+=que[2]
            else:
                r+=que[2]
            #print(r,l, que)
    #print(r,l)
    if cnt%2==0:
        print(l[::-1]+s+r)
    else:
        print(l[::-1]+s[::-1]+r)



if __name__ == '__main__':
    main()