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

def solve():
    N = int(raw_input())
    D = [int(raw_input()) for i in range(N)]
    if sum(D) % 2 > 0:
        print '-1'
        return
    Di = sorted([(di, i) for i, di in enumerate(D)], key = lambda x : x[0], reverse = True)
    d_to_i = {dd:i for dd, i in Di}
    # child = [[] for i in range(N)]
    ans = []
    n_child = [1] * N
    d_child = [0] * N
    for valD, node in Di:
        valD_par = valD - N + 2 * n_child[node]
        if valD_par in d_to_i.keys():
            node_par = d_to_i[valD_par]
            # child[node].append(node_par) ##
            # child[node_par].append(node)
            ans.append([node_par + 1, node + 1])
            n_child[node_par] += n_child[node]
            d_child[node_par] += n_child[node] + d_child[node]
            if n_child[node_par] == N:
                break
        else:
            print '-1'
            return
    # check if Di satisfied or not
    d_min, i_min = Di[-1]
    if d_child[i_min] != d_min:
        print '-1'
        return
    # for i in range(N):
    #     for j in child[i]:
    #         print str(i + 1) + ' ' + str(j + 1)
    for ele in ans:
        print str(ele[0]) + ' ' + str(ele[1])

if __name__ == '__main__':
    solve()


### FIXED CODE ###

n = int(input())
d = [int(input()) for i in range(n)]

if sum(d)%2 > 0:
    print(-1)
    exit()

d = sorted([(dd, i) for i, dd in enumerate(d)], reverse = True)
d_to_i = {dd:i for dd, i in d}
n_child = [1]*n
d_child = [0]*n
ans = []
for dd, i in d:
    d_i = dd+2*n_child[i]-n
    if d_i in d_to_i.keys():
        i_next = d_to_i[d_i]
        ans.append((i+1, i_next+1))
        n_child[i_next] += n_child[i]
        d_child[i_next] += d_child[i] + n_child[i]
        if n_child[i_next] == n:
            break
    else:
        print(-1)
        exit()

d_min, i_min = d[-1]
if d_min == d_child[i_min]:
    for a in ans:
        print(*a)
else:
     print(-1)
### BUGGY CODE ###

n = int(input())
ans = 0

A = [["".join(sorted(input()))] for _ in range(n)]
A.sort()

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


### FIXED CODE ###

n = int(input())
ans = 0

A = [["".join(sorted(input()))] for _ in range(n)]
A.sort()

k = 0

for i in range(n-1):
    if k > 1:
        k = k-1
        ans += k
    else:
        k = 0
        a = A[i]
        for j in range(n-i-1):
                if a == A[j+i+1]:
                    ans += 1
                    k += 1
                else:
                    break

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

import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def main():
	n, m = IN()
	vl=[]
	for n in range(n):
		a,b = IN()
		vl.append((a,b))
		
	vl.sort(key=lambda x:-x[1])
	ret = 0
	nwdl=[-1]*(m+1) #list(range(m+1))
	for a,b in vl:
		j=m-a
		while j >= 0:
			if nwdl[j]==-1:
				nwdl[j]=0
				ret+=b
				break
			j-=1
		#pa((a,b,m-a,nwdl))
	print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys
import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

class node:
	def __init__(self,a_val, a_parent=None):
		self.val=a_val
		self.parent=a_parent
		self.right=None
		self.left=None

def main2():
	n, m = IN()
	vl=[]
	for n in range(n):
		a,b = IN()
		vl.append((a,b))
		
	vl.sort(key=lambda x:-x[1])
	ret = 0
	nwdl=[-1]*(m+1) #list(range(m+1))
	for a, b in vl:
		j=m-a
		while j >= 0:
			if nwdl[j]==-1:
				nwdl[j]=0
				ret+=b
				break
			j-=1
		#pa((a,b,m-a,nwdl))
	print(ret)
	
	
def main():
	n, m = IN()
	st_day=[[] for _ in range(m+1)]
	for n in range(n):
		duration, pay = IN()
		if duration > m:
			continue
		st_day[m-duration].append(pay)
	
	pq=queue.PriorityQueue()
	ret = 0
	for di in range(m+1):
		day=m-di
		for pay in st_day[day]:
			pq.put(-pay)
		if not pq.empty():
			v = pq.get()
			ret -= v
	print(ret)
			
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

inp = int(input())
A = []
for a in range(inp):
    A.append(input())

def charcnt(s):
    cset = {}
    for c in s:
        if c in cset:
            cset[c] += 1
        else:
            cset[c] = 1
    sortedset = sorted(cset.items(), key=lambda x:x[0])
    s = ""
    for k, v in sortedset:
        s += k + str(v)
    return s

sorted = [charcnt(v) for v in A]    

cnt = 0
for i1, s1 in enumerate(sorted[:-1]):
    for s2 in sorted[i1 + 1:]:
        if s1 == s2:
            cnt += 1 
print(cnt)


### FIXED CODE ###

import collections
import math

inp = int(input())
A = []
for a in range(inp):
    A.append(input())

def charcnt(s):
    cset = {}
    for c in s:
        if c in cset:
            cset[c] += 1
        else:
            cset[c] = 1
    sortedset = sorted(cset.items(), key=lambda x:x[0])
    s = ""
    for k, v in sortedset:
        s += k + str(v)
    return s

sorted = [charcnt(v) for v in A]    

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


counted = collections.Counter(sorted)
cnt = 0
for v in counted.values():
    if v > 1:
        cnt += cmb(v, 2)
print(int(cnt))
### BUGGY CODE ###

class SegmentTree:
  def __init__(self, size, default, op = min):
    self.size = 2**size.bit_length()
    self.dat = [default]*(self.size*2)
    self.op = op

  def update(self, i, x):
    i += self.size
    self.dat[i] = x
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

  def add(self, i, x):
    i += self.size
    self.dat[i] = self.op(self.dat[i], x)
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i], x)

  def get(self, a, b = None):
    if b is None:
      b = a + 1
    l, r = a + self.size, b + self.size
    res = None
    while l < r:
      if l & 1:
        if res is None:
          res = self.dat[l]
        else:
          res = self.op(res, self.dat[l])
        l += 1

      if r & 1:
        r -= 1
        if res is None:
          res = self.dat[r]
        else:
          res = self.op(res, self.dat[r])
      l >>= 1
      r >>= 1
    return res

N,M = map(int,input().split())
LRC = [list(map(int,input().split())) for _ in range(M)]
LRC.sort(key=lambda x:(x[0],x[1]))
#print(LRC)

INF = 10**18
dp = SegmentTree(N,INF,min)
dp.update(0,0)
#print(dp.get(0,1))

for l,r,c in LRC:
  p = dp.get(l-1,r-1)+c
  for i in range(l,r):
    if p < dp.get(i):
      dp.update(i,p)
print(dp.get(N-1) if dp.get(N-1) != INF else -1)


### FIXED CODE ###

class SegmentTree:
  def __init__(self, size, default, op = min):
    self.size = 2**size.bit_length()
    self.dat = [default]*(self.size*2)
    self.op = op

  def update(self, i, x):
    i += self.size
    self.dat[i] = x
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

  def add(self, i, x):
    i += self.size
    self.dat[i] = self.op(self.dat[i], x)
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i], x)

  def get(self, a, b = None):
    if b is None:
      b = a + 1
    l, r = a + self.size, b + self.size
    res = None
    while l < r:
      if l & 1:
        if res is None:
          res = self.dat[l]
        else:
          res = self.op(res, self.dat[l])
        l += 1

      if r & 1:
        r -= 1
        if res is None:
          res = self.dat[r]
        else:
          res = self.op(res, self.dat[r])
      l >>= 1
      r >>= 1
    return res

N,M = map(int,input().split())
LRC = [list(map(int,input().split())) for _ in range(M)]
LRC.sort(key=lambda x:(x[0],x[1]))
#print(LRC)

INF = 10**18
dp = SegmentTree(N,INF,min)
dp.update(0,0)
#print(dp.get(0,1))

for l,r,c in LRC:
  p = dp.get(l-1,r-1)+c
  # cf.https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/1109_nikkei2019-2-qual
  #for i in range(l,r):
  #  if p < dp.get(i):
  #    dp.update(i,p)
  if p < dp.get(r-1):
    dp.update(r-1,p)
print(dp.get(N-1) if dp.get(N-1) != INF else -1)
### BUGGY CODE ###

N,Q = list(map(int, input().split()))
S=list(str(input()))
ACs=[]
for i in range(len(S)-1):
    if S[i]=='A' and S[i+1]=='C':
        ACs.append(i)

for q in range(Q):
    l,r = list(map(lambda x:int(x)-1, input().split()))
    lr=list(range(l,r))
    print(len(set(lr)&set(ACs)))



### FIXED CODE ###

N, Q = list(map(int, input().split()))
S = list(str(input()))
questions = [tuple(map(int, input().split())) for _ in range(Q)]
ACs = [0] * N

for i in range(len(S)-1):
    if S[i] == 'A' and S[i + 1] == 'C':
        ACs[i + 1] = ACs[i] + 1
    else:
        ACs[i + 1] = ACs[i]

for q in questions:
    print(ACs[q[1]-1] - ACs[q[0]-1])
### BUGGY CODE ###

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

ans = functools.reduce(operator.mul, A)
    
if len(str(ans)) < 19:
  print(ans)
elif ans == 1000000000000000000:
  print(ans)
else:
  print(-1)

### FIXED CODE ###

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

def main(A):
  if 0 in A:
    print(0)
    return
  prod = 1
  for a in A:
    prod *= a
    if prod > 1000000000000000000:
      print(-1)
      return
  print(prod)
    
main(A)
### BUGGY CODE ###

n = int(input())
a = input().split(" ")
lista = [int(n) for n in a]
for i in range (1,n):
  print(lista.count(i))
print(0)

### FIXED CODE ###

n = int(input())
a = input().split(" ")
lista = [int(n) for n in a]
listb = [0]*n
for i in range (n-1):
  l = lista[i]
  listb[l-1] += 1
[print(i) for i in listb]
### BUGGY CODE ###

from itertools import product

X,Y,Z,K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

BC = [i+j for i,j in list(product(B,C))]
BC.sort(reverse=True)

ans = [i+j for i,j in list(product(BC[:min(3000, X*Y*Z)], A))]
ans.sort(reverse=True)

[print(ans[i]) for i in range(K)]


### FIXED CODE ###

from itertools import product

X,Y,Z,K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

BC = [i+j for i,j in list(product(B,C))]
BC.sort(reverse=True)

ans = [i+j for i,j in list(product(BC[:min(3000, X*Y*Z)], A))]
ans.sort(reverse=True)

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

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

ans = 1

for i in A_list:
    ans = ans * i


if ans > 10 ** 18:
    ans = -1

print(ans)

### FIXED CODE ###

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

ans = 1

for i in A_list:
    if i == 0:
        ans = 0

if ans != 0:
    for i in A_list:
        ans = ans * i
        if ans > 10 ** 18:
            ans = -1
            break

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

import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle

# from functools import reduce
# from math import ceil, floor, log10, log2, factorial

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

# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

def main():
    """"ここに今までのコード"""
    N, M = [int(x) for x in input().split()]
    S = [int(x) for x in input().split()]
    T = [int(x) for x in input().split()]

    DP = [[0] * (M + 1) for _ in range(N + 1)]
    DP[0] = [1] * (M + 1)
    for n in range(1, N + 1):
        DP[n][0] = DP[n - 1][0]
        for m in range(1, M + 1):
            DP[n][m] = DP[n][m - 1] + DP[n - 1][m] - DP[n - 1][m - 1]
            DP[n][m] %= MOD
            if S[n - 1] == T[m - 1]:
                DP[n][m] += DP[n - 1][m - 1]
                DP[n][m] %= MOD
    print(DP[n][m])


if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle

# from functools import reduce
# from math import ceil, floor, log10, log2, factorial

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

# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

def main():
    """"ここに今までのコード"""
    N, M = [int(x) for x in input().split()]
    S = [int(x) for x in input().split()]
    T = [int(x) for x in input().split()]

    DP = [[0] * (M + 1) for _ in range(N + 1)]
    DP[0] = [1] * (M + 1)
    for n in range(1, N + 1):
        DP[n][0] = DP[n - 1][0]
        for m in range(1, M + 1):
            DP[n][m] = DP[n][m - 1] + DP[n - 1][m] - DP[n - 1][m - 1]
            DP[n][m] %= MOD
            if S[n - 1] == T[m - 1]:
                DP[n][m] += DP[n - 1][m - 1]
                DP[n][m] %= MOD
    print(DP[n][m])


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

import itertools

n = int(input())
a_list = list(map(int, input().split()))
max = 0
mod = 10 ** 9 + 7

for a in itertools.combinations(a_list, 2):
    b, c = a
    max += b * c

print(max % mod)

### FIXED CODE ###

mod = 10 ** 9 + 7
n = int(input())
a_list = list(map(int, input().split()))
result = 0
a_sum = sum(a_list)
for i in a_list:
    a_sum -= i
    result += i * a_sum
print(result % mod)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def z_algo(S):
    N = len(S)
    LCPs = [0]*N
    i = 1 ## iから何文字一致してるか調べる
    j = 0
    LCPs[0] = N
    while i < N:
        while i+j < N and S[j] == S[i+j]:
            j += 1
        if j == 0:
            i += 1
            continue
        LCPs[i] = j
        k = 1
        while k+i < N and k+LCPs[k] < j:
            LCPs[i+k] = LCPs[k]
            k += 1
        i += k
        j -= k
    return LCPs

def solve(N: int, S: str):
    answer = 0
    for i in range(N):
        LCP = z_algo(S[i:])
        for j in range(len(LCP)):
            # jの長さまでなら重ならない
            a = min(j,LCP[j])
            answer = max(answer,a)
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int, S: str):

    a = ""
    ans = 0
    for i in range(N):
        a += S[i]
        while(len(a) > 0):
            if a in S[i+1:]:    
                ans = max(ans,len(a))
                break
            else:               
                a = a[1:]
    print(ans)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

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

import operator as o
import functools as f
n,*a=map(int,open(0).read().split())
#print(f.reduce(o.mul,a))
x=f.reduce(o.mul,a)
count=0
while True:
    if x%2==0:
        x=x//2
        count+=1
    else:
        break
print(count)

### FIXED CODE ###

n,*a=map(int,open(0).read().split())
#print(f.reduce(o.mul,a))
a=[s for s in a if s%2==0]
if len(a)==0:
    print(0)
    exit()
count=0

for x in a:
    while True:
        if x%2==0:
            x=x//2
            count+=1
        else:
            break
print(count)
### BUGGY CODE ###

import sys
#import numpy as np
import bisect
sys.setrecursionlimit(10 ** 7)

N, Q = map(int, input().split())
STX = []
for _ in range(N):
    s, t, x = map(int, input().split())
    STX.append((s, t, x))

PEOPLE = []
for _ in range(Q):
    d = int(input())
    PEOPLE.append(d)

ans = [str(-1)] * Q

STX.sort(key=lambda x: -x[2])

for s, t, x in STX:
    #print("s,t,x", s, t, x)
    #i = np.searchsorted(PEOPLE, s - x)
    #j = np.searchsorted(PEOPLE, t - x)
    i = bisect.bisect_left(PEOPLE, s - x)
    j = bisect.bisect_left(PEOPLE, t - x)
    #print("i,j", i, j)

    ans[i:j] = [str(x)] * (j-i)

    # for k in range(i, j):
    # if ans[k] == '-1':
    #ans[k] = str(x)

    # print(ans)

print("\n".join(ans))


### FIXED CODE ###

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from collections import defaultdict

N,Q = map(int,input().split())
task = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  task.append((t-x,0,x)) # xで止まらなくなる
  task.append((s-x,1,x)) # xで止まる

for i in range(Q):
  d = int(input())
  task.append((d,2,i)) # 止まる位置を答える
answer = [-1]*Q

task.sort()

# 引っかかってる場所の管理
se = set()
se_hp = [] # heapで最小値を先頭に保つ

# 小さい時刻から順に見ていく
for a,b,c in task:
  if not b: # b == 0
    se.remove(c)
  elif b&1: # b == 1
    se.add(c)
    heappush(se_hp,c)
  else: # b == 2
    while se_hp and se_hp[0] not in se:
      heappop(se_hp)
    answer[c] = se_hp[0] if se_hp else -1

print('\n'.join(map(str,answer)))
### BUGGY CODE ###

N = int(input())
num_line = [int(input()) for _ in range(N)]
for i in range(N):
    save_num = num_line[i]
    num_line.pop(i)
    print(max(num_line))
    num_line.insert(i, save_num)

### FIXED CODE ###

N = int(input())
num_line = [int(input()) for _ in range(N)]
sort_line = sorted(num_line)
for i in num_line:
    if i == sort_line[N-1]:
        print(sort_line[N-2])
    else:
        print(sort_line[N-1])
### BUGGY CODE ###

N, X, *A = map(int, open(0).read().split())


class SegmentTree:
    inf = 2 ** 31 - 1
    
    def __init__(self, n):
        """0-indexed."""
        x = 1
        while x < n:
            x *= 2

        self.n = x
        self.dat = [self.inf] * (2 * x - 1)
        
    def update(self, k, v):
        """Update dat[k] to v."""
        k += self.n - 1
        self.dat[k] = v
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])
            
    def query(self, a, b, k=0, l=0, r=0):
        """Returns min in [a, b)."""
        if l >= r:
            r = self.n
            
        if b <= l or r <= a:
            return self.inf
        
        if a <= l and r <= b:
            return self.dat[k]
        
        vl = self.query(a, b, k * 2 + 1, l, (l + r) // 2)
        vr = self.query(a, b, k * 2 + 2, (l + r) // 2, r)
        return min(vl, vr)


st = SegmentTree(N)
for i, v in enumerate(A):
    st.update(i, v)

ans = 10 ** 10
for k in range(N):
    b = [0] * N
    for i in range(N):
        if i - k < 0:
            b[i] = min(st.query(0, i + 1), st.query(N - (k - i), N))
        else:
            b[i] = st.query(i - k, i + 1)
    ans = min(ans, k * X + sum(b))
print(ans)


### FIXED CODE ###

N, X, *A = map(int, open(0).read().split())

ans = sum(A)
b = A[:]
for k in range(1, N):
    for i in range(N):
        b[i] = min(b[i], A[i - k])
    ans = min(ans, k * X + sum(b))
print(ans)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(len(l) - 2):
    for j in range(i + 1, len(l) - 1):
        for k in range(j + 1, len(l)):
            if l[i] + l[j] > l[k]:
                ans += 1
            else:
                break
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(len(l) - 2):
    for j in range(i + 1, len(l) - 1):
        ans += bisect.bisect_left(l, l[i] + l[j]) - j - 1
print(ans)
### BUGGY CODE ###

input_num = int(input())

minimam = input_num
for i in range(1,input_num+1):
    q, mod = divmod(input_num, i)
    distance = q + i -2
    if mod == 0 and minimam > distance:
        minimam = distance
print(minimam)


### FIXED CODE ###

num = int(input())
minimam = 10**12
for i in range(1,10**6+1):
    q, mod = divmod(num, i)
    distance = q + i -2
    if mod == 0 and minimam > distance:
        minimam = distance
print(minimam)
### BUGGY CODE ###

import math
import queue
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def printQueue(q):
	r=q
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)

s = readChar()
q = readInt()
qa = []
booh = 0
for i in range(q):
	x = input()
	if x=="1":
		qa.append([1,0,0])
	else:
		x = x.split()
		qa.append([int(x[0]),int(x[1]),x[2]])

def hanten():
	global booh
	booh = (booh+1)%2

def t1(s):
	return s[::-1]

def t2(f,c,s):
	if f==1:
		return c+s
	else:
		return s+c

for a in qa:
	if a[0]==1:
		hanten()
	else:
		s=t2((a[1]+booh)%2,a[2],s)
if booh==1:
	s = t1(s)

print(s)

### FIXED CODE ###

import math
import queue
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def printQueue(q):
	r=q
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)

s = readChar()
q = readInt()
qa = []
booh = 0
for i in range(q):
	x = input()
	if x=="1":
		qa.append([1,0,0])
	else:
		x = x.split()
		qa.append([int(x[0]),int(x[1]),x[2]])

def t1(s):
	return s[::-1]

def t2(f,c,s):
	if f==1:
		return c+s
	else:
		return s+c

fi=""
la=""
for a in qa:
	if a[0]==1:
		booh = (booh+1)%2
	else:
		if (a[1]+booh)%2==1:
			fi=a[2]+fi
		else:
			la+=a[2]

s = fi+s+la
if booh==1:
	s = t1(s)

print(s)