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

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

mod = 0 #反転が何回目か（先頭がどっちか）,偶数回の時0，奇数回の時1

for _ in range(Q):
    Query = input()
    if Query[0] == "1":
        mod = (1 + mod) % 2
    else:
        if Query[2] == "1":
            if mod == 0:
                S = Query[4] + S
            else:
                S = S + Query[4]
        else:
            if mod == 0:
                S = S + Query[4]
            else:
                S = Query[4] + S
    #print("Qans",S)
if mod==0:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())
d = deque(S)
#print(d)

mod = 0 #反転が何回目か（先頭がどっちか）,偶数回の時0，奇数回の時1

for _ in range(Q):
    Query = input()
    if Query[0] == "1":
        mod = (1 + mod) % 2
    else:
        if Query[2] == "1":
            if mod == 0:
                d.appendleft(Query[4])
            else:
                d.append(Query[4])
        else:
            if mod == 0:
                d.append(Query[4])
            else:
                d.appendleft(Query[4])

S = ""
if mod==0:
    for _ in range(len(d)):
        S += d.popleft()
else:
    for _ in range(len(d)):
        S += d.pop()
print(S)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def sol():
    N,M = list(map(int,input().split()))
    A = list(map(int,input().split()))
    tmp = sorted([list(map(int,input().split())) for _ in range(M)],key = lambda x:-x[1])

    t = []
    for a,b in tmp:
        t= t + [b]*a
        
        if len(t) >=N:
            break

    A = A+ t
    A.sort(reverse = 1)
    print(sum(A[:N]))

if __name__ == '__main__':
    sol()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def sol():
    N,M = list(map(int,input().split()))
    A = list(map(int,input().split()))
    tmp = sorted([list(map(int,input().split())) for _ in range(M)],key = lambda x:-x[1])

    t = []
    for a,b in tmp:
        t+=[b]*a
        
        if len(t) >=N:
            break

    A += t
    A.sort(reverse = 1)
    print(sum(A[:N]))

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

N = int(input())
a = []

for i in range(N):
    A = int(input())
    if A in a:
        a.remove(A)

    else:
        a.append(A)
print(len(a))


### FIXED CODE ###

from collections import Counter
N = int(input())
a = []
count = 0

for i in range(N):
    A = int(input())
    a.append(A)

c = Counter(a)
for i in c:
    if c[i] % 2 == 1:
        count += 1

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

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

L1=[]
ans=[]

for i in range(N-2):
    for j in range(i+1,N-1):
        temp=S[i]+S[j]
        if temp in L1:
            continue
        else:
            L1.append(temp)
        for k in range(j+1,N):
            ans.append(temp+S[k])


print(len(set(ans)))

### FIXED CODE ###

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

L0=[]
L1=[]
ans=[]

for i in range(N-2):
    if S[i] in L0:
        continue
    else:
        L0.append(S[i])
    for j in range(i+1,N-1):
        temp=S[i]+S[j]
        if temp in L1:
            continue
        else:
            L1.append(temp)
        for k in range(j+1,N):
            ans.append(temp+S[k])


print(len(set(ans)))
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
#各bit 累積和テーブル作成
bit =[[0 for i in range(20)] for _ in range(N+1)]
for j in range(N):
    for i in range(20):
        bit[j+1][i] = (L[j] >> i) & 1
#accumulate
for j in range(1,len(L)):
    for i in range(20):
        bit[j+1][i] += bit[j][i]
#作成終了

#1がダブって立ってたらアウト
def check(start,x):
    #bit20桁チェック
    for i in range(20):
        if bit[x][i] - bit[start][i] >= 2:
            return False
    return True

#bisect( [x,y) 半開区間で探索)
def bisect(start,x,y):
    if y - x == 1: return x
    mid = (x + y) // 2
    if check(start,mid) == False:
        return bisect(start,x,mid)
    else:
        return bisect(start,mid,y)

cnt = 0
#今見てるとこが右からn番目でここより右にある物の中からいい感じ(check()の境界)のところを二分で探す
for n in range(N):
    #OKな個数を足し込む
    cnt += bisect(n, n, N+1) - n
print(cnt)



### FIXED CODE ###

N = int(input())
L = list(map(int,input().split()))
cand = []
bit =[[0 for i in range(20)] for _ in range(N)]
for j in range(len(L)):
    for i in range(20):
        bit[j][i] = (L[j] >> i) & 1
for j in range(1,len(L)):
    for i in range(20):
        bit[j][i] += bit[j-1][i]
bit = [[0 for i in range(20)]] + bit

#bisect( [x,y) )

def check(start,x):
    for i in range(20):
        if bit[x][i] - bit[start][i] >= 2:
            return False
    return True


def bisect(start,x,y):
    if y - x == 1: return x
    mid = (x + y) // 2
    if check(start,mid) == False:
        return bisect(start,x,mid)
    else:
        return bisect(start,mid,y)

cnt = 0
for n in range(N):
    cnt += bisect(n, n, N+1) - n
 #   print(bisect(n,n,N+1),n)
print(cnt)
### BUGGY CODE ###

import bisect
A, B, Q = map(int,input().split())

S = [-10**18] + sorted([int(input()) for _ in [0]*A]) + [10**18]
T = [-10**18] + sorted([int(input()) for _ in [0]*B]) + [10**18]





for _ in range(Q):
    x = int(input())
    ans = 10**18
    for i in range(2):
        if i == 0:
            a = S
            b = T
        elif i== 1:
            a = T
            b = S

        idx_x = bisect.bisect_left(a,x)
        for j in range(2):
            ax = a[idx_x-j]
            idx_a = bisect.bisect_left(b,ax)
            for k in range(2):
                bx = b[idx_a-k]
                ans = min(ans, abs(ax-x)+abs(bx-ax))
    print(ans)

### FIXED CODE ###

import bisect
import sys

A, B, Q = map(int,input().split())
s = [-(10**18)] + list(map(int, (sys.stdin.readline() for _ in [0]*A))) + [10**18]
t = [-(10**18)] + list(map(int, (sys.stdin.readline() for _ in [0]*B))) + [10**18]


def solve(s,t,x):
    ans = 10**18
    for i in range(2):
        a, b = (s, t) if i==0 else (t, s)
        posX1 = bisect.bisect_left(a,x)
        for j in range(2):
            ax = a[posX1 -j]
            posX2 = bisect.bisect_left(b,ax)
            for k in range(2):
                bx = b[posX2-k]
                ans = min(ans, abs(x-ax)+abs(bx-ax))
    return ans

for _ in range(Q):
    x = int(input())
    print(solve(s,t,x))
### BUGGY CODE ###

N = int(input())
S = [input() for i in range(N)]
S_set = sorted(list(set(S)))
L = len(S_set)

count = [0]*L
for i in range(L):
  count[i] = S.count(S_set[i])

#print(S_set)
M = max(count)
for i in range(L):
  if count[i] == M:
    print(S_set[i])

### FIXED CODE ###

from collections import Counter
N = int(input())
S = [input() for i in range(N)]

S_c = Counter(S)
max_count = max(S_c.values())

ans = []

for key, value in S_c.items():
  if value == max_count:
    ans.append(key)
    
ans.sort()

for i in range(len(ans)):
  print(ans[i])
### BUGGY CODE ###

I=lambda:list(map(int,input().split()))
n,W=I()
g=[0]+[I()for _ in range(n)]
dp=[[0]*-~W for _ in range(n+1)]
for i in range(1,n+1):
    t=g[i]
    for j in range(W+1):
        if j-t[0]>=0:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[0]]+t[1])
        else:
            dp[i][j]=dp[i-1][j]
print(max(dp[-1]))

### FIXED CODE ###

I=lambda:list(map(int,input().split()))
n,W=I()
g=[0]+[I()for _ in range(n)]
dp=[[0]*-~W for _ in range(n+1)]
for i in range(1,n+1):
    t=g[i]
    for j in range(W+1):
        if j-t[0]>=0:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[0]]+t[1])
        else:
            dp[i][j]=dp[i-1][j]
print(max(dp[-1]))
### BUGGY CODE ###



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

Rcnt = 0
Gcnt = 0

excep = 0

for i in range(len(S)):
    if S[i] == 'R':
        Rcnt += 1
    elif S[i] == 'G':
        Gcnt += 1
    for j in range(1, len(S)):
        if i+j+j < len(S) and S[i] != S[i+j]:
            if S[i] != S[i+j+j] and S[i+j] != S[i+j+j]:
                excep += 1
        elif i+j+j >= len(S):
            break

RGBcalc = Rcnt * Gcnt * (N - Rcnt - Gcnt)

print(RGBcalc - excep)

### FIXED CODE ###



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

Rcnt = 0
Gcnt = 0

excep = 0

for i in range(len(S)):
    if S[i] == 'R':
        Rcnt += 1
    elif S[i] == 'G':
        Gcnt += 1
    for j in range(1, len(S)):
        if i+j+j < len(S) and S[i] != S[i+j]:
            if S[i] != S[i+j+j] and S[i+j] != S[i+j+j]:
                excep += 1
        elif i+j+j >= len(S):
            break

print(Rcnt * Gcnt * (N - Rcnt - Gcnt) - excep)
### BUGGY CODE ###

#!/usr/bin/env python3
from functools import reduce
from operator import mul


def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


def stair(r):
    con = 0
    for i in range(r // 2 + 1):
        con += cmb(r - i, i)
    return con


n, m, *a = map(int, open(0).read().split())
if sum(a[i + 1] == a[i] + 1 for i in range(m - 1)) > 0:
    print(0)
    exit()

a.append(n + 1)
c = -1
ans = 1
for i in a:
    ans = ans * stair(i - c - 2) % (10**9 + 7)
    c = i
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(1000000)


memo = [0]*(10**5+1)
def count(n):
    if n < 2:
        return 1
    if memo[n] != 0:
        return memo[n]
    memo[n] = count(n-1) + count(n-2)
    return memo[n]


n, m, *a = map(int, open(0).read().split())
if sum(a[i + 1] == a[i] + 1 for i in range(m - 1)) > 0:
    print(0)
    exit()

a.append(n + 1)
c = -1
ans = 1
for i in a:
    ans = ans * count(i - c - 2) % (10**9 + 7)
    c = i
print(ans)
### BUGGY CODE ###

import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output
def chkprint(*args):
    names = {id(v):k for k,v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

# Binary converter
def to_bin(x):
    return bin(x)[2:]

# --------------------------------------------

dp = None

def main():
    S = input()
    K = int(input())

    A = []
    for i in range(len(S)):
        for j in range(i+1, len(S)+1):
            A.append(S[i:j])

    print(sorted(list(set(A)))[K-1])

main()


### FIXED CODE ###

import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output
def chkprint(*args):
    names = {id(v):k for k,v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

# Binary converter
def to_bin(x):
    return bin(x)[2:]

# --------------------------------------------

dp = None

def main():
    S = input()
    K = int(input())

    A = []
    for i in range(len(S)):
        for j in range(i+1, min(i+6, len(S)+1)):
            A.append(S[i:j])

    print(sorted(list(set(A)))[K-1])

main()
### BUGGY CODE ###

import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
from fractions import gcd
from copy import deepcopy
import math
import queue
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main(): #startline-------------------------------------------
    k = int(input())
    ans = 0
    for i in range(1,k+1):
        for j in range(i,k+1):
            for l in range(j,k+1):
                plist = list(set((i,j,l)))
                if len(plist) == 1:
                    ans += plist[0]
                elif len(plist) == 2:
                    ans += gcd(plist[0],plist[1])*3
                else:
                    ans += gcd(gcd(plist[0],plist[1]),plist[2])*6
    print(ans)
if __name__ == "__main__":
    main() #endline===============================================

### FIXED CODE ###

from math import gcd
def main(): #startline-------------------------------------------
    k = int(input())
    ans = 0
    for i in range(1,k+1):
        for j in range(1,k+1):
            for l in range(1,k+1):
                ans += gcd(gcd(i,j),l)

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

N = range(1, int(input()) + 1)
prod = 1
for i in N:
    prod *= i
print(prod % (10**9 + 7))


### FIXED CODE ###

num = 1
for i in range(1, int(input()) + 1):
  num = (num * i) % (10**9 + 7)
print(num)
### BUGGY CODE ###

n=int(input())
s=[input() for i in range(n)]
s.sort()
cnt=1
ans=0
pri=[]
for i in range(n-1):
    if s[i]==s[i+1]:
        cnt+=1
    else:
        ans=max(cnt,ans)
        cnt=1
ans=max(cnt,ans)
for i in range(n):
    if ans==s.count(s[i]):
        pri.append(s[i])
t=set(pri)
p=list(t)
p.sort()
for i in range(len(p)):
    print(p[i])

### FIXED CODE ###

n=int(input())
s=[input() for i in range(n)]
s.sort()
cnt=1
ans=0
pri=[]
for i in range(n-1):
    if s[i]==s[i+1]:
        cnt+=1
    else:
        ans=max(cnt,ans)
        cnt=1
ans=max(cnt,ans)
cnt=1
for i in range(n-1):
    if s[i]==s[i+1]:
        cnt+=1
    else:
        if cnt==ans:
            pri.append(s[i])
            cnt=1
        else:
            cnt=1
if cnt==ans:
    pri.append(s[-1])
for i in range(len(pri)):
    print(pri[i])
### BUGGY CODE ###

k,s = map(int,input().split())
a = 0
for x in range(k+1):
  for y in range(x,k+1):
    for z in range(y,k+1):
      if x+y+z == s:
        if x != y and y != z and z != x:
          a += 6
        elif (x == y and y != z) or (x == z and z != y) or (z == y and y!= x):
          a += 3
        else:
          a += 1
        
print(a)

### FIXED CODE ###

k,s = map(int,input().split())
a = 0
for x in range(k+1):
  for y in range(k+1):
      if s-(x+y) <= k and s-(x+y) >= 0:
        a += 1
        
print(a)
### BUGGY CODE ###

# -*- coding:utf-8 -*-
import sys
l = [int(i) for i in sys.stdin]
used = []
add = used.append
now = 1
count = 0
while True:
  if now == 2:
    break
  if now in used:
    print(-1)
    exit()
  add(now)
  now = l[now]
  count += 1
print(count)

### FIXED CODE ###

# -*- coding:utf-8 -*-
import sys
button = [int(i) for i in sys.stdin]
now = 1
count = 0
for i in range(button[0]):
  if now == 2:
    print(count)
    exit()
  now = button[now]
  count += 1
print(-1)
### BUGGY CODE ###

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7

dp = [0] * (1 << n)
dp[0] = 1

for bit in range((1 << n) - 1):
    i = bin(bit).count('1')
    for j in range(n):
        newbit = bit | (1 << j)
        if (a[i][j] == 1) and (bit != newbit):
            dp[newbit] += dp[bit]
            dp[newbit] %= mod
print(dp[-1])


### FIXED CODE ###

mod = 10**9+7
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
dp = [0]*(1 << n)
dp[0] = 1
for i in range(1, 1 << n):
    k = bin(i).count("1")
    for j in range(n):
        if i >> j & 1 and a[k-1][j]:
            dp[i] += dp[i ^ (1 << j)]
    dp[i] %= mod
print(dp[(1 << n)-1])
### BUGGY CODE ###

from collections import defaultdict

M = 998244353
B = 10**18 % M

def mex(s):
  for i in range(max(s)+2):
    if i not in s:
      return i

def calc_grandy(e):
  g = {}
  rev_g = defaultdict(set)
  rev_g[0] = set(range(1, N+1))
  for i in sorted(e.keys(), reverse=True):
    m = mex({g.get(j,0) for j in e[i]})
    if m:
      g[i] = m
      rev_g[m].add(i)
      rev_g[0].remove(i)
  return defaultdict(int, ((k,sum(map(lambda x:pow(B, x, M), v))%M) for k, v in rev_g.items()))

def get_edge():
  M = int(input())
  e = defaultdict(set)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].add(b)
  return e

def solve(N, edge):
  grandy = list(map(calc_grandy, edge))
  ret = 0
  for gx, x in grandy[0].items():
    for gy, y in grandy[1].items():
      gz = gx^gy
      z = grandy[2][gz]
      ret = (ret + x*y*z)%M
  return ret

N = int(input())
edge = [get_edge() for i in range(3)]

print(solve(N, edge))

### FIXED CODE ###

from collections import defaultdict

M = 998244353
B = 10**18 % M

def mex(s):
  for i in range(max(s)+2):
    if i not in s:
      return i

def ext_euc(a, b):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, b
  while z1 != 1:
    d, m = divmod(z2,z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1, y1

def inv_mod(a, b, m):
  x, y = ext_euc(a, m)
  return (x * b % m)

def calc_grundy(e):
  g = {}
  sum_g = defaultdict(int)
  sum_g[0] = inv_mod(B-1, pow(B, N+1, M)-B, M)
  for i in sorted(e.keys(), reverse=True):
    m = mex({g.get(j,0) for j in e[i]})
    if m:
      g[i] = m
      x = pow(B, i, M)
      sum_g[m] += x
      sum_g[0] -= x
  return sum_g

def get_edge():
  M = int(input())
  e = defaultdict(set)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].add(b)
  return e

def solve(N, edge):
  sum_g = list(map(calc_grundy, edge))
  ret = 0
  for gx, x in sum_g[0].items():
    for gy, y in sum_g[1].items():
      gz = gx^gy
      z = sum_g[2][gz]
      ret = (ret + x*y*z)%M
  return ret

N = int(input())
edge = [get_edge() for i in range(3)]

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

def main():
    n=int(input())
    nn=2*n
    s=[input() for _ in [0]*n]
    #s=[i+i[:-1] for i in s]+[i+i[:-1] for i in s][:-1]
    ans=[[0]*n for _ in [0]*n]
    for i in range(1,nn-1):
        m=min(i+1,n)
        for j in range(nn-2):
            for k in range(1,min(m,nn-1-j)):
                ii=i-k
                if s[i%n][j%n]!=s[ii%n][(j+k)%n]:
                    l=min(n-k+1,ii,j)
                    width=l-max(-1,ii-n,j-n)
                    if width<1:
                        continue
                    ans[ii-l][j-l]=max(ans[ii-l][j-l],width)
    for i in range(1,n):
        for j in range(1,n):
            ans[i][j]=max(ans[i][j],ans[i-1][j-1]-1)
    print(sum([sum([i==0 for i in a]) for a in ans]))
main()

### FIXED CODE ###

def main():
    n=int(input())
    nn=2*n-1
    s=[input() for _ in [0]*n]
    s=[i+i[:-1] for i in s]+[i+i[:-1] for i in s][:-1]
    ans=[[0]*n for _ in [0]*n]
    for i in range(1,nn):
        m=min(i+1,n)
        for j in range(nn-1):
            for k in range(max(i-j-n,0)+1,min(m,nn-j,i-j+n)):
                ii=i-k
                if s[i][j]!=s[ii][j+k]:
                    l=min(n-k+1,ii,j)
                    width=l-max(-1,ii-n,j-n)
                    ans[ii-l][j-l]=max(ans[ii-l][j-l],width)
    for i in range(1,n):
        for j in range(1,n):
            ans[i][j]=max(ans[i][j],ans[i-1][j-1]-1)
    print(sum([sum([i==0 for i in a]) for a in ans]))
main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

N, Q = map(int, input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

# 木構造をリストで表現する
G = [[] for _ in range(N+1)]

for a, b in AB:
    G[a].append(b)
    G[b].append(a)

# 各操作で与えられる値を、各頂点ごとに集計しておく
P = [0] * (N+1)
for p, x in PX:
    P[p] += x


def dfs(v, parent, point):
    # 現在いる頂点vの親までの値をpointとする
    P[v] += point
    for next_v in G[v]:
        if next_v == parent:
            continue
        dfs(next_v, v, P[v])


dfs(1, 0, 0)

res = ' '.join(map(str, P[1:]))
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

 
N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
 
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
 
value = [0] * (N+1)
for p,x in PX:
    value[p] += x
 
def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])
 
dfs(1,0,0)
 
answer = ' '.join(map(str,value[1:]))
print(answer)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(500*500) # default 1000



def dfs(v,p=-1): # vertices & parent idx
    lst=to[v] # children list
    for child in lst:
        if child==p:
            continue
        ans[child]+=ans[v]
        # print('vertices=',v)
        # print('child=',child)
        # print('parent=',p)
        dfs(child,v)
        
N, Q = map(int, input().strip().split())

to=[[] for j in range(N)] # N points
ans=[0]*N # N points

for i in range(N-1):
    a,b=map(int, input().strip().split())
    a-=1
    b-=1
    to[a].append(b)
    to[b].append(a)

for i in range(Q):
    p,x=map(int, input().strip().split())
    p-=1
    ans[p]+=x

dfs(0)
for i in range(N):
    print(ans[i],end=' ')

### FIXED CODE ###

N, Q = map(int, input().strip().split())

# visited = [False for _ in range(N)]
# def dfs(v): # vertices & parent idx
#     visited[v]=True
#     for child in to[v]:
#         if visited[child]==True:
#             continue
#         ans[child]+=ans[v]
#         dfs(child)
# def dfs(v,p=-1): # vertices & parent idx
#     for child in to[v]:
#         if child==p:
#             continue
#         ans[child]+=ans[v]
#         dfs(child,v)

to=[[] for j in range(N)] # N points
ans=[0]*N # N points

for i in range(N-1):
    a,b=map(int, input().strip().split())
    a-=1
    b-=1
    to[a].append(b)
    to[b].append(a)

for i in range(Q):
    p,x=map(int, input().strip().split())
    p-=1
    ans[p]+=x

# dfs(0)
stack=[0]
visited=[False]*N
while stack:
    v=stack.pop()
    visited[v]=True
    for child in to[v]:
        if visited[child] ==False:
            # visited[v]=True
            ans[child]+=ans[v]
            stack.append(child)
for i in range(N):
    print(ans[i],end=' ')
# print(ans)
### BUGGY CODE ###

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

cnt=0

for i in range(q):
  x=input()
  if x=='1':
    cnt+=1
    
  elif x[0]=='2':
    if (x[2]=='1' and cnt%2==0) or (x[2]=='2' and cnt%2==1):
      s.insert(0,x[4])
      
    else:
      s+=x[4]
      
if cnt%2==1:
  s.reverse()
  

print(''.join(s))
    

### FIXED CODE ###

from collections import deque


Q=deque(list(input()))

q=int(input())

cnt=0

for i in range(q):
  x=input()
  if x[0]=='1':
    cnt+=1
    cnt%=2
    
  elif x[0]=='2':
    if x[2]=='1':
        if cnt%2==0:
            Q.appendleft(x[4])
        else:
            Q.append(x[4])

    else:
        if cnt%2==0:
            Q.append(x[4])
        else:
            Q.appendleft(x[4])
      
if cnt%2==1:
  Q.reverse()


print(''.join(Q))