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

S = list(input())
Q = int(input())
is_reversed = False

for i in range(Q):
  q = list(input())
  if q[0] == '1':
    is_reversed = True if is_reversed == False else False
  else:
    if q[2] == '1' and is_reversed:
      S.append(q[4])
    elif q[2] == '1': 
      S.insert(0, q[4])
    elif is_reversed:
      S.insert(0, q[4])      
    else:
      S.append(q[4])
      
if is_reversed:
  S.reverse()
  
print(''.join(S))

### FIXED CODE ###

S = list(input())
Q = int(input())
is_reversed = False
append_first = []
my_first = append_first.append
append_end = []
my_end = append_end.append

for i in range(Q):
  q = list(input())
  if q[0] == '1':
    is_reversed = True if is_reversed == False else False
  else:
    if q[2] == '1' and is_reversed:
      append_end.append(q[4])
    elif q[2] == '1': 
      append_first.append(q[4])
    elif is_reversed:
      append_first.append(q[4])   
    else:
      append_end.append(q[4])
      
append_first.reverse()
append_first.extend(S) 
append_first.extend(append_end)

if is_reversed:
  append_first.reverse()
print(''.join(append_first))
### BUGGY CODE ###

# -*- coding: utf-8 -*-


def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    cost = [float('inf') for _ in range(n)]
    cost[n - 1] = 0

    for j in range(2, n + 1):
        for i in range(max(1, j - k), j + 1):
            cost[n - j] = min(cost[n - j],
                              cost[n - i] + abs(h[n - i] - h[n - j]))

    print(cost[0])


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-


def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    cost = [float('inf') for _ in range(n)]
    cost[n - 1] = 0

    for j in range(2, n + 1):
        for i in range(max(1, j - k), j + 1):
            cost[n - j] = min(cost[n - j],
                              cost[n - i] + abs(h[n - i] - h[n - j]))

    print(cost[0])


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

L,R=map(int,input().split())
ans=2018
for i in range(L,R+1):
  for j in range(L,R+1):
    if i>=j: continue
    cnt=(i*j)%2019
    ans=min(ans,cnt)
print(ans)

### FIXED CODE ###

L,R=map(int,input().split())
if R-L>=2019:
    minimum=0
else:
    left,right=L%2019,R%2019
    minimum=2018**2
    for i in range(left,right+1):
        for j in range(i+1,right+1):
            minimum=min(minimum,i*j%2019)
print(minimum)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh, Dw = map(int, input().split())
Dh -= 1
Dw -= 1
S = [input() for _ in range(H)]

dh = [-1, 0, 0, 1]
dw = [0, 1, -1, 0]

INF = pow(10, 10)
seen = [[INF] * W for _ in range(H)]
seen[Ch][Cw] = 0
q = deque()
q.append([Ch, Cw, 0])

while q:
    th, tw, t = q.pop()
    for i in range(4):
        nh = th + dh[i]
        nw = tw + dw[i]
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= t:
            continue
        seen[nh][nw] = t
        q.append([nh, nw, t])
    for dh2 in range(-2, 3):
        for dw2 in range(-2, 3):
            if dh2 == 0 and dw2 == 0:
                continue
            nh = th + dh2
            nw = tw + dw2
            if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= t + 1:
                continue
            seen[nh][nw] = t + 1
            q.append([nh, nw, t + 1])

if seen[Dh][Dw] is INF:
    print(-1)
else:
    print(seen[Dh][Dw])

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh, Dw = map(int, input().split())
Dh -= 1
Dw -= 1
S = [input() for _ in range(H)]

dh = [-1, 0, 0, 1]
dw = [0, 1, -1, 0]

INF = pow(10, 10)
seen = [[INF] * W for _ in range(H)]
seen[Ch][Cw] = 0
q = deque()
q.append([Ch, Cw])

while q:
    th, tw = q.pop()
    for i in range(4):
        nh = th + dh[i]
        nw = tw + dw[i]
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= seen[th][tw]:
            continue
        seen[nh][nw] = seen[th][tw]
        q.append([nh, nw])
    for dh2 in range(-2, 3):
        for dw2 in range(-2, 3):
            if dh2 == 0 and dw2 == 0:
                continue
            nh = th + dh2
            nw = tw + dw2
            if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= seen[th][tw] + 1:
                continue
            seen[nh][nw] = seen[th][tw] + 1
            q.appendleft([nh, nw])

if seen[Dh][Dw] is INF:
    print(-1)
else:
    print(seen[Dh][Dw])
### BUGGY CODE ###

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

lists = [[] for _ in range(N)]
items = [list(map(int, input().split())) for _ in range(M)]
for p, y in items:
  lists[p-1].append(y)

for n in range(N):
  lists[n].sort()  

for p, y in items:
  index = lists[p-1].index(y)
  print("{:06g}{:06g}".format(p,index+1))

### FIXED CODE ###

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

lists = [[] for _ in range(N)]
items = [list(map(int, input().split())) for _ in range(M)]
for p, y in items:
  lists[p-1].append(y)

dic = {}

for n in range(N):
  lists[n].sort()  

for n in range(N):
  l = lists[n]
  count = 1
  for i in l:
    dic[i] = count
    count+=1

for p, y in items:
  print("{:06g}{:06g}".format(p,dic[y]))
### BUGGY CODE ###

# soundhound2018_summer_qual_d
import networkx as nx
n, m, s, t = map(int, input().split())


Gy = nx.Graph()   # Yen
Gy.add_nodes_from(range(1, n+1))

Gs = nx.Graph()   # Snuuk
Gs.add_nodes_from(range(1, n+1))


for _ in range(m):
    u, v, a, b = map(int, input().split())
    Gy.add_edge(u, v, weight=a)
    Gs.add_edge(u, v, weight=b)

shortest_length_from_s = nx.shortest_path_length(Gy, source=s, weight='weight')
shortest_length_to_t = nx.shortest_path_length(Gs, target=t, weight='weight')


dist = [-1]
for i in range(1, n+1):
    dist.append(shortest_length_from_s[i]+shortest_length_to_t[i])
# print(dist)

for i in range(1, n+1):
    print(10**15-sorted(dist[i:])[0])


### FIXED CODE ###

import numpy as np
from heapq import heappush, heappop

n, m, s, t = map(int, input().split())
G = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    G[u].append((v, a, b))
    G[v].append((u, a, b))


def dijkstra(start, mode):
    INF = 10 ** 15
    dist = [INF] * (n+1)
    dist[start] = 0
    q = [(0, start)]
    while q:
        d, v = heappop(q)
        if dist[v] < d:
            continue
        for w, *a in G[v]:
            d1 = d + a[mode]
            if dist[w] > d1:
                dist[w] = d1
                heappush(q, (d1, w))
    return dist


d1 = np.array(dijkstra(s, 0))
d2 = np.array(dijkstra(t, 1))

# print(d1)


d = []
for i in range(n+1):
    d.append(d1[i]+d2[i])


ans = []
B = 10**15
for i in range(n):
    B = min(B, d[n-i])
    ans.append(B)
ans = ans[::-1]

for i in range(n):
    print(10**15-ans[i])
### BUGGY CODE ###

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

cnt=0
for i in range(N):
    if i + As[i]>N:
        continue
    for j in range(i+As[i],N):
        if j-i == As[i] + As[j]:
            cnt+=1
print(cnt)

### FIXED CODE ###

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

d1={}
for i,e in enumerate(As):
    d=i-e
    if d > 0:
        if d in d1.keys():
            d1[d]+=1
        else:
            d1[d]=1
cnt=0
for i,e in enumerate(As):
    if (i+e) in d1.keys():
        cnt += d1[i+e]
print(cnt)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# input
n = int(input())
a_list = []
a_dic = {}
for ai in input().split():
    int_ai = int(ai)
    a_list.append(int_ai)
    if int_ai in a_dic:
        a_dic[int_ai] += 1
    else:
        a_dic[int_ai] = 1

a_solution_dic = {}
a_solution_dic_at_k = {}
for key in list(a_dic.keys()):
    if a_dic[key] == 1:
        del a_dic[key]
        continue
    a_solution_dic[key] = int(a_dic[key] * (a_dic[key]-1) / 2)
    #a_solution_dic_at_k[key] = int((a_dic[key]-1) * (a_dic[key]-2) / 2)

for k, ak in enumerate(a_list):
    sum_select = 0
    if ak in a_dic.keys():
        sum_select += int((a_dic[ak]-1) * (a_dic[ak]-2) / 2)
    for key in a_solution_dic:
        if key != ak:
            sum_select += a_solution_dic[key]


    print(sum_select)


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# input
n = int(input())
a_list = []
a_dic = {}
for ai in input().split():
    int_ai = int(ai)
    a_list.append(int_ai)
    if int_ai in a_dic:
        a_dic[int_ai] += 1
    else:
        a_dic[int_ai] = 1

a_solution_dic = {}
all_sum_select = 0
for key in list(a_dic.keys()):
    all_sum_select += int(a_dic[key] * (a_dic[key]-1) / 2)
    #a_solution_dic_at_k[key] = int((a_dic[key]-1) * (a_dic[key]-2) / 2)

for k, ak in enumerate(a_list):
    sum_select_at_k = all_sum_select + int((a_dic[ak]-1) * (a_dic[ak]-2) / 2) \
                       - int(a_dic[ak] * (a_dic[ak]-1) / 2)


    print(sum_select_at_k)
### BUGGY CODE ###



from functools import *
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())




def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact


def serch(x, count):
    #print("top", x, count)

    for d in directions:
        nx = d+x
        # print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)

    return count


N = int(input())
A = []
for i in range(N):
    A.append(II())


if A[0] >0:
    print(-1)
    sys.exit()

for i in range(1, N):
    if A[i]-A[i-1] > 1:
        print(-1)
        sys.exit()

count = 0
x = [0]*N

for i in reversed(range(N)):
    if A[i] != x[i]:
        for j in range(i-A[i], i):
            x[j+1] = x[j]+1
            count += 1


print(count)


### FIXED CODE ###



from functools import *
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())




N = int(input())
A = []
for i in range(N):
    A.append(II())


if A[0] >0:
    print(-1)
    sys.exit()

for i in range(1, N):
    if A[i]-A[i-1] > 1:
        print(-1)
        sys.exit()

count = 0
x = [0]*N

for i in range(0,N-1):
    if A[i]+1==A[i+1]:
        count+=1
    else:
        count+=A[i+1]

""" for i in reversed(range(N)):
    if A[i] != x[i]:
        for j in range(i-A[i], i):
            x[j+1] = x[j]+1
            count += 1

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

import sys

def longestcommonsubsequence():
    seq1 = raw_input()
    seq2 = raw_input()

    a,b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    i=0
    for e1 in seq1:
        x2 = x1
        x1 = [0 for i in range(b+1)]
        j=0
        for e2 in seq2:
            if e1 == e2:
                x1[j+1]=x2[j] + 1
            else:
                x1[j+1]=max(x2[j+1], x1[j])
            j += 1
        i += 1
    return x1[-1]

n = input()
for i2 in range(n):

    print longestcommonsubsequence()

### FIXED CODE ###

import sys

def longestcommonsubsequence():
    seq1 = raw_input()
    seq2 = raw_input()

    a, b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = seq1[i]
        x2 = x1+[]
        #x1 = [0 for i2 in range(b+1)]
        for j in range(b):
            if e1 == seq2[j]:
                x1[j+1] = x2[j] + 1
            elif x1[j+1]<x1[j]:
                x1[j+1] = x1[j]
    return x1[-1]

n = input()
for i2 in range(n):

    print longestcommonsubsequence()
### BUGGY CODE ###

a, b, n = map(int, input().split())
print(max([(a*i)//b - a*(i//b) for i in range(n + 1)]))

### FIXED CODE ###

a, b, n = map(int, input().split())
if n < b:
    k = n
else:
    k = b - 1
print((a*k)//b - a*(k//b))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, X, Y, Z = MAP()
M = X + Y + Z

# XYZとの一致をチェックするビット列
check = 1<<(X+Y+Z-1) | 1<<(Y+Z-1) | 1<<(Z-1)
dp = list2d(N+1, 1<<(M-1), 0)
# dp[i][S] := i個目まで見て、前の値M-1以下までの集合がSの時の、XYZを含まないものの通り数
dp[0][0] = 1
msk1 = (1<<M) - 1
msk2 = (1<<(M-1)) - 1
for i in range(N):
    for S in range(1<<(M-1)):
        if not dp[i][S]:
            continue
        for j in range(10):
            # 1ビットずらして1を足してjビットずらしてマスクする
            S2 = (S<<1|1)<<j & msk1
            # 直前Mビットで使った値がXYZと一致していないか確認する
            if not (S2 & check) == check:
                dp[i+1][S2&msk2] += dp[i][S]
                dp[i+1][S2&msk2] %= MOD
total = pow(10, N, MOD)
cnt = 0
for S in range(1<<(M-1)):
    cnt += dp[N][S]
    cnt %= MOD
print((total-cnt)%MOD)


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, X, Y, Z = MAP()
M = X + Y + Z

# XYZとの一致をチェックするビット列
check = 1<<(X+Y+Z-1) | 1<<(Y+Z-1) | 1<<(Z-1)
dp = list2d(N+1, 1<<(M-1), 0)
# dp[i][S] := i個目まで見て、前の値M-1以下までの集合がSの時の、XYZを含まないものの通り数
dp[0][0] = 1
msk1 = (1<<M) - 1
msk2 = (1<<(M-1)) - 1
for i in range(N):
    for S in range(1<<(M-1)):
        if not dp[i][S]:
            continue
        for j in range(10):
            # 1ビットずらして1を足してjビットずらしてマスクする
            S2 = (S<<1|1)<<j & msk1
            # 直前Mビットで使った値がXYZと一致していないか確認する
            if not (S2 & check) == check:
                dp[i+1][S2&msk2] += dp[i][S]
                dp[i+1][S2&msk2] %= MOD
total = pow(10, N, MOD)
cnt = 0
for S in range(1<<(M-1)):
    cnt += dp[N][S]
    cnt %= MOD
print((total-cnt)%MOD)
### BUGGY CODE ###

from bisect import bisect_left
N = int(input())
L = list(map(int, input().split()))
L.sort()
res = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        idx = bisect_left(L[j+1:], L[i]+L[j])
        res += idx
print(res)

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = list(map(int, input().split()))
L.sort()
res = 0
for i in range(N):
    for j in range(i+1, N):
        idx = bisect_left(L, L[i]+L[j])
        res += max(0,idx-(j+1))
print(res)
### BUGGY CODE ###

def hoge(S):
    cum = 0
    mi = 0
    for s in S:
        cum += 1 if s == '(' else -1
        mi = min(mi, cum)
    return (-mi, cum - mi)

N = int(input())
S = [hoge(input()) for _ in range(N)]

plus = []
minus = []

for l, r in S:
    if l <= r:
        plus.append((l, r))
    else:
        minus.append((l, r))

plus.sort(key=lambda a: a[0])
minus.sort(key=lambda a: a[1], reverse=True)
M = 0
for l, r in (plus + minus):
    M -= l
    if M < 0:
        print('No')
        exit()
    M += r

print('Yes' if M == 0 else 'No')


### FIXED CODE ###

N = int(input())
S = [input() for _ in range(N)]

def calc(T):
    now = 0
    ret = 0
    for s in T:
        if s == '(':
            now += 1
        elif s == ')':
            now -= 1
        ret = min(ret, now)
    return ret

H = []
P = []
L = []

for s in S:
    less = -calc(s)
    if less == 0:
        H.append(s)
    else:
        l = s.count('(')
        r = len(s) - l
        if l >= r:
            P.append((less, s))
        else:
            L.append((less - (r - l), s))

P.sort(key=lambda a: a[0])
L.sort(key=lambda a: a[0], reverse=True)
P = [s for _, s in P]
L = [s for _, s in L]
ans = ''.join(H) + ''.join(P) + ''.join(L)

l = ans.count('(')
r = len(ans) - l

if l != r or calc(ans) < 0:
    print('No')
else:
    print('Yes')
### BUGGY CODE ###

s = input()

count = 0
while True:
    n = len(s)
    if n == 0 or all(c == '0' for c in s) or all(c == '1' for c in s):
        break
    sn = s + '\n'
    for i in range(n):
        if sn[i-1] + sn[i] == '10' or sn[i-1] + sn[i] == '01':
            s = sn[:i-1] + sn[i+1:n]
            count += 1
            break

print(count * 2)

### FIXED CODE ###

s = input()

zero = s.count('0')
one = s.count('1')

print(2 * min(zero, one))
### BUGGY CODE ###

#coding:utf-8
import bisect,math
A,B,Q=map(int,raw_input().split())
s=[]
t=[]
for a in range(A):
    s.append(input())
for a in range(B):
    t.append(input())
for _ in range(Q):
    x=input()
    sl=bisect.bisect_left(s,x)-1
    sr=bisect.bisect_left(s,x)
    tl=bisect.bisect_left(t,x)-1
    tr=bisect.bisect_left(t,x)
    ans=1<<50
    if sl!=-1 and tl!=-1:
        A=max(s[sl],t[tl])
        B=min(s[sl],t[tl])
        L=abs(x-A)+abs(A-B)
        ans=min(ans,L)
    if sl!=-1 and tr!=len(t):
        L=abs(x-s[sl])*2 + abs(t[tr]-x)
        ans=min(ans,L)
        ans=min(ans,abs(x-s[sl])+abs(t[tr]-x)*2)
    if tl!=-1 and sr!=len(s):
        ans=min(ans,abs(x-t[tl])*2+abs(s[sr]-x))
        ans=min(ans,abs(x-t[tl])+abs(s[sr]-x)*2)
    if tr!=len(t) and sr!=len(s):
        A=min(s[sr],t[tr])
        B=max(s[sr],t[tr])
        L=abs(A-x)+abs(B-A)
        ans=min(ans,L)
    print(ans)
    
    




### FIXED CODE ###

#coding:utf-8
import bisect,sys
A,B,Q=map(int,raw_input().split())
s=[0]*A
t=[0]*B
for i in range(A):    
    s[i]=int(sys.stdin.readline())
for i in range(B):
    t[i]=int(sys.stdin.readline())
buf=[]
def f(x):
    sl=bisect.bisect_left(s,x)-1
    sr=sl+1
    tl=bisect.bisect_left(t,x)-1
    tr=tl+1
    ans=float("inf")
    if sl!=-1 and tl!=-1:
        A=max(s[sl],t[tl])
        B=min(s[sl],t[tl])
        L=abs(x-A)+abs(A-B)
        ans=min(ans,L)
    if sl!=-1 and tr!=len(t):
        L=abs(x-s[sl])*2 + abs(t[tr]-x)        
        ans=min(ans,L)
        ans=min(ans,abs(x-s[sl])+abs(t[tr]-x)*2)
    if tl!=-1 and sr!=len(s):
        ans=min(ans,abs(x-t[tl])*2+abs(s[sr]-x))
        ans=min(ans,abs(x-t[tl])+abs(s[sr]-x)*2)
    if tr!=len(t) and sr!=len(s):
        A=min(s[sr],t[tr])
        B=max(s[sr],t[tr])
        L=abs(A-x)+abs(B-A)
        ans=min(ans,L)
    return str(ans)

I=[0]*Q
for i in xrange(Q):
    I[i]=int(sys.stdin.readline())
r=map(f,I)
print("\n".join(r))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(65536)

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

uf=[i for i in range(N+1)]
nc=[1 for i in range(N+1)]

def find(i):
	if uf[i] == i:
		return i
	else:
		uf[i] = find(uf[i])
		return uf[i]

def union(i, j):
	gi, gj = find(i), find(j)
	if gi != gj:
		uf[gi] = gj
		diff = nc[gj] * nc[gi]
		nc[gj] += nc[gi]
		return diff
	return 0

su = N*(N-1)//2
ans = [-1]*M

for i in range(M-1, -1, -1):
	ans[i] = su
	x,y = bridge[i]
	su -= union(x, y)

print("\n".join(map(str, ans)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(65536)

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

uf=[i for i in range(N+1)]
nc=[1 for i in range(N+1)]

def find(i):
	if uf[i] == i:
		return i
	else:
		uf[i] = find(uf[i])
		return uf[i]

def union(i, j):
	gi, gj = find(i), find(j)
	if gi != gj:
		uf[gi] = gj
		diff = nc[gj] * nc[gi]
		nc[gj] += nc[gi]
		return diff
	return 0

su = N*(N-1)//2
ans = [-1]*M

for i in range(M-1, -1, -1):
	ans[i] = su
	x,y = bridge[i]
	su -= union(x, y)

print("\n".join(map(str, ans)))
### BUGGY CODE ###

S = input()
q = int(input())

is_s0_head = True
tail = len(S)-1

for _ in range(q):
    # print(S)
    Q = list(input().split())
    if Q[0] == "1":
        is_s0_head = not is_s0_head
    else:
        if Q[1] == "1":
            if is_s0_head:
                S = Q[2] + S
            else:
                S = S + Q[2]
        else:
            if is_s0_head:
                S = S + Q[2]
            else:
                S = Q[2] + S

if is_s0_head:
    print(S)
else:
    print(S[::-1])


### FIXED CODE ###

from collections import deque

S = input()
q = int(input())

is_s0_head = True
tail = len(S)-1

queue = deque(S)

for _ in range(q):
    # print(queue)
    Q = list(input().split())
    if Q[0] == "1":
        is_s0_head = not is_s0_head
    else:
        if Q[1] == "1":
            if is_s0_head:
                queue.appendleft(Q[2])
            else:
                queue.append(Q[2])
        else:
            if is_s0_head:
                queue.append(Q[2])
            else:
                queue.appendleft(Q[2])

if is_s0_head:
    print("".join(list(queue)))
else:
    print("".join(list(queue)[::-1]))
### BUGGY CODE ###

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

sign = 1
head = ""
tail = ""
for i in range(Q):
    Q = [i for i in input().split()]
    if Q[0] == "1":
        sign *= -1
    else:
        if Q[1] == "1" and sign == 1:
            head = Q[2] + head
        elif Q[1] == "1" and sign == -1:
            tail = tail + Q[2]
        elif Q[1] == "2" and sign == 1:
            tail = tail + Q[2]
        elif Q[1] == "2" and sign == -1:
            head = Q[2] + head

if sign==1:
    print(head + S + tail)
elif sign==-1:
    S = (head + S + tail)[::-1]
    print(S)


### FIXED CODE ###

from collections import deque

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

sign = 1
head = ""
tail = ""
for i in range(Q):
    Q = input().split()
    if Q[0] == "1":
        sign *= -1
    else:
        if int(Q[1]) * sign == 1:
            S.appendleft(Q[2])
        elif int(Q[1]) * sign == -1:
            S.append(Q[2])
        elif int(Q[1]) * sign == 2:
            S.append(Q[2])
        elif int(Q[1]) * sign == -2:
            S.appendleft(Q[2])

if sign==1:
    print("".join(S))
elif sign==-1:
    S.reverse()
    print("".join(S))
### BUGGY CODE ###

def max_heapify(A, i, pt):
    l = (i+1)*2-1
    r = (i+1)*2
    largest = i
    if l <= pt and A[largest] < A[l]:
        largest = l
    if r <= pt and A[largest] < A[r]:
        largest = r

    if largest != i:
        A[largest],A[i] = A[i],A[largest]
        max_heapify(A,largest,pt)

heap = [0]*2000000
pt = -1
while True:
    c = raw_input()
    if c[0] == 'i':
        n = int(c[7:])
        pt += 1
        heap[pt] = n
        i = pt
        p = (i+1)/2-1
        while p >= 0 and heap[p] < heap[i]:
            heap[p],heap[i] = heap[i],heap[p]
            i = p
            p = (i+1)/2-1
    elif c[1] == 'x':
        ret = heap[0]
        heap[0] = heap[pt]
        pt -= 1
        max_heapify(heap,0,pt)
        print ret
    else:
        break

### FIXED CODE ###

from sys import stdin

def max_heapify(A, i):
    l = i*2
    r = i*2+1
    largest = i
    if l <= A[0] and A[i] < A[l]:
        largest = l
    else:
        largest = i
    if r <= A[0] and A[largest] < A[r]:
        largest = r

    if largest != i:
        A[largest],A[i] = A[i],A[largest]
        max_heapify(A,largest)

heap = [0]*2000000
for c in stdin:
    if c[0] == 'i':
        heap[0] += 1
        heap[heap[0]] = int(c[7:])
        i = heap[0]
        p = i/2
        while p > 0 and heap[p] < heap[i]:
            heap[p],heap[i] = heap[i],heap[p]
            i = p
            p = i/2
    elif c[1] == 'x':
        print heap[1]
        heap[1] = heap[heap[0]]
        heap[0] -= 1
        max_heapify(heap,1)
    else:
        break