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

import sys

sys.setrecursionlimit(10**6)
N, Q = map(int, input().split())
connections = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    pa, ki = map(int, input().split())
    connections[pa].append(ki)
    connections[ki].append(pa)

scores = [0 for _ in range(N + 1)]
for _ in range(Q):
    tag, p = map(int, input().split())
    scores[tag] += p

i = 1
fins = []

def dfs(k=1,bef=-1):
    global scores
    global fins
    kids = connections[k]
    if len(kids)==1 and bef==kids[0]:
        return
    for kid in kids:
        # print(f'k:{k} kids:{kids}')
        if bef==kid:
            continue
        scores[kid]+=scores[k]
        fins.append(kid)
        dfs(kid,k)


dfs()



print(*scores[1:])

### FIXED CODE ###

import sys

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

N, Q = map(int, input().split())
connections = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    pa, ki = map(int, input().split())
    connections[pa].append(ki)
    connections[ki].append(pa)

scores = [0 for _ in range(N + 1)]
for _ in range(Q):
    tag, p = map(int, input().split())
    scores[tag] += p

i = 1

def dfs(k=1,bef=-1):
    global scores
    global fins
    kids = connections[k]
    if len(kids)==1 and bef==kids[0]:
        return
    for kid in kids:
        # print(f'k:{k} kids:{kids}')
        if bef==kid:
            continue
        scores[kid]+=scores[k]
        dfs(kid,k)


dfs()



print(*scores[1:])
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
R = [list(map(int, input().split())) for i in range(Q)]
ans = []
for i in range(Q):
    x = R[i][0]-1
    y = R[i][1]
    a=S[x:y].count("AC")
    ans.append(a)

for i in range(Q):
    print(ans[i])

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0]*(N+1)
for i in range(N):
    t[i+1]=t[i] + (1 if S[i:i+2]=="AC" else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

import sys
import numpy as np

def IL():
	return list(map(int, sys.stdin.readline().rstrip().split()))


N, K = IL()
h_i = IL()
dp = np.full((N,), np.inf)
dp[0] = 0
for i in range(N):
	for j in range(1, K+1):
		if i+j < N:
			dp[i+j] = np.min([dp[i+j], abs(h_i[i] - h_i[i+j]) + dp[i]])
	
print(int(dp[-1]))

### FIXED CODE ###

import sys
import numpy as np

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def main():
	N, K = LI()
	h_i = np.array(LI())
	dp = np.full(N, 10**10, dtype=int)
	dp[0] = 0
	for i in range(1, N):
		dp[i:i+K] = np.fmin(dp[i:i+K], dp[i-1] + np.abs(h_i[i:i+K] - h_i[i-1]))
		
	return dp[-1]


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

def check(A, F, K, x):
    for i in range(len(A)):
        if A[i] * F[i] > x:
            need = (A[i] * F[i] - x + F[i] - 1) // F[i]
            if need > K:
                return False
            K -= need
    return True


N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
F = list(map(int, input().split(' ')))
A.sort()
F.sort()
F = F[::-1]

high, low = 10 ** 13, -1
while high - low > 1:
    mid = (high + low) // 2
    if check(A, F, K, mid):
        high = mid
    else:
        low = mid
print(high)

### FIXED CODE ###

def check(A, F, K, x):
    for i in range(len(A)):
        if A[i] * F[i] > x:
            need = (A[i] * F[i] - x + F[i] - 1) // F[i]
            if need > K:
                return False
            K -= need
    return True


N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
F = list(map(int, input().split(' ')))
A.sort()
F.sort()
F = F[::-1]

high, low = 10 ** 13, -1
while high - low > 1:
    mid = (high + low) // 2
    if check(A, F, K, mid):
        high = mid
    else:
        low = mid
print(high)
### BUGGY CODE ###

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


n, m, k = map(int, input().split())
uf = UnionFind(n)
friend = [0] * (n+1)
block = [0] * (n+1)

for _ in range(m):
    a, b = map(int, input().split())
    friend[a] += 1
    friend[b] += 1
    uf.union(a-1, b-1)

for _ in range(k):
    c, d = map(int, input().split())
    if uf.same(c-1, d-1):
        block[c] += 1
        block[d] += 1

groups = list(uf.all_group_members().values())
w = [0] * (n+1)

for group in groups:
    r = len(group)
    for member in group:
        member += 1
        w[member] = r - friend[member] - block[member] - 1

print(*w[1:])

### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.parents[self.find(x)]


n, m, k = map(int, input().split())
uf = UnionFind(n)
friend = [0] * (n+1)
block = [0] * (n+1)

for _ in range(m):
    a, b = map(int, input().split())
    friend[a] += 1
    friend[b] += 1
    uf.union(a-1, b-1)

for _ in range(k):
    c, d = map(int, input().split())
    if uf.same(c-1, d-1):
        block[c] += 1
        block[d] += 1

w = [0] * (n+1)

for i in range(1, n+1):
    w[i] = uf.size(i-1) - friend[i] - block[i] - 1

print(*w[1:])
### BUGGY CODE ###

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

for i in set(a):
    cnt = 0
    for j in a:
        if j - 1 <= i <= j + 1:
            cnt += 1
    ans = max(ans, cnt)

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    a = list(map(int, input().split()))
    l = [0]*(10**5 + 10)


    for i in a:
        l[i] += 1
        l[i + 1] += 1
        if i != 0:
            l[i - 1] += 1
    print(max(l))

main()
### BUGGY CODE ###

k,s=[int(i) for i in input().split()]
c=0
for i in range(k+1):
    for j in range(k+1):
        l=s-(i+j)
        if(0<=l<=k and i+j+l==s):
            c+=1
print(c)



### FIXED CODE ###

k,s=[int(i) for i in input().split()]
c=0
for i in range(k+1):
    for j in range(k+1):
        l=s-(i+j)
        if(0<=l<=k):
            c+=1
print(c)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
while m>0 and sum(a)>0:
  a[a.index(max(a))]=int(max(a)//2)
  m=m-1
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)
while m>0:
  heapq.heappush(a,(-1)*int((-1)*heapq.heappop(a)//2))
  m=m-1

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

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

ans = []
for i in range(N):
    if i < N-1:
        ans.append(A[i+1]-A[i])
ans.append(K-A[N-1])

c = list(itertools.combinations(ans,N-1))

a = []
for i in range(len(c)):
    a.append(sum(c[i]))
print(min(a))

### FIXED CODE ###

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

ans = []
for i in range(N-1):
    ans.append(A[i+1]-A[i])

ans.append(K-A[N-1]+A[0])
print(K-(max(ans)))
### BUGGY CODE ###

n = int(input())
b_list = list(map(int,input().split()))
b_list+=b_list
c_list = []
for i in range(n):
    sum_num = 0
    for j in range(i,i+n):
        sum_num += b_list[j]*((-1)**(j-i))
    c_list.append(sum_num)
print(" ".join(map(str,c_list)))

### FIXED CODE ###

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

from collections import deque
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1; Cw -= 1; Dh -= 1; Dw -= 1;
S = []

for _ in range(H):
    S.append(input())

dq = deque()
dq.append((Cw, Ch))

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

visited = [[-1 for _ in range(W)] for _ in range(H)]
visited[Ch][Cw] = 0
while dq:
    x, y = dq.popleft()

    #コスト無しで行けるエリアを列挙
    for dx_, dy_ in zip(dx, dy):
        if (not 0 <= x+dx_ < W) or (not 0 <= y+dy_ < H):
            continue
        if S[y+dy_][x+dx_] == "#":
            continue
        #まだ訪れていない or 実はノーコストで到達可能な点だった
        if visited[y+dy_][x+dx_] == -1 or visited[y+dy_][x+dx_] > visited[y][x]:
            visited[y+dy_][x+dx_] = visited[y][x]
            dq.appendleft((x+dx_, y+dy_))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if (not 0 <= x+i < W) or (not 0 <= y+j < H):
                continue
            if S[y+j][x+i] == '#':
                continue

            if visited[y+j][x+i] == -1:
                visited[y+j][x+i] = visited[y][x] + 1
                dq.append((x+i, y+j))

ans = visited[Dh][Dw]
print(ans)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1; Cw -= 1; Dh -= 1; Dw -= 1;
S = []

for _ in range(H):
    S.append(input())

dq = deque()
dq.append((Cw, Ch))

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

visited = [[-1 for _ in range(W)] for _ in range(H)]
visited[Ch][Cw] = 0
while dq:
    x, y = dq.popleft()

    #コスト無しで行けるエリアを列挙
    for dx_, dy_ in zip(dx, dy):
        if (not 0 <= x+dx_ < W) or (not 0 <= y+dy_ < H):
            continue
        if S[y+dy_][x+dx_] == "#":
            continue
        #まだ訪れていない or 実はノーコストで到達可能な点だった
        if visited[y+dy_][x+dx_] == -1 or visited[y+dy_][x+dx_] > visited[y][x]:
            visited[y+dy_][x+dx_] = visited[y][x]
            dq.appendleft((x+dx_, y+dy_))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if (not 0 <= x+i < W) or (not 0 <= y+j < H):
                continue
            if S[y+j][x+i] == '#':
                continue

            if visited[y+j][x+i] == -1:
                visited[y+j][x+i] = visited[y][x] + 1
                dq.append((x+i, y+j))

ans = visited[Dh][Dw]
print(ans)
### BUGGY CODE ###

from heapq import heappop, heappush, heapify

N, K = map(int, input().split())
sushi = []
for _ in range(N):
    t, d = map(int, input().split())
    sushi.append((-d, t))
heapify(sushi)

maxs = []
rems = []
kinds = set()
for _ in range(K):
    d, t = heappop(sushi)
    if t in kinds:
        heappush(rems, -d)
    else:
        maxs.append(-d)
        kinds.add(t)
ans = sum(maxs) + sum(rems) + len(kinds)**2

while True:
    if not sushi or not rems:
        break
    d, t = heappop(sushi)
    if t in kinds:
        continue
    else:
        heappop(rems)
        maxs.append(-d)
        kinds.add(t)
        ans = max(ans, sum(maxs) + sum(rems) + len(kinds)**2)

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(N)]
sushi.sort(key=lambda x: x[1], reverse=True)

score = 0

remains = []
kinds = set()
for t, d in sushi[:K]:
    if t in kinds:
        remains.append(d)
    kinds.add(t)
    score += d
score += len(kinds)**2

test = score
for t, d in sushi[K:]:
    if not remains:
        break
    if t in kinds:
        continue
    kinds.add(t)
    rm = remains.pop()
    test = test + (d - rm) + (len(kinds)*2 - 1)
    score = max(score, test)

print(score)
### BUGGY CODE ###

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

for _ in range(K):
    B = [0]*N
    for i in range(N):
        for j in range(max(0,i-A[i]),min(N,i+A[i]+1)):
            B[j] += 1

    # print(B)
    A = B

print(*B)

### FIXED CODE ###

import numpy as np

from numba import njit
@njit(cache=True)
def solve(N,K,A):
    for _ in range(K):
        B = np.zeros(N,dtype=np.int64)
        for i in range(N):
            l = max(0,i-A[i])
            r = min(N-1,i+A[i])
            B[l] += 1
            if N > r+1:
                B[r+1] -= 1
        
        A = np.cumsum(B)
        if np.all(A==N):
            break

    return A

def main():
    N,K = map(int,input().split())
    A = np.array(list(map(int,input().split())))

    A = solve(N,K,A)
    print(*A)

main()
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split(" ")]
r = [i+1-j for i, j in enumerate(a)]
l = [j+i+1 for i, j in enumerate(a)]
ans = 0
for i in set(r):
    p = r.count(i)
    q = l.count(i)
    ans += p*q
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
a = [int(i) for i in input().split(" ")]
r = [i+1-j for i, j in enumerate(a)]
l = [j+i+1 for i, j in enumerate(a)]
nl = Counter(l)
nr = Counter(r)
 
ans = 0
for k, v in nl.items():
    ans += nr[k]*v
print(ans)
### BUGGY CODE ###

r, g, b, n = map(int, input().split())

if r <= g and g <= b:
    pass
elif r <= b and b <= g:
    temp = g
    g = b
    b = temp
else:
    temp = r
    r = g
    g = temp

rg = {}
ri = 0
while ri <= n:
    gi = 0
    while gi <= n - ri:
        if (n - ri - gi) % b == 0:
            total = rg.get(ri + gi, 0)
            rg[ri + gi] = total + 1
        else:
            pass
        gi += g
    ri += r

bi = 0
result = 0

while bi <= n:
    total = rg.get(n - bi, 0)
    result += total
    bi += b

print(result)


### FIXED CODE ###

r, g, b, n = map(int, input().split())

if r >= g and g >= b:
    pass
elif r >= b and b >= g:
    temp = g
    g = b
    b = temp
else:
    temp = r
    r = g
    g = temp

if (r == 1 and g == 1) or (r == 1 and b == 1) or (g == 1 and b == 1):
    rg = [i + 1 for i in range(n + 1)]
elif (r == 1 and g == 2) or (r == 1 and b == 2) or (g == 1 and b == 2) or (r == 2 and g == 1) or (r == 2 and b == 1) or (g == 2 and b == 1):
    rg = [1 + i // 2 for i in range(n + 1)]
else:
    rg = [0 for _ in range(n + 1)]
    ri = 0
    while ri <= n:
        gi = 0
        while gi <= n - ri:
            rg[ri + gi] += 1
            gi += g
        ri += r

bi = 0
result = 0

while bi <= n:
    total = rg[n - bi]
    result += total
    bi += b

print(result)
### BUGGY CODE ###

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

ans = 0

for i in range(n):
    for j in range(i+1,n):
        if a[i]+a[j] == j-i:
            ans += 1
print(ans)

### FIXED CODE ###

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

mp = [0] * n

ans = 0

for i in range(n):
    if i-a[i] >= 0:
        ans += mp[i-a[i]]
    if n > a[i]+i:
        mp[a[i]+i] += 1

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

s = input()[::-1]
# (Xl,0 − Xr−1,0) % 2019 = 0 → Xl,0 % 2019 = Xr−1,0 % 2019
cnts = [1] + [0] * (2019 - 1)
tmp = 0
d = 1

for i in s:
    tmp += int(i) * d
    cnts[tmp % 2019] += 1
    d = d * 10 # 桁数が大きくなりすぎる → 10と2019が素だから可能な技

ans = 0
for cnt in cnts:
    ans += (cnt - 1) * cnt // 2

print(ans)


### FIXED CODE ###

s = input()[::-1]

cnts = [1] + [0] * (2019 - 1)
tmp = 0
d = 1

for i in s:
    tmp += int(i) * d
    cnts[tmp % 2019] += 1
    d = d * 10 % 2019 # 桁数が大きくなりすぎる → 10と2019が素だから可能

ans = 0
for cnt in cnts:
    ans += (cnt - 1) * cnt // 2

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

n,m,s = map(int, input().split())
G = [[] for i in range(n)]
for i in range(m):
    u,v,a,b = map(int, input().split())
    u,v = u-1, v-1
    G[u].append([v, a, b])
    G[v].append([u, a, b])
cd = [list(map(int, input().split())) for i in range(n)]

from heapq import heappop, heappush
max_money = n*60
state = [[float("inf")]*(max_money+1) for i in range(n)]
s = min(s, max_money)
heap = [(0,-s,0)]
while heap:
    time, money, cur = heappop(heap)
    money = -money
    if state[cur][money] <= time:
        continue
    state[cur][money] = time
    n_money = money
    n_time = time
    f = False
    for i in range(10000):
        n_money += cd[cur][0]
        n_time += cd[cur][1]
        if n_money > max_money:
            n_money = max_money
            f = True
        if state[cur][n_money] < n_time:
            break
        heappush(heap, (n_time, -n_money, cur))
        if f:
            break
    for to, a,b in G[cur]:
        if money < a or state[to][money-a] <= time+b:
            continue
        heappush(heap, (time+b, -(money-a), to))

for i in range(1, n):
    print(min(state[i]))

### FIXED CODE ###

max_s = 2500

n,m,s = map(int, input().split())
s = min(s, max_s)
conv = lambda i,j : i*10000+j

G = [[] for i in range(conv(n-1, max_s)+1)]
for i in range(m):
    u,v,a,b = map(int, input().split())
    u,v = u-1, v-1
    for j in range(max_s+1):
        if j-a >= 0:
            G[conv(u,j)].append((conv(v,j-a), b))
            G[conv(v,j)].append((conv(u,j-a), b))

for i in range(n):
    c,d = map(int, input().split())
    for j in range(max_s+1):
        if j+c > max_s:
            break
        G[conv(i,j)].append((conv(i,j+c), d))

from heapq import heappush, heappop
def dijkstra(G, start):
    n = len(G)
    dist = [float("inf")]*n
    visited = set()
    heap = [(0, start)]

    while heap and len(visited) != n:
        d, cur = heappop(heap)
        if cur in visited:
            continue
        visited.add(cur)
        dist[cur] = d
        for to, cost in G[cur]:
            if to not in visited:
                heappush(heap, (d+cost, to))
    return dist

dist = dijkstra(G, conv(0, s))
for i in range(1,n):
    cost = min(dist[conv(i,0):conv(i,max_s)+1])
    print(cost)
### BUGGY CODE ###

import heapq

def main():
    n, m = map(int, input().split())
    dics = [{} for _ in range(n)]
    for _ in range(m):
        l, r, c = map(int, input().split())
        ky = r-1
        if ky in dics[l-1]:
            if c < dics[l-1][ky]:
                dics[l-1][ky] = c
        else:
            dics[l-1][ky] = c
    dist = [float("inf")]*n
    dist[0] = 0
    hq = []
    heapq.heappush(hq, [0, 0])
    idx = 0
    while len(hq) > 0:
        v, p = heapq.heappop(hq)
        if p < idx:
            continue
        if p == n-1:
            break
        for i in range(idx, p):
            if len(dics[i]) > 0:
                for ky in dics[i].keys():
                    if ky in dics[p]:
                        if dics[p][ky] > dics[i][ky]:
                            dics[p][ky] = dics[i][ky]
                    else:
                        if p < ky:
                            dics[p][ky] = dics[i][ky]
        idx = p
        for r in dics[p].keys():
            if dist[r] > v + dics[p][r]:
                dist[r] = v + dics[p][r]
                heapq.heappush(hq, [v + dics[p][r], r])
    if dist[n-1] == float("inf"):
        print(-1)
    else:
        print(dist[n-1])

if __name__ == "__main__":
    main()


### FIXED CODE ###

import heapq

def main():
    n, m = map(int, input().split())
    dics = [{} for _ in range(n)]
    for _ in range(m):
        l, r, c = map(int, input().split())
        ky = r-1
        if ky in dics[l-1]:
            if c < dics[l-1][ky]:
                dics[l-1][ky] = c
        else:
            dics[l-1][ky] = c
    dist = [float("inf")]*n
    dist[0] = 0
    hq = []
    heapq.heappush(hq, [0, 0])
    idx = 0
    while len(hq) > 0:
        v, p = heapq.heappop(hq)
        if p < idx:
            continue
        if p == n-1:
            break
        for i in range(idx+1, p):
            if len(dics[i]) > 0:
                for ky in dics[i].keys():
                    if ky in dics[p]:
                        if dics[p][ky] > dics[i][ky]:
                            dics[p][ky] = dics[i][ky]
                    else:
                        if p < ky:
                            dics[p][ky] = dics[i][ky]
        idx = p
        for r in dics[p].keys():
            if dist[r] > v + dics[p][r]:
                dist[r] = v + dics[p][r]
                heapq.heappush(hq, [v + dics[p][r], r])
    if dist[n-1] == float("inf"):
        print(-1)
    else:
        print(dist[n-1])

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

if __name__ == "__main__":
    N = int(input())
    L = list(map(int, input().split()))

    L.sort()
    L.reverse()

    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            for k in range(j+1, N):
                if i != j and j != k and k != i:
                    if L[i] < L[j] + L[k] and L[j] < L[k] + L[i] and L[k] < L[i] + L[j]:
                        ans += 1
                        # print("{} {} {}".format(L[i], L[j], L[k]))

    print(ans)


### FIXED CODE ###

from bisect import bisect_right

if __name__ == "__main__":
    N = int(input())
    L = list(map(int, input().split()))

    L.sort()

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

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

import collections

d = collections.deque()
for i in input():
    d.append(i)
q = int(input())
is_head = True

for _ in range(q):
    tmp = input().split(" ")
    if (len(tmp) == 1):
        is_head = not is_head
    else:
        t, f, c = tmp
        if (f == '1'):
            if (is_head):
                d.appendleft(c)
            else:
                d.append(c)
        else:
            if (is_head):
                d.append(c)
            else:
                d.appendleft(c)

ans = ""
if is_head:
    while len(d) > 0:
        ans += d.popleft()
else:
    while len(d) > 0:
        ans += d.pop()
print(ans)

### FIXED CODE ###

import collections

d = collections.deque()
for i in input():
    d.append(i)
q = int(input())
is_head = True

for _ in range(q):
    tmp = input().split(" ")
    if (len(tmp) == 1):
        is_head = not is_head
    else:
        t, f, c = tmp
        if (f == '1'):
            if (is_head):
                d.appendleft(c)
            else:
                d.append(c)
        else:
            if (is_head):
                d.append(c)
            else:
                d.appendleft(c)

ans = ""
if is_head:
    while len(d) > 0:
        ans += d.popleft()
else:
    while len(d) > 0:
        ans += d.pop()
print(ans)