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

from collections import defaultdict, deque

N = int(input())
E = [[] for _ in range(N+1)]
inp = []
for i in range(N-1):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
    inp.append((a, b))


# node: (id, parent_id)
root_node = (1, -1)
open_list = deque([root_node])
n2c = defaultdict(list)
ans = {}
colors = [-1]*(N-1)
while open_list:
    cur_node = open_list.popleft()
    cur_id, parent_id = cur_node
    adj_id_list = E[cur_id]
    for child_id in adj_id_list:
        if child_id == parent_id:
            continue
        color = 1
        while True:
            if not color in n2c[cur_id]:
                n2c[cur_id].append(color)
                n2c[child_id].append(color)
                ans[(cur_id, child_id)] = color
                break
            color += 1
        open_list.append((child_id, cur_id))

print(max(list(map(lambda x:len(x), n2c.values()))))
for a, b in inp:
    if (a, b) in ans.keys():
        print(ans[(a, b)])
    else:
        print(ans[(b, a)])

### FIXED CODE ###

from collections import defaultdict, deque

N = int(input())
E = [[] for _ in range(N+1)]
edge_order = []
for i in range(N-1):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
    edge_order.append(b)


# node: (id, parent_id)
root_node = (1, -1)
open_list = deque([root_node])
ans = {}
colors = [-1]*(N+1)
while open_list:
    cur_node = open_list.popleft()
    cur_id, parent_id = cur_node
    adj_id_list = E[cur_id]
    c = 1
    for child_id in adj_id_list:
        if child_id == parent_id:
            continue
        if c == colors[cur_id]:
            c += 1
        colors[child_id] = c
        c += 1
        open_list.append((child_id, cur_id))

print(max(colors))
for i in edge_order:
    print(colors[i])
### BUGGY CODE ###

H, N = map(int, input().split())
Magic = [list(map(int, input().split())) for i in range(N)]
MAX_COST = max(Magic)[1]
 
# dp[damage] := モンスターに damage を与えるために必要な最小コスト
dp = [float('inf')] * (H + 1)
dp[0] = 0
for h in range(H):
    for damage, cost in Magic:
        next_index = min(h + damage, H)
        dp[next_index] = min(dp[next_index], dp[h] + cost)
print(dp[-1])

### FIXED CODE ###

H, N = map(int, input().split())
Magic = [list(map(int, input().split())) for i in range(N)]
MAX_COST = max(Magic)[1]
 
# dp[damage] := モンスターに damage を与えるために必要な最小コスト
dp = [float('inf')] * (H + 1)
dp[0] = 0
for h in range(H):
    for damage, cost in Magic:
        next_index = min(h + damage, H)
        dp[next_index] = min(dp[next_index], dp[h] + cost)
print(dp[-1])
### BUGGY CODE ###

import sys
input=sys.stdin.readline

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    #最寄りまで-してく場合
    x1,x2=n//ttf,n%ttf
    if ttf-x2>=x2:
        if check.get(x1) is not None:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

    #最寄りまで+1してく場合
    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>x2:
        if check.get(x1) is not None:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

### FIXED CODE ###

import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])
### BUGGY CODE ###

def check():
    count1 = 0
    for i in range(4):
        if A[i] == B[i]:
            count1 += 1
    count2 = 0
    for v in B:
        if v in A:
            count2 += 1
    Hit = count1
    Blow = count2 - count1
    
    print Hit, Blow
    
while True:
    try:
        A = list(raw_input().split())
        B = list(raw_input().split())
        check()
    except EOFError:
        pass

### FIXED CODE ###

def check():
    count1 = 0
    for i in range(4):
        if A[i] == B[i]:
            count1 += 1
    count2 = 0
    for v in B:
        if v in A:
            count2 += 1
    Hit = count1
    Blow = count2 - count1
    
    print Hit, Blow
    
while True:
    try:
        A = list(raw_input().split())
        B = list(raw_input().split())
        check()
    except EOFError:
        break
### BUGGY CODE ###

n,m=map(int,input().split())
data=[[] for _ in range(m+1)]
for _ in range(n):
    a,b=map(int,input().split())
    if a<=m:
        data[a].append(b)
for i in range(1,m+1):
    data[i].sort()
s=0
for i in range(1,m+1):
    a=0
    count=0
    for j in range(1,i+1):
        if data[j]:
            if a<data[j][-1]:
                a=data[j][-1]
                count=j
    if count!=0:
        s+=a
        data[count].pop()
print(s)

### FIXED CODE ###

from heapq import heappush, heappop
from collections import deque
n,m=map(int,input().split())
data=[[] for _ in range(m+1)]
for _ in range(n):
    a,b=map(int,input().split())
    if a<=m:
        data[a].append([-b,a])
for i in range(1,m+1):
    data[i].sort()
    data[i]=deque(data[i])
h=[]
s=0
for i in range(1,m+1):
    if data[i]:
        heappush(h,data[i].popleft())
    if h:
        d=heappop(h)
        if data[d[1]]:
            heappush(h,data[d[1]].popleft())
        s+=-d[0]
print(s)
### BUGGY CODE ###

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

Asum = [0]*(N+1)
for i in range(N):
    Asum[i+1] = Asum[i] + A[i]

ans = 0
for i in range(N):
    ans += Asum[i+1:].count(Asum[i])
print(ans)

### FIXED CODE ###

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

Asum = [0]*(N+1)
for i in range(N):
    Asum[i+1] = Asum[i] + A[i]

Asum.sort()
ans = 0
same = 1
tmp = Asum[0] - 1
for i in range(N+1):
    if tmp != Asum[i]:
        ans += same*(same - 1)//2
        tmp = Asum[i]
        same = 1
    else:
        same += 1
ans += same*(same - 1)//2
print(ans)
### BUGGY CODE ###

l = reversed(list(input()))
mod = 10 ** 9 + 7
ans = 1
for key, i in enumerate(l):
    if i == "1":
        ans =  ((3 ** key) % mod + 2 * ans) % mod
print(ans)

### FIXED CODE ###

l = reversed(list(input()))
mod = 10 ** 9 + 7
ans = 1
for key, i in enumerate(l):
    if i == "1":
        ans = (pow(3,key,mod) % mod + 2 * ans) % mod
print(ans)
### BUGGY CODE ###

x, y, z, k = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
c = list(map(int, input().split(' ')))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
t = []
for i in set(range(x)):
    for j in set(range(y)):
        for l in set(range(z)):
            if i * j * l < k:
                t.append(a[i]+b[j]+c[l])
            else:
                break
t.sort(reverse=True)
for i in range(k):
    print(t[i])


### FIXED CODE ###

x,y,z,K=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
ans=[]
for i in range(x):
  for j in range(y):
    for k in range(z):
      if (i+1)*(j+1)*(k+1)<=K:
        ans.append(a[i]+b[j]+c[k])
      else:
        break
ans.sort(reverse=True)
for i in range(K):
  print(ans[i])
### BUGGY CODE ###

from fractions import gcd
from functools import reduce
n = int(input())
al = list(map(int,input().split()))

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

p = lcm_list(al)

ans = 0

for a in al:
    ans += p // a
    ans %= 10**9 + 7

print(ans)


### FIXED CODE ###

import fractions
n = int(input())
al = list(map(int,input().split()))
al = sorted(al)
p = al[0]
for i in range(1, n):
    p = p * al[i] // fractions.gcd(p, al[i])

ans = 0

for a in al:
    ans += p // a

print(ans % (10**9 + 7))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
inf = 10 ** 9 + 7
total = 0

l = len(a)

for i in range(l - 1):
    for j in range(i + 1, l):
        a[i] %= inf
        a[j] %= inf
        total += (a[i]*a[j])

print(total % inf)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
inf = 10 ** 9 + 7

S = sum(a)
S2 = 0

for i in a:
    S2 += i * i

print((S*S - S2)//2 % inf)
### BUGGY CODE ###

import math

N, K = map(int, input().split(" "))
# A = list(map(minus_one, list(map(int, input().split(" ")))))

doubling_table = [list(map(lambda n: n - 1, list(map(int, input().split(" ")))))]
for i in range(0,int(math.log2(K))):
    doubling_table.append([doubling_table[i][doubling_table[i][j]] for j in range(0,N)])
#     next_table = [doubling_table[i][doubling_table[i][j]] for j in range(0,N)]
#     doubling_table.append(next_table)
# print(doubling_table)

city = 0
for i in range(int(math.log2(K)), -1, -1):
    if K >= 2 ** i:
        K, city = K - 2 ** i, doubling_table[i][city] 
#         city = doubling_table[i][city]
        
print(city + 1)

### FIXED CODE ###

import math

def minus_one(n):
    return n - 1

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

doubling_table = [A]
for i in range(0,int(math.log2(K))):
    doubling_table.append([doubling_table[i][doubling_table[i][j]] for j in range(0,N)])
#     next_table = [doubling_table[i][doubling_table[i][j]] for j in range(0,N)]
#     doubling_table.append(next_table)
# print(doubling_table)

city = 0
for i in range(int(math.log2(K)), -1, -1):
    if K >= 2 ** i:
        K -= 2 ** i
        city = doubling_table[i][city]
        
print(city + 1)
### BUGGY CODE ###

s = input()
n = len(s)
xy = tuple(map(int, input().split()))

# 各ターンで、後何回動けるか
move = [0]
for i in range(n):
    if s[-i-1]=='F':
        move.append(move[-1]+1)
    else:
        move.append(move[-1])
move.reverse()

# 各ターンで行きうる位置
dp = [set() for j in range(n+1)]
dp[0].add((0,0,0))

if move[0]%2!=(sum(xy))%2:
    print('No')
    exit()

for i in range(n):
    for x, y, z in dp[i]:
        if abs(xy[0] - x) + abs(xy[1] - y) > move[i]:
            continue
        if s[i]=='F':
                if z==0:
                    dp[i+1].add((x+1,y,z))
                elif z==1:
                    dp[i+1].add((x,y+1,z))
                elif z==2:
                    dp[i+1].add((x-1,y,z))
                else:
                    dp[i+1].add((x,y-1,z))
        else:
                if z==0:
                    dp[i+1].add((x,y,1))
                    dp[i+1].add((x,y,3))
                elif z==3:
                    dp[i+1].add((x,y,0))
                    dp[i+1].add((x,y,2))
                else:
                    dp[i+1].add((x,y,z-1))
                    dp[i+1].add((x,y,z+1))

for x,y,z in dp[n]:
    if xy == (x,y):
        print('Yes')
        exit()

print('No')

### FIXED CODE ###

s = input()
n = len(s)
xy = list(map(int, input().split()))

right = 0
updown = []
rightleft = []

direction = 0
for i in range(n):
    if s[i]=='F':
        if direction == 0:
            right+=1
        elif direction == 1:
            updown[-1]+=1
        else:
            rightleft[-1]+=1
    else:
        if direction == 0 or direction == 2:
            direction = 1
            updown.append(0)
        else:
            direction = 2
            rightleft.append(0)

updown = [x for x in updown if x!=0]
rightleft = [x for x in rightleft if x!=0]

# 最初はx方向にしか進めないので補正
xy[0]-=right

# updownでyに行けるか？rightleftでxに行けるかを考えれば良い
dpy = [set() for i in range(len(updown)+1)]
dpy[0].add(0)
for i in range(len(updown)):
    for y in dpy[i]:
        dpy[i+1].add(y+updown[i])
        dpy[i+1].add(y-updown[i])

dpx = [set() for i in range(len(rightleft)+1)]
dpx[0].add(0)
for i in range(len(rightleft)):
    for x in dpx[i]:
        dpx[i+1].add(x+rightleft[i])
        dpx[i+1].add(x-rightleft[i])

if xy[1] in dpy[-1] and xy[0] in dpx[-1]:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

from collections import deque
import copy
H,W = map(int,input().split())
grid = [[0]*W for _ in range(H)]
for i in range(H):
    grid[i] = list(input())
ans = 0
for sy in range(H):
    for sx in range(W):
        for gy in range(H):
            for gx in range(W):
                if sy == gy and sx == sy:
                    continue
                now_grid = copy.deepcopy(grid)
                time_grid = [[-1]*W for _ in range(H)]
                queue = deque()
                queue.append([sy,sx,0])
                now_grid[sy][sx] = '#'
                while queue:
                    y,x,t = queue.popleft()
                    for next_y, next_x in [[y+1, x],[y,x+1],[y-1,x],[y,x-1]]:
                        if 0<= next_y < H and 0 <= next_x < W and now_grid[next_y][next_x] != '#':
                            queue.append([next_y,next_x,t+1])
                            time_grid[next_y][next_x] = t+1
                            now_grid[next_y][next_x] = '#'
                ans = max(ans, time_grid[gy][gx])
print(ans)



### FIXED CODE ###

from collections import deque
import copy
H,W = map(int,input().split())
grid = [[0]*W for _ in range(H)]
for i in range(H):
    grid[i] = list(input())
ans = 0
for sy in range(H):
    for sx in range(W):
        if grid[sy][sx] == '#':
            continue
        now_grid = copy.deepcopy(grid)
        time_grid = [[-1]*W for _ in range(H)]
        queue = deque()
        queue.append([sy,sx,0])
        now_grid[sy][sx] = '#'
        while queue:
            y,x,t = queue.popleft()
            for next_y, next_x in [[y+1, x],[y,x+1],[y-1,x],[y,x-1]]:
                if 0<= next_y < H and 0 <= next_x < W and now_grid[next_y][next_x] != '#':
                    queue.append([next_y,next_x,t+1])
                    time_grid[next_y][next_x] = t+1
                    now_grid[next_y][next_x] = '#'
        Max= 0
        for i in range(H):
            for j in range(W):
                Max = max(Max,time_grid[i][j])
        ans = max(ans, Max)
print(ans)
### BUGGY CODE ###

from sys import stdin
import bisect

N = int(input())
L = list(map(int,stdin.readline().strip().split()))

L.sort()

ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if L[k] < (L[i]+L[j]):
                ans+=1

print(ans)    


### FIXED CODE ###

from sys import stdin
import bisect

N = int(input())
L = list(map(int,stdin.readline().strip().split()))

L.sort()

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

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

# ABC139
def main():
    N, *A = map(int, open(0).read().split())
    B = {}
    for i in range(N):
        x = i * (N - 1)
        B[i + 1] = A[x : x + N - 1][::-1]
    ans, flg, matched = 0, 0, set()
    while B:
        for i in range(1, N + 1):
            if i in B and i not in matched:
                x = B[i][-1]
                if x in B and x not in matched and B[x][-1] == i:
                    B[i].pop()
                    B[x].pop()
                    matched |= {i, x}
                    flg = 1
                    if B[i] == []:
                        del B[i]
                    if B[x] == []:
                        del B[x]
        if flg:
            ans += 1
            flg = 0
            matched = set()
        else:
            print(-1)
            return
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

# ABC139E - League
from collections import deque


def main():
    N, *A = map(int, open(0).read().split())
    B = {}
    for i in range(N):
        x = i * (N - 1)
        B[i + 1] = deque(A[x : x + N - 1])
    ans, cnt, matched = 0, 0, set()
    q = [i for i in range(1, N + 1)]
    while q:
        ans += 1
        next_q = []
        for i in q:
            if i in B and i not in matched:
                x = B[i][0]
                if x in B and x not in matched and B[x][0] == i:
                    B[i].popleft(), B[x].popleft()
                    matched |= {i, x}
                    cnt += 1
                    if not B[i]:
                        del B[i]
                    else:
                        next_q += [i]
                    if not B[x]:
                        del B[x]
                    else:
                        next_q += [x]
        q = next_q
        matched = set()
    flg = cnt == N * (N - 1) // 2
    print(ans if flg else -1)


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

import sys
from collections import deque
from copy import copy

N,K = list(map(int, input().split()))
V = deque(list(map(int, input().split())))

max_value = 0

def calc_max_value(V, k, l, r):
    store = []
    for i in range(l):
        if len(V)>0:
            store.append(V.popleft())
            continue
        else:
            break
    for i in range(r):
        if len(V)>0:
            store.append(V.pop())
            continue
        else:
            break
    store.sort()
    store = deque(store)
    max_value = sum(store)
    for i in range(k-l-r):
        if len(store)>0:
            e = store.popleft()
            if e < 0:
                max_value -= e
            else:
                break
        else:
            break
    return max_value

    
for k in range(K+1):
    for l in range(K+1):
        for r in range(K+1-l):
            max_value = max(max_value, calc_max_value(copy(V), k, l, r))

print(max_value)


### FIXED CODE ###

import sys
from collections import deque
from copy import copy

N,K = list(map(int, input().split()))
V = deque(list(map(int, input().split())))

max_value = 0

def calc_max_value(V, K, k, l, r):
    store = deque([])
    for i in range(l):
        if len(V)>0:
            store.append(V.popleft())
            continue
        else:
            break
    for i in range(r):
        if len(V)>0:
            store.append(V.pop())
            continue
        else:
            break
    store = deque(sorted(store))
    for i in range(K-l-r):
        if len(store)>0:
            e = store.popleft()
            if e < 0:
                continue
            else:
                store.appendleft(e)
                break
        else:
            break
    max_value = sum(store)
    return max_value

    
for k in range(min(K+1,N+1)):
    for l in range(k+1):
        for r in range(k+1-l):
            max_value = max(max_value, calc_max_value(copy(V), K, k, l, r))

print(max_value)
### BUGGY CODE ###

s = input()
n = int(input())

for i in range(n):
    t = input().split()
    if t[0] == '1':
        s = ''.join(list(reversed(s)))
    if t[0] == '2':
        if t[1] == '1':
            s = t[2] + s
        else:
            s = s + t[2]

print(s)

### FIXED CODE ###

s = input()
n = int(input())

t = ''
for i in range(n):
    q = input().split()
    if len(q) == 1:
        t, s = s, t
    elif len(q) == 3:
        if q[1] == '1':
            t += q[2]
        elif q[1] == '2':
            s += q[2]

t = t[::-1]
print(t + s)
### BUGGY CODE ###




import collections as cl
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
n = onem()

on = []
wh = [[-1 for j in range(n)] for i in range(n)]
de = cl.deque()
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
cl = [1 for i in range(n)]

while de:

    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = [1 for i in range(n)]

    elif len(on[kkk[0]]) != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        if len(on[kkk[1]]) != 0 and len(on[kkk[0]]) != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)


### FIXED CODE ###

import collections as cl
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
n = onem()

on = []
de = cl.deque()
ppp = [n-1 for i in range(n)]
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
ppppp = [1 for i in range(n)]
cl = ppppp[:]
while de:
    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = ppppp[:]

    elif ppp[kkk[0]] != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        ppp[kkk[0]] -= 1
        ppp[kkk[1]] -= 1
        if ppp[kkk[1]] != 0 != 0 and ppp[kkk[0]] != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)
### BUGGY CODE ###

S = input()
Q = int(input())
query = [list(input().split()) for _ in range(Q)]
forward = 1
for i in range(Q):
    if query[i][0] == '1':
        forward *= -1
    else:
        if query[i][1] == '1':
            if forward == 1:
                S = query[i][2] + S
            else:
                S = S + query[i][2] 
        else:
            if forward == 1:
                S = S + query[i][2] 
            else:
                S = query[i][2] + S

if forward == -1:
    ans = ''
    for i in range(len(S)):
        ans += S[-i-1]
else:
    ans = S
print(ans)


### FIXED CODE ###

S = input()
Q = int(input())
query = [list(input().split()) for _ in range(Q)]
forward = 1
f = ''
b = ''
for i in range(Q):
    if query[i][0] == '1':
        forward *= -1
    else:
        if query[i][1] == '1':
            if forward == 1:
                f += query[i][2]
            else:
                b += query[i][2] 
        else:
            if forward == 1:
                b += query[i][2] 
            else:
                f += query[i][2]
S = ''.join(list(reversed(f))) + S + b

if forward == -1:
    ans = ''.join(list(reversed(S)))
else:
    ans = S
print(ans)