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

N, Q = map(int, input().split())
G = [[] for _ in range(N)]
memo = [[i] for i in range(N)]
flg = [False]*N
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)

ans = [0]*N
add = [0]*N

for i in range(Q):
    p, x = map(int, input().split())
    if not flg[p-1]:
        flg[p-1] = True
        ans[p-1] += x
        queue = [p-1]
        while queue:
            par = queue.pop(0)
            if G[par]:
                for i in G[par]:
                    ans[i] += x
                    queue.append(i)
                    memo[p-1].append(i)
    else:
        add[p-1] += x

ct = 0
for i in flg:
    if i:
        for j in memo[ct]:
            ans[j] += add[ct]
    ct += 1

print(*ans)

### FIXED CODE ###

N, Q = map(int, input().split())
G = [[] for _ in range(N)]
ans = [0]*N

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

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

judge = [False]*N
judge[0] = True
queue = [0]
while queue:
    a = queue.pop()
    for i in G[a]:
        if not judge[i]:
            judge[i] = True
            ans[i] += ans[a]
            if G[i]:
                queue.append(i)

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

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

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

for i in range(M):
    max_ind = A.index(max(A))
    A[max_ind] = A[max_ind] // 2

print(sum(A))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)

for _ in range(m):
    tmp_min = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-tmp_min//2))

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

from itertools import accumulate
from operator import mul
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N, K = map(int, input().split())
    A = tuple(map(int, input().split()))

    point = list(accumulate(A[:K], mul))
    for i in range(K, N):
        point.append(point[-1] * A[i] // A[i - K])
    for i in range(K, N):
        if point[i - 1] < point[i]:
            print("Yes")
        else:
            print("No")


main()


### FIXED CODE ###

from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N, K = map(int, input().split())
    A = tuple(map(int, input().split()))

    for i in range(K, N):
        if A[i - K] < A[i]:
            print("Yes")
        else:
            print("No")


main()
### BUGGY CODE ###

n=int(input())
table=[[0]*n for i in range(60)]
for i,v  in enumerate(map(int,input().split())):
    for j in range(60):
        table[j][n-1-i]=v%2
        v//=2
        if v==0:break
#print(*table,sep='\n')
ans=0
mod1,mod2=10**9+7,998244353
mod=mod1
a=1
for t in table:
    o,z=0,0
    
    for v in t:
        if v:
            o+=1
            ans=(ans+z*a)%mod
        else:
            z+=1
            ans=(ans+o*a)%mod

    a=a*2%mod
print(ans)

### FIXED CODE ###

n=int(input())
l=[int(c) for c in input().split()]
ans=0
mod=10**9+7
for i in range(60):
  s=sum(a>>i&1 for a in l)
  ans+=s*(n-s)<<i%mod
  ans%=mod
print(ans)
### BUGGY CODE ###

import os

def main():
        num = int(input())
        dict_list = [] 
        for i in range(num):
                strings = input()
                dict_list.append(strings)

        dict_lists = set(dict_list)

        max_num = 0
        result = []
        for i in dict_lists:
                count = dict_list.count(i)
                if max_num <= count:
                        if max_num == count:
                                result.append(i)
                        else:
                                max_num = count
                                result = []
                                result.append(i) 
        
        result.sort()
        for i in result:
                print(i)

if __name__ == "__main__":
        main()



### FIXED CODE ###

import os

def main():
        num = int(input())
        dict_list = {}
        for i in range(num):
                strings = input()
                if strings in dict_list.keys():
                        dict_list[strings] += 1
                else:
                        dict_list[strings] = 1 

        max_num = max(dict_list.values())
        result = []
        
        for k,v in dict_list.items():
                if v == max_num:
                        result.append(k)
        result.sort()
        for i in result:
                print(i)

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

N = int(input())
A = sorted(list(map(int, input().split())))
if N == 2:
    print(max(A))
    exit()
result = []
num = 0
for a in A[1:]:
    if a % A[0] != 0:
        num += 1
        if num == 2:
            break
else:
    result.append(A[0])
for n in range(A[0], 0, -1):
    if A[0] % n != 0:
        continue
    num = 0
    for a in A[1:]:
        if a % n != 0:
            num += 1
            if num == 2:
                break
    else:
        result.append(n)
num = 0
for a in A[0:1] + A[2:]:
    if a % A[1] != 0:
        num += 1
        if num == 2:
            break
else:
    result.append(A[1])
for n in range(A[1], 0, -1):
    if A[1] % n != 0:
        continue
    num = 0
    for a in A[0:1] + A[2:]:
        if a % n != 0:
            num += 1
            if num == 2:
                break
    else:
        result.append(n)
print(max(result))


### FIXED CODE ###

import math
N = int(input())
A = sorted(list(map(int, input().split())))
if N == 2:
    print(max(A))
    exit()
result = []
num = 0
for a in A[1:]:
    if a % A[0] != 0:
        num += 1
        if num == 2:
            break
else:
    result.append(A[0])
for n in range(2, int(math.sqrt(A[0])) + 1):
    if A[0] % n != 0:
        continue
    num = 0
    x = A[0] // n
    for a in A[1:]:
        if a % x != 0:
            num += 1
            if num == 2:
                break
    else:
        result.append(x)
    num = 0
    for a in A[1:]:
        if a % n != 0:
            num += 1
            if num == 2:
                break
    else:
        result.append(n)
num = 0
B = A[0:1] + A[2:]
for a in B:
    if a % A[1] != 0:
        num += 1
        if num == 2:
            break
else:
    result.append(A[1])
for n in range(2, int(math.sqrt(A[1])) + 1):
    if A[1] % n != 0:
        continue
    num = 0
    x = A[1] // n
    for a in B:
        if a % x != 0:
            num += 1
            if num == 2:
                break
    else:
        result.append(x)
    num = 0
    for a in B:
        if a % n != 0:
            num += 1
            if num == 2:
                break
    else:
        result.append(n)
if len(result) != 0:
    print(max(result))
else:
    print(1)
### BUGGY CODE ###

import sys

n=int(input())
l=set(map(str,sys.stdin))
alp=[chr(_) for _ in range(97,97+26)]
res=[]
ans=0

for j in l:
    ll=list(j)
    tmp=[0]*26
    for k in ll:
        m=0
        for x in alp:
            if k==x:
                tmp[m]+=1
            m+=1
    aa="".join(map(str,tmp))
    tmp2=0
    for z in res:
        if aa==z:
            tmp2+=1
    ans+=tmp2
    res.append(aa)

print(int(ans))

### FIXED CODE ###

import sys

n=int(input())
l=["".join(sorted(sys.stdin.readline().strip())) for i in range(n)]


res={}
ans=0
 
for j in range(n):
    ll=list(l[j])
    ll.sort()
    aa="".join(ll)
    if aa in res:
        ans+=res[aa]
        res[aa]+=1
    else:
        res[aa]=1

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

import sys
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def main():
    N, K = readnums()
    x = list(readnums())
    ans = 0
    for i in range(K, N + 1):
        l = x[i - K:i]
        if all([m > 0 for m in l]):
            val = abs(max(l))
        elif all([m < 0 for m in l]):
            val = abs(min(l))
        else:
            val = abs(min(l)) + abs(max(l))
            val += min(abs(min(l)), abs(max(l)))
        if not ans:
            ans = val
        else:
            ans = min(ans, val)

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def main():
    N, K = readnums()
    x = list(readnums())
    ans = 0
    for i in range(K - 1, N):
        ls = i - K + 1
        le = i
        if x[ls] > 0:
            val = abs(x[le])
        elif x[le] < 0:
            val = abs(x[ls])
        else:
            val = abs(x[ls]) + abs(x[le])
            val += min(abs(x[ls]), abs(x[le]))
        if not ans:
            ans = val
        else:
            ans = min(ans, val)

    print(ans)


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

N, M = map(int, input().split())
PY = []
array = [[] for _ in range(N)]

for _ in range(M):
    P, Y = map(int, input().split())
    PY.append([P, Y])
    array[P-1].append(Y)

for p, y in PY:
    print('%06d%06d' % (p, sorted(array[p-1]).index(y)+1))


### FIXED CODE ###

import bisect

N, M = map(int, input().split())
PY = []
array = [[] for _ in range(N)]

for _ in range(M):
    P, Y = map(int, input().split())
    PY.append([P, Y])
    array[P-1].append(Y)
    
for i in range(N):
    array[i].sort()

for p, y in PY:
    n = bisect.bisect_left(array[p-1], y) + 1
    print('%06d%06d' % (p, n))
### BUGGY CODE ###

from collections import Counter

from operator import mul
from functools import reduce

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


N = int(input())
matched = [False] * N
s = [None] * N
for i in range(N):
    s[i] = input()



ans = 0
i = 0
j = 1
cnt = 0
while i < N:
    cnt = 0

    if matched[i] == True:
        if i >= N-1:
            break
        
        i += 1
        j = i+1
        continue

    si = Counter(s[i])
    while j <= N-1:

        if matched[j] == True:
            j += 1

            continue


        sj = Counter(s[j])
        if si == sj:
            matched[i] = True
            matched[j] = True
            cnt += 1
        j += 1
    
    if cnt != 0:
        ans += cmb(cnt+1,2)

    if i == N-2:
        break

    i += 1
    j = i+1
    
print(ans)



### FIXED CODE ###

from collections import Counter

from operator import mul
from functools import reduce

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


N = int(input())
matched = [False] * N
s = [None] * N
for i in range(N):
    moji = list(input())
    moji.sort()
    tmp = "".join(moji)
    s[i]= tmp

s.sort()
#print(s)
ans = 0
i = 0
j = 1
while i < N-1:
    cnt = 0
    #print("ss",i,j)
    if j == N:
        break
    while j <= N-1:
        #print("aa",i,j)
        if s[i] == s[j]:
            cnt += 1
            j += 1
            continue
        else:

            i = j
            j = i+1
            break
    if cnt >= 1:
        ans += cmb(cnt+1,2)
    

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

# BFS queue
import queue
import copy

import time
sss = time.time()
H, W = map(int,input().split())
b = [list(input()) for _ in range(H)]
dist = [[10**9 for _ in range(W)] for _ in range(H)]
start = (-1,-1)
qq = queue.Queue()
# start把握
for i in range(H):
    for j in range(W):
        if b[i][j] == '.':
            qq.put((i,j))
far = 0
move = [(-1,0), (0,-1), (1,0), (0,1)]
def BFS(start, bb):
    dist = [[10**9 for _ in range(W)] for _ in range(H)]
    far = 0
    q = queue.Queue()
    q.put(start)
    dist[start[0]][start[1]] = 0
    # BFS
    while 1:
        now = q.get()
        x = now[0]
        y = now[1]
        bb[x][y] == '#'
        for elem in move:
            dx = elem[0]
            dy = elem[1]
            if x+dx>=0 and x+dx<= H-1 and y+dy>=0 and y+dy<=W-1 and abs(dx-dy)==1:
                if bb[x+dx][y+dy] != '#':
                    if dist[x+dx][y+dy] > dist[x][y]:
                        dist[x+dx][y+dy] = dist[x][y] + 1
                        if dist[x+dx][y+dy] > far:
                            far = dist[x+dx][y+dy]
                        q.put((x+dx,y+dy))
        if q.empty():
            break
    return far
res = 0
while 1:
    ttt = time.time()
    if ttt-sss >= 1.8:
        break
    now = qq.get()
    res = max([res, BFS(now, copy.deepcopy(b))])
    if qq.empty():
        break
print(res)


### FIXED CODE ###

# BFS queue
import queue
import copy

import time
sss = time.time()
H, W = map(int,input().split())
b = [list(input()) for _ in range(H)]
dist = [[10**9 for _ in range(W)] for _ in range(H)]
start = (-1,-1)
qq = queue.Queue()
l = 0
# start把握
for i in range(H):
    for j in range(W):
        if b[i][j] == '.':
            qq.put((i,j))
            l += 1
if l >= H*W-(H-2):
    print(H+W-2)
    exit()
far = 0
move = [(-1,0), (0,-1), (1,0), (0,1)]
def BFS(start, bb):
    dist = [[10**9 for _ in range(W)] for _ in range(H)]
    far = 0
    q = queue.Queue()
    q.put(start)
    dist[start[0]][start[1]] = 0
    # BFS
    while 1:
        now = q.get()
        x = now[0]
        y = now[1]
        bb[x][y] == '#'
        for elem in move:
            dx = elem[0]
            dy = elem[1]
            if x+dx>=0 and x+dx<= H-1 and y+dy>=0 and y+dy<=W-1 and abs(dx-dy)==1:
                if bb[x+dx][y+dy] != '#':
                    if dist[x+dx][y+dy] > dist[x][y]:
                        dist[x+dx][y+dy] = dist[x][y] + 1
                        if dist[x+dx][y+dy] > far:
                            far = dist[x+dx][y+dy]
                        q.put((x+dx,y+dy))
        if q.empty():
            break
    return far
res = 0
while 1:
    ttt = time.time()
    if ttt-sss >= 1:
        break
    now = qq.get()
    res = max([res, BFS(now, copy.deepcopy(b))])
    if qq.empty():
        break
print(res)
### BUGGY CODE ###

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

py=[]
#初期値が0の辞書
from collections import defaultdict
p2year = defaultdict(lambda: []) 

for _ in range(m):
    p,y=map(int,input().split())
    py.append((p,y))
    p2year[p].append(y)


for item in p2year.keys():
    p2year[item].sort()

for item in py:
    pp=item[0]
    yy=item[1]
    result=str(pp).zfill(6)+str((p2year[pp].index(yy)+1)).zfill(6)
    print(result)



### FIXED CODE ###

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

py=[]
#初期値が0の辞書

p2year = [[] for _ in range(n+1)]

for _ in range(m):
    p,y=map(int,input().split())
    py.append((p,y))
    p2year[p].append(y)

#初期値が0の辞書
from collections import defaultdict
py2index = defaultdict(lambda: 0) 

for item in range(n+1):
    p2year[item].sort()
    for index,temp in enumerate(p2year[item]):
        py2index[(item,temp)]=index+1

for item in py:
    pp=item[0]
    yy=item[1]
    result=str(pp).zfill(6)+str((py2index[(pp,yy)])).zfill(6)
    print(result)
### BUGGY CODE ###

N,Q = map(int,input().split())
if N == 1:
    for i in range(Q):
        print(min(map(int,input().split())))
    exit()

for i in range(Q):
    a,b = map(int,input().split())
    while a != b:
        if a < b: a,b = b,a
        a = (a+N-2) // N
    print(a)


### FIXED CODE ###

N,Q = map(int,input().split())
if N == 1:
    for i in range(Q):
        print(min(map(int,input().split())))
    exit()

def solve(s):
    a,b = map(int,s.split())
    while a != b:
        if a < b: a,b = b,a
        a = (a+N-2) // N
    return str(a)

print('\n'.join(map(solve, [input() for i in range(Q)])))
### BUGGY CODE ###

a=int(input())
ans=0
s = 1
while True:
    ans+=s
    a//=2
    s*=2
    if a==1:
        break
ans+=s    
print(ans)

### FIXED CODE ###

a=int(input())
ans=0
s = 1
while True:
    if a==1:
        break
    ans+=s
    a//=2
    s*=2
ans+=s    
print(ans)
### BUGGY CODE ###

n=int(input())
s=input().rstrip()
count=0

for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if (j-i)!=(k-j):
                if s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
                    count+=1
print(count)

### FIXED CODE ###

n=int(input())
s=input().rstrip()
r=s.count("R")
g=s.count("G")
b=s.count("B")
count=0
for i in range(n-2):
    for j in range(i+1,n-1):
        if j+j-i<n:
            if s[i]!=s[j] and s[i]!=s[j+j-i] and s[j]!=s[j+j-i]:
                count+=1
print(r*g*b-count)
### BUGGY CODE ###

n, m = input().split()
N = int(n)
M = int(m)

A = list(map(int, input().split()))
A.sort(reverse=True)

for _ in range(M):
    A[0] = A[0] // 2
    A.sort(reverse=True)
print(sum(A))


### FIXED CODE ###

N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
it = 0
for i in range(M):
    A[it]=A[it]//2
    if it<N-1:
        if A[it]<A[it+1] and A[0]<A[it+1]:
            it+=1
        else:
            A.sort(reverse = True)
            it = 0
    if it == N-1:
        A.sort(reverse = True)
        it = 0
print(sum(A))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
for i in range(Q):
  l, r = map(int, input().split())
  # print(S[l - 1: r].count('AC'))
  T = S[l - 1: r]
  R = T.replace('AC', '')
  print((len(T) - len(R)) // 2)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
LR = [list(map(int,input().split())) for _ in range(Q)]
#print(LR)

C = [0 for _ in range(N+1)]
for i in range(1,N):
  if S[i-1] == 'A' and S[i] == 'C':
    C[i+1] = C[i] + 1
  else:
    C[i+1] = C[i]
#print(C)
for l,r in LR:
  print(C[r]-C[l])
### BUGGY CODE ###

s = input()
K = int(input())

ans = set()
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        ans.add(s[i:j])
ans = sorted(ans)
print(ans[K-1])

### FIXED CODE ###

s = input()
K = int(input())

ans = set()
for i in range(len(s)):
    for j in range(K):
        ans.add(s[i:i+1+j])
ans = sorted(ans)
print(ans[K-1])
### BUGGY CODE ###

n = int(input())

ai = list(map(int, input().split()))

n = 1
for i in ai :
    print(ai.count(n))
    n += 1
print(0)


### FIXED CODE ###

n = int(input())
ai = list(map(int, input().split()))
b = [0]*n
for i in range(n-1) :
    b[ai[i]-1] += 1
for m in range(n):
    print(b[m])
### BUGGY CODE ###

mod = 10**9+7
import sys
sys.setrecursionlimit(1000000)

N,M = [int(x) for x in input().split()]
a = [int(input()) for _ in range(M)]
dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(N+1):
    if(i in a):
        continue
    if(i<N-1):
        if(i+2 not in a):
            dp[i+2]+=dp[i]
            dp[i+2]%=mod
    if(i<N):
        if(i+1 not in a):
            dp[i+1]+=dp[i]
            dp[i+1]%=mod
print(dp[N])


### FIXED CODE ###

mod = 10**9+7
import sys
sys.setrecursionlimit(10000000)

N,M = [int(x) for x in input().split()]
a = [int(input()) for _ in range(M)]
di = {}
for i in a:
    di[i]=1
dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(N+1):
    if(i in di):
        continue
    if(i<N-1):
        if(i+2 not in di):
            dp[i+2]+=dp[i]
            dp[i+2]%=mod
    if(i<N):
        if(i+1 not in di):
            dp[i+1]+=dp[i]
            dp[i+1]%=mod
print(dp[N])
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]

from scipy.sparse.csgraph import floyd_warshall
wf=floyd_warshall(a)
if not (a==wf).all() :
    print(-1)
    exit()

ans=0
for i in range(n):
    for j in range(n):
        use=True
        for h in range(n):
            if h!=i and h!=j and wf[i][j] == wf[i][h]+wf[h][j]:
                use=False
        if use:
            ans+=wf[i][j]
print(int(ans//2))

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
wf=[list(map(int,input().split())) for i in range(n)]

ans=0
for i in range(n):
    for j in range(i+1,n):
        use=True
        for h in range(n):
            if h!=i and h!=j and wf[i][j] > wf[i][h]+wf[h][j]:
                print(-1)
                exit()
            if h!=i and h!=j and wf[i][j] == wf[i][h]+wf[h][j]:
                use=False
        if use:
            ans+=wf[i][j]
print(int(ans))
### BUGGY CODE ###

import collections

h,w,m = map(int,input().split())

gyou = collections.defaultdict(int)
retu = collections.defaultdict(int)
q = collections.deque()

for i in range(m):
    y,x = map(int,input().split())
    gyou[y-1] += 1
    retu[x-1] += 1
    q.append((y-1,x-1))

ymax = max(gyou.values())
xmax = max(retu.values())
ans =  ymax + xmax 

for xk,xv in retu.items():
    if xv != xmax:
        continue
    for yk, yv in gyou.items():
        if yv != ymax:
            continue
        if (yk,xk) not in q:
            print(ans)
            exit()

print(ans-1)

### FIXED CODE ###

import collections

h,w,m = map(int,input().split())

gyou = [0 for i in range(h)]
retu = [0 for i in range(w)]
l = []

for i in range(m):
    y,x = map(int,input().split())
    gyou[y-1] += 1
    retu[x-1] += 1
    l.append((y-1,x-1))

ymax = max(gyou)
xmax = max(retu)
c_ymax = gyou.count(ymax)
c_xmax = retu.count(xmax)
ans = ymax + xmax

c = 0
for y,x in l:
    if gyou[y] == ymax and retu[x] == xmax:
        c += 1

if c == c_ymax*c_xmax:
    print(ans-1)
else:
    print(ans)
### BUGGY CODE ###

K, S = map(int,input().split())

count = 0
for i in range(0,K+1):
    if i > S:
        continue
    for j in  range(0,K+1):
        if i + j > S:
            continue
        for k in  range(0,K+1):
            if i + j + k > S:
                continue
            if i + j + k == S:
                count += 1
print(count)

### FIXED CODE ###

K, S = map(int,input().split())

count = 0
for i in range(0,K+1):
    if i > S:
        continue
    for j in  range(0,K+1):
        if 0 <= (S - i - j) <= K:
            count += 1

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

n,k = map(int,input().split())
p = [int(i) for i in input().split()]
ans = []
maxv = max(p)
dp = [i+1 for i in range(maxv+1)]
for i in range(1,maxv+1):
    dp[i] = dp[i-1]+dp[i]
dp = [j/(i+1) for i,j in enumerate(dp)]

def func(n,dp):
    ans = 0
    for i in n:
        ans += dp[i-1]
    return ans

maxv = 0
for i in range(n-k+1):
    ans.append(func(p[i:(i+k)],dp))
    
print(max(ans))

### FIXED CODE ###

n,k = map(int,input().split())
p = [(int(i)+1)/2 for i in input().split()] #期待値にして格納

#累積和を求める
for i in range(1,n):
    p[i]=p[i-1]+p[i]
mx = p[k-1]
for i in range(k,n):
    a = p[i] - p[i-k]
    if a > mx:
        mx = a
        
print(mx)
### BUGGY CODE ###

from sys import stdin
from collections import deque
S=list(stdin.readline().strip())
N=list(map(int,stdin.readline().strip().split()))[0]

d = deque(S)
rev=False
for i in range(N):

    Q = list(stdin.readline().strip().split())
    if Q[0]=='1' :
        if rev==False:rev=True
        else:rev=False

    if Q[0]=='2':
        if Q[1]=='1':
            if rev==False:d.appendleft(Q[2])
            else:d.append(Q[2])
        if Q[1]=='2':
            if rev == False:
                d.append(Q[2])
            else:
                d.appendleft(Q[2])
if rev==False:[print(x,end="") for x in d]
else:[print(d[x],end="") for x in range(len(d)-1,-1,-1)]

### FIXED CODE ###

from sys import stdin
from collections import deque
d=deque(list(stdin.readline().strip()))
N=list(map(int,stdin.readline().strip().split()))[0]
rev=False
for i in range(N):
    Q = list(stdin.readline().strip().split())
    if Q[0]=='1' :
        if rev==False:rev=True
        else:rev=False
    if Q[0]=='2':
        if Q[1]=='1':
            if rev==False:d.appendleft(Q[2])
            else:d.append(Q[2])
        if Q[1]=='2':
            if rev == False:
                d.append(Q[2])
            else:
                d.appendleft(Q[2])
# if rev==False:[print(x,end="") for x in d]
# else:[print(d[x],end="") for x in range(len(d)-1,-1,-1)]
if rev==False:[print(d.popleft(),end="") for x in range(len(d))]
else:[print(d.pop(),end="") for x in range(len(d))]