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

import collections

def main():
    s=input()
    t=input()
    n = len(s)
    cs = collections.Counter(s)
    ct = collections.Counter(t)

    for sct in ct.keys():
        if cs[sct] == 0:
            return -1
    l = 0
    lc = 0
    for c in t:
        while c != s[l]:
            l += 1
            if l == n:
                l = 0
                lc += 1
        l += 1
        if l == n:
            l = 0
            lc += 1

    return lc * n + l

print(main())

### FIXED CODE ###

import collections
import bisect

def main():
    s=input()
    t=input()
    s = s*2
    n = len(s)
    cs = collections.Counter(s)
    ct = collections.Counter(t)
    for sct in ct.keys():
        if cs[sct] == 0:
            return -1
    dc = collections.defaultdict(list)
    for i in range(n):
        dc[s[i]].append(i+1)
    res = 0
    ptl = 0
    for i in range(len(t)):
        tl = dc[t[i]][bisect.bisect_left(dc[t[i]],ptl+1)]
        res += tl - ptl
        ptl = tl - n//2 if tl > n//2 else tl
    return res

print(main())
### BUGGY CODE ###

from collections import deque
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix


def bfs(cnt, p, cn, row, col, data):
    cnt += 1
    if cnt < 3:
        for cg in graph[p]:
            d.appendleft([cnt, cg])
    if cnt == 3:
        for cg in graph[p]:
            if not cg in graph_k[cn]:
                graph_k[cn].append(cg)
                row = np.append(row, cn)
                col = np.append(col, cg)
                data = np.append(data, 1)
    return cnt, row, col, data

n, m = map(int,input().split())
edge = []
graph = [[] for i in range(n+1)]
for i in range(m):
    edge.append(list(map(int,input().split())))
    graph[edge[-1][0]].append(edge[-1][1])
s, g = map(int,input().split())

row = np.array([], dtype=int)
col = np.array([], dtype=int)
data = np.array([], dtype=int)

d = deque()
graph_k = [[] for i in range(n+1)]
for cn in range(1, n+1):
    for cg in graph[cn]:
        d.appendleft([1, cg])
    while d:
        cnt, p = d.pop()
        cnt, row, col, data = bfs(cnt, p, cn, row, col, data)
# print(graph_k)
csr = csr_matrix((data, (row, col)), shape=(n+1, n+1))
ans = shortest_path(csr, indices=s)
if np.isinf(ans[g]):
    print(-1)
else:
    print(int(ans[g]))

### FIXED CODE ###

import copy

n, m = map(int,input().split())
edge = []
graph = [[] for i in range(n+1)]
for i in range(m):
    edge.append(list(map(int,input().split())))
    graph[edge[-1][0]].append(edge[-1][1])
s, g = map(int,input().split())

INF = 10**18
ans = [[INF, INF, INF] for i in range(n+1)]
q = [s]
d = 0
while q:
    nq = []
    d += 1
    p = d % 3
    for cf in q:
        for ct in graph[cf]:
            if ans[ct][p] == INF:
                ans[ct][p] = d
                nq.append(ct)
    q = copy.deepcopy(nq)
if ans[g][0] == INF:
    print(-1)
else:
    print(ans[g][0]//3)
### BUGGY CODE ###

n,m=map(int,input().split())
ls=[int(input()) for i in range(m)]

if 1 in ls:
    steps=[1,0]
else:
    steps=[1,1]

while len(steps)<=n:
    this_step=len(steps)
    if this_step in ls:
        ap=0
    else:
        ap=steps[-1]+steps[-2]
    steps.append(ap)

print(steps[-1]%1000000007)

### FIXED CODE ###

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
a = set(a)
mod = 10**9+7
dp = [0]*(n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
for i in range(2,n+1):
    if i not in a:
        dp[i] = dp[i-1]+dp[i-2]
print(dp[-1]%mod)
### BUGGY CODE ###

n= int(input())
a=list(map(int, input().split()))
b=[]
for i in range(n):
    print(a.index(i+1)+1,end=" ")

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=["0"]*n
for i in range(n):
    ans[a[i]-1]=str(i+1)
print(" ".join(ans))
### BUGGY CODE ###

N = int(input())
points = []
for i in range(0, N):
    points.append(list(map(int, input().split(' '))))
abcd = set(sum(points, []))
count = 0
for a in abcd:
    for b in abcd:
        for c in abcd:
            for d in abcd:
                if a == c and b == d:
                    continue
                p = []
                if [a, b] not in points:
                    p.append([a, b])
                if [a, d] not in points:
                    p.append([a, d])
                if [c, b] not in points:
                    p.append([c, b])
                if [c, d] not in points:
                    p.append([c, d])
                if len(p) == 1:
                    count += 1
                    points.append(p[0])
print(count)

### FIXED CODE ###

N = int(input())
points = []
for i in range(0, N):
    points.append(list(map(int, input().split(' '))))
X = dict()
Y = dict()
count = 0
for p in points:
    if p[0] not in X.keys():
        X[p[0]] = []
    X[p[0]].append(p[1])
    if p[1] not in Y.keys():
        Y[p[1]] = []
    Y[p[1]].append(p[0])
while len(X.items()) > 0:
    item = list(X.items())[0]
    del X[item[0]]
    queue = [item]
    point_dict = {'x': [], 'y': []}
    queue_is_x = [True]
    while len(queue) > 0:
        item = queue.pop(0)
        is_x = queue_is_x.pop(0)
        if is_x:
            point_dict['x'].append(item[0])
            for i in item[1]:
                if i in Y.keys():
                    queue.append((i, Y[i]))
                    queue_is_x.append(False)
                    del Y[i]
        else:
            point_dict['y'].append(item[0])
            for i in item[1]:
                if i in X.keys():
                    queue.append((i, X[i]))
                    queue_is_x.append(True)
                    del X[i]
    # print((point_dict['x']))
    # print(len((point_dict['x'])))
    # print((point_dict['y']))
    # print(len((point_dict['y'])))
    count += len(set(point_dict['x'])) * len(set(point_dict['y']))

print(count - len(points))
### BUGGY CODE ###

input()
da = list(map(int,input().split()))
al = 0
ta = [0]*len(da)
for i in range(len(da)):
  if i == 0:
    for j in range(len(da)-i):
      if j == 0:
        ta[0] = da[i]
      else:
        ta[j] = ta[j-1] + da[i+j]
      if ta[j] == 0:
        al += 1
  else:
    for j in range(len(da)-i):
      ta[j+i] -= da[i -1]
      if ta[j+i] == 0:
        al += 1
print(al)

### FIXED CODE ###

from collections import defaultdict
 
n = int(input())
a = [int(i) for i in input().split()]
 
s = 0
d = defaultdict(int)
ans = 0
d[0] = 1
 
for i in a:
    s += i
    ans += d[s]
    d[s] += 1
 
print(ans)
### BUGGY CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

d = {}
m = []

if len(A) == 2:
    print(max(A))
    exit()

for i in range(N):
    _A = []
    _A.extend(A[0:i])
    _A.extend(A[i+1:N])

    for j in range(1, len(_A)):
        if j == 1:
            tmp = gcd(_A[j], _A[j-1])
        else:
            tmp = gcd(_A[j], tmp)
    m.append(tmp)
print(max(m))


### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

L = [0] * N
R = [0] * N

L[0] = A[0]
R[N-1] = A[-1]

for n in range(1, N):
    L[n] = gcd(L[n - 1], A[n])
for n in reversed(range(N-1)):
    R[n] = gcd(R[n + 1], A[n])

ans = 0
for n in range(N):
    if n == 0:
        ans = max(ans, R[n+1])
    elif n == N - 1:
        ans = max(ans, L[n-1])
    else:
        ans = max(ans, gcd(L[n-1], R[n+1]))

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

import array

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

for i in range(m):
        a[a.index(max(array.array("L", a)))] //= 2

print(sum(a))

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = list(map(lambda x: x*(-1), a))
heapq.heapify(a)
for i in range(m):
        maxVal = heapq.heappop(a)*(-1)
        heapq.heappush(a, (maxVal//2)*(-1))

print((-1)*(sum(a)))
### BUGGY CODE ###

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

path = [1]
current_pos = 1
detect_loop = False

while not detect_loop:
    current_pos = A[current_pos - 1]
    if current_pos in path:
        detect_loop = True
    path.append(current_pos)

loop = path[(idx := path.index(current_pos)):-1]
straight = path[:idx]

if K < len(straight):
    print(straight[K])
else:
    print(loop[(K - len(straight)) % len(loop)])



### FIXED CODE ###

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

path = [1]
checked = [False] * N
detect_loop = False

current_pos = 1
while not detect_loop:
    current_pos = A[current_pos - 1]

    if checked[current_pos - 1]:
        detect_loop = True

    path.append(current_pos)
    checked[current_pos - 1] = True

loop = path[(idx := path.index(current_pos)):-1]
straight = path[:idx]

if K < len(straight):
    print(straight[K])
else:
    print(loop[(K - len(straight)) % len(loop)])
### BUGGY CODE ###

N = int(input())
a_list = list(map(int, input().split()))
a_list.sort()
cnt = 0
for i in range(N):
    if a_list[i] > N:
        cnt += len(a_list[i:])
        break
for i in range(1, N+1):
    if a_list.count(i) > i:
        cnt += a_list.count(i) - i
    elif a_list.count(i) < i:
        cnt += a_list.count(i)
    else:
        pass
print(cnt)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import Counter


N = int(input())
a_list = list(map(int, input().split()))
a_list_unique = list(set(a_list))
a_cnt = Counter(a_list)
cnt = 0
for i in a_list_unique:
    a_dict = a_cnt[i]
    if i <= a_dict:
        cnt +=  a_dict - i
    else:
        cnt += a_dict
print(cnt)
### BUGGY CODE ###


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 




n,k = [int(i) for i in readline().split()]
a = [0]+[int(i) for i in readline().split()] + [0]

n += 2

INF  = 10**18

diff = [0]
for i in range(n-1):
    diff.append(max(a[i+1]-a[i],0))

from itertools import accumulate
acc = list(accumulate(diff))

ans = {}

def calc(p,q,k):
    if (p,q,k) in ans: return ans[(p,q,k)]
    if k == 0:
        res = acc[q] - acc[p]
    elif k == q-p-1:
        res = max(0,a[q] - a[p])
    else:
        res = INF
        for i in range(p+1,q):
            for l in range(min(k+1,i-p)):
                if k-l > q-p-1: break
                #if p ==1 and q == 4 and k == 1: print(i,l)
                res = min(res, calc(p,i,l)+calc(i,q,k-l))
    #print(p,q,k,res)    
    ans[(p,q,k)] = res    
    return res

#print(acc)
#print(a,n)
print(calc(0,n-1,k))
#print(calc(0,n-1,k))



        





### FIXED CODE ###


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 




n,k = [int(i) for i in readline().split()]
a = [0]+[int(i) for i in readline().split()]

n += 1

INF = 10**18

K = n-k-1

dp = [[INF]*n for _ in range((K+1))]
dp[0][0] = 0



for i in range(1,n):
    ndp = [c[:] for c in dp]
    
    for l in range(min(i,K)):
        for now in range(0,i):
            ndp[l+1][i] = min(ndp[l+1][i], ndp[l][now]+max(0,a[i]-a[now]))
    
    dp = ndp
    #print(dp)    

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

from collections import deque

N = int(input())
edge_list = [list(map(int, input().split())) for i in range(N-1)]
colors = [[0 for j in range(N)] for i in range(N)]
reached = [False for i in range(N)]
edges = [[] for j in range(N)]
for edge in edge_list:
    a = edge[0] - 1
    b = edge[1] - 1
    edges[a].append(b)
    edges[b].append(a)

color_num = 0
for i in range(N):
    if len(edges[i]) > color_num:
        color_num = len(edges[i])


color_stack = deque([[]])
node_stack = deque([0])
while len(node_stack) > 0:
    current = node_stack.pop()
    reached[current] = True
    used_colors = color_stack.pop()
    nodes = edges[current]
    if (len(used_colors)) == 0:
        can_color = [i+1 for i in range(color_num)]
    else:
        can_color = [i+1 for i in range(color_num) if i != used_colors[0]-1]
    for node in nodes:
        if reached[node]:
            continue
        color = can_color.pop()
        node_stack.append(node)
        color_stack.append([color])
        colors[current][node] = color
        colors[node][current] = color

print(color_num)
for edge in edge_list:
    a = edge[0] - 1
    b = edge[1] - 1
    print(colors[a][b])



### FIXED CODE ###

from collections import deque
from functools import reduce

n = int(input())
colors = [0]*(n-1)
mat = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1

    mat[a].append((i, b))
    mat[b].append((i, a))

q = deque()
max_len = reduce(lambda a, x:max(a, len(x)), mat, 0)
q.append(0)
while len(q) > 0:
    current = q.popleft()

    used_colors = set([colors[p[0]] for p in mat[current] if colors[p[0]] > 0])
    col = 1

    for p in mat[current]:
        if colors[p[0]] > 0:
            continue
        while col in used_colors:
            col += 1
        colors[p[0]] = col
        col += 1
        q.append(p[1])
print(max_len)
for col in colors:
    print(col)
### BUGGY CODE ###

N = input()
P = list(map(int, input().split()))
count = 0

for i in range(int(N)):
    if P[i] ==(min(P[:i+1])):
            count = count + 1
print(count)

### FIXED CODE ###

N = input()
P = list(map(int, input().split()))
count = 0

now_mini= 1<<20
for i in P:
    if i < now_mini:
        count = count + 1
        now_mini=i
print(count)
### BUGGY CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
ans = 0
n_max = 0
place = 0
for i in range(N - K + 1):
	n_max = max(n_max , sum(P[i:i+K]))
	if n_max == sum(P[i:i+K]):
		place = i
for i in range(place,place + K):
	semi = 0
	for j in range(P[i] + 1):
		semi += j
	ans += semi / P[i]
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
ans = 0
n_max = 0
place = 0
n_sum = sum(P[:K])
for i in range(N - K):
	n_sum = n_sum - P[i] + P[i+K]
	if n_max <= n_sum:
		n_max = n_sum
		place = i + 1
for i in range(place,place + K):
	ans += (1 + P[i]) /2 
print(ans)
### BUGGY CODE ###

def make_ps(n):
    tbl = [False, True, False, False, False, True] * (n // 6 + 1)
    for i in range(1, 4):
        tbl[i] = not tbl[i]
    p, stp, sqrt = 5, 2, n ** 0.5
    while p < sqrt:
        for i in range(p ** 2, n, 2 * p):
            tbl[i] = False
        while True:
            p += stp
            stp = 6 - stp
            if tbl[p]:
                break
    return [i for i in range(n) if tbl[i]]
while True:
    n = int(input())
    ps = make_ps(n)
    if not n:
        break
    if n % 2:
        print(1 if n - 2 in ps else 0)
    else:
        res = 0
        for p in ps:
            if p > n / 2:
                break
            if n - p in ps:
                res += 1
    print(res)

### FIXED CODE ###

def make_tbl(n):
    tbl = [False, True, False, False, False, True] * (n // 6 + 1)
    for i in range(1, 4):
        tbl[i] = not tbl[i]
    p, stp, sqrt = 5, 2, n ** 0.5
    while p < sqrt:
        for i in range(p ** 2, n, 2 * p):
            tbl[i] = False
        while True:
            p += stp
            stp = 6 - stp
            if tbl[p]:
                break
    return tbl
tbl = make_tbl(50000)
ps = [i for i in range(50000) if tbl[i]]
while True:
    n = int(input())
    if not n:
        break
    res = 0
    if n % 2:
        if tbl[n - 2]:
            res += 1
    else:
        res = 0
        for p in ps:
            if 2 * p > n:
                break
            if tbl[n - p]:
                res += 1
    print(res)
### BUGGY CODE ###

n = int(input().strip())

count_by_kw = {}
for i in range(n):
    s=''.join(sorted(input().strip()))
    if s in count_by_kw.keys():
        count_by_kw[s]+=1
    else:
        count_by_kw[s]=1

c=list(count_by_kw.values())
ans=0
for val in c:
    ans+=val*(val-1)//2

print(ans)

### FIXED CODE ###

n = int(input().strip())

count_by_kw = {}
for i in range(n):
    s=''.join(sorted(input().strip()))
    if s in count_by_kw.keys():
        count_by_kw[s]+=1
    else:
        count_by_kw[s]=1

c=list(count_by_kw.values())
ans=0
for val in c:
    ans+=val*(val-1)//2

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

N=int(input())
a_list = list(map(int, input().split()))
res = 1
for a in a_list:
    res *= a

print(res if res <= 10**18 else -1)

### FIXED CODE ###

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

if 0 in a_list:
    print(0)
    exit()

res = 1
for a in a_list:
    res *= a
    if res > 10**18:
        print(-1)
        exit()

print(res)
### BUGGY CODE ###

n,k=map(int,input().split())
li=list(map(int,input().split()))
ans=[0]*n
ans[1]=abs(li[0]-li[1])
for i in range(2,n):
    ans[i]=min([y+z for (y,z) in zip(map(lambda x: abs(x-li[i]),li[max(0,i-k):i]),ans[max(0,i-k):i])])
    
print(ans[n-1])


### FIXED CODE ###

n,k=map(int,input().split())
li=list(map(int,input().split()))
ans=[0]*n
ans[1]=abs(li[0]-li[1])
for i in range(2,n):
    ans[i]=min([y+z for (y,z) in zip(map(lambda x: abs(x-li[i]),li[max(0,i-k):i]),ans[max(0,i-k):i])])
    
print(ans[n-1])
### BUGGY CODE ###

"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
"""

from __future__ import division
from sys import stdin, maxint

def lcs(s1, s2):
	dp = [[0 for _ in xrange(len(s2) + 1)] for _ in xrange(2)]

	for i in xrange(1, len(s1) + 1):
		for j in xrange(1, len(s2) + 1):
			if s1[i - 1] == s2[j - 1]:
				dp[i & 1][j] = dp[1 - i & 1][j - 1] + 1
			else:
				dp[i & 1][j] = max(dp[1 - i & 1][j], dp[i & 1][j - 1])

	return dp[len(s1) & 1][len(s2)]

if __name__ == '__main__':
	tc = int(stdin.readline())
	for _ in range(tc):
		sa = stdin.readline().strip()
		sb = stdin.readline().strip()
		print(lcs(sa, sb))

### FIXED CODE ###

"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
"""


def lcs():
	s1 = raw_input()
	s2 = raw_input()
	la, lb = len(s1), len(s2)
	dp1 = [0 for _ in range(lb + 1)]

	for i in range(la):
		dp2 = dp1 + []
		for j in range(lb):
			if s1[i] == s2[j]:
				dp1[j + 1] = dp2[j] + 1
			elif dp1[j + 1] < dp1[j]:
				dp1[j + 1] = dp1[j]

	return dp1[-1]

if __name__ == '__main__':
	tc = int(raw_input())
	for _ in range(tc):
		print(lcs())
### BUGGY CODE ###

import itertools
while 1:
	n = input()
	if n == 0: break
	s = map(int,raw_input().split())
	sm = ans = sum(s)
	for i in range(1,n-1):
		for party in itertools.combinations(s,i):
			ans = min(ans,abs(sm-2*sum(party)))
	print ans

### FIXED CODE ###

def S(i,x,y):
	if 2*x >= A: return 2*x-A
	if 2*y >= A: return 2*y-A
	return min(S(i+1,x+a[i],y),S(i+1,x,y+a[i]))
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))[::-1]
	A = sum(a)
	print S(1,a[0],0)
### BUGGY CODE ###

"""import sys
input = sys.stdin.readline
input = sys.stdin.buffer.readline

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
"""

def main():
    S = input()
    Q = int(input())
 
    qi = [[0 for j in range(3)] for i in range(Q)]
    for i in range(Q):
        n = input()
        if n != 1:
            qi[i]= n.split()
        else:
            qi[i][0] = 1

    #for i in range(Q):

        if qi[i][0] == "1":
            S = S[::-1]
        elif qi[i][0] == "2":
            if qi[i][1] == "1":
                S = str(qi[i][2]) + S
            elif qi[i][1] == "2":
                S = S + str(qi[i][2]) 
    print(S)

if __name__ == "__main__":
	main()

### FIXED CODE ###

from collections import deque

def main():
    S = deque(input())
    
    Q = int(input())
    count = 1

    for i in range(Q):
        n = input()
        if n == "1":
            #qi[i][0] = 1
            count += 1
        else:
            q= list(n.split())
            if (count % 2 == 1 and q[1] == "1") or(count % 2 == 0 and q[1] == "2"):
                S.appendleft(q[2])
            else:
                S.append(q[2]) 

    if count % 2 == 0:
        S.reverse()
    print(''.join(S))

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

from collections import deque
import sys
def longest_subsequence(sequence):
  table = [(1, sequence[0])]
  for x in sequence[1:]:
    maxlen = 0
    for (L, z) in table:
      if z < x: # strict increasing
        maxlen = max(maxlen, L)
    table.append((maxlen+1, x))
  return max(L for (L, _) in table)
n = int(input())
a = list(map(int, input().split()))
adjacent = {i: [] for i in range(n)}
for _ in range(n-1):
  node1, node2 = map(int, input().split())
  node1 -= 1
  node2 -= 1
  adjacent[node1].append(node2)
  adjacent[node2].append(node1)
node_sequences = [[] for _ in range(n)]
visited = [False]*n
queue_nodes = deque()
queue_nodes.append((0, []))
while queue_nodes:
  (vertex, sequence) = queue_nodes.popleft()
  visited[vertex] = True
  node_sequences[vertex] = sequence + [a[vertex]]
  for node in adjacent[vertex]:
    if not visited[node]:
      queue_nodes.append((node, node_sequences[vertex]))
[print(longest_subsequence(sequence)) for sequence in node_sequences]

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
from bisect import bisect, bisect_left
def longest_subsequence(sequence):
  subsequence = [float("inf") for _ in range(len(sequence)+1)]
  subsequence[0] = float("-inf")
  for value in sequence:
    j = bisect(subsequence, value)
    if subsequence[j-1] != value: # strict increasing
      subsequence[j] = value
  return bisect_left(dp, float("inf"))-1
# print(longest_subsequence([9, 13, 2, 10, 4, 13, 11, 13]))
# sys.exit()
def dfs(vertex):
  visited[vertex] = True
  value = a[vertex]
  j = bisect(subsequence, value)
  previous = subsequence[j]
  if subsequence[j-1] != value: # strict increasing
    subsequence[j] = value
  ans[vertex] = bisect_left(subsequence, float("inf"))-1
  for node in adjacent[vertex]:
    if not visited[node]:
      dfs(node)
  subsequence[j] = previous
  return
n = int(input())
a = list(map(int, input().split()))
adjacent = {i: [] for i in range(n)}
for _ in range(n-1):
  node1, node2 = map(int, input().split())
  node1 -= 1
  node2 -= 1
  adjacent[node1].append(node2)
  adjacent[node2].append(node1)
visited = [False]*n
ans = [0]*n
subsequence = [float("inf") for _ in range(n+1)]
subsequence[0] = float("-inf")
dfs(0)
[print(value) for value in ans]
### BUGGY CODE ###

import sys
sys.setrecursionlimit(5000)
n = int(input())
a = list(map(int, input().split()))

dp = [[-1]*(n+1) for i in range(n)]
for i in range(n):
    dp[i][i] = 0

def rec(i=0, j=n):
    if i == j:
        return 0
    if dp[i][j] != -1:
        return dp[i][j]
    # 太郎
    if (n - (j-i))%2==0:
        dp[i][j] = max(a[i] + rec(i+1,j), a[j-1] +rec(i,j-1))
    else:
        dp[i][j] = min(-a[i] + rec(i+1,j), -a[j-1] +rec(i,j-1))
    return dp[i][j]
print(rec())

### FIXED CODE ###

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

dp = [[0]*(n+1) for i in range(n+1)]
for l in range(1,n+1):
    for i in range(n+1-l):
        j = i+l
        if (n-l)%2 == 0:
            dp[i][j] = max(dp[i+1][j]+a[i], dp[i][j-1]+a[j-1])
        else:
            dp[i][j] = min(dp[i+1][j]-a[i], dp[i][j-1]-a[j-1])
print(dp[0][-1])
### BUGGY CODE ###

S = input()
Q = int(input())

for _ in range(Q):
    op = input().split(" ")
    if int(op[0]) == 1:
        S = S[::-1]
    else:
        f, ch = op[1:]
        if f == "1":
            S = ch + S
        else:
            S = S + ch

print(S)

### FIXED CODE ###

from collections import  deque
S = input()
Q = int(input())
rev = 1
q = deque(list(S))
for _ in range(Q):
    op = input().split(" ")
    if int(op[0]) == 1:
        rev *= -1
    else:
        f, ch = op[1:]
        if rev == 1:
            if f == "1":
                q.appendleft(ch)
            else:
                q.append(ch)
        else:
            if f == "1":
                q.append(ch)
            else:
                q.appendleft(ch)
S = "".join(q)
if rev == -1:
    S = S[::-1]
print(S)