p02756 AtCoder Beginner Contest 158 - String Formation
Takahashi has a string S consisting of lowercase English letters.

Starting with this string, he will produce a new one in the procedure given as follows.

The procedure consists of Q operations. In Operation i (1 \leq i \leq Q), an integer T_i is provided, which means the following:

* If T_i = 1: reverse the string S.

* If T_i = 2: An integer F_i and a lowercase English letter C_i are additionally provided.

* If F_i = 1 : Add C_i to the beginning of the string S.
* If F_i = 2 : Add C_i to the end of the string S.



Help Takahashi by finding the final string that results from the procedure.

Constraints

* 1 \leq |S| \leq 10^5
* S consists of lowercase English letters.
* 1 \leq Q \leq 2 \times 10^5
* T_i = 1 or 2.
* F_i = 1 or 2, if provided.
* C_i is a lowercase English letter, if provided.

Input

Input is given from Standard Input in the following format:


S
Q
Query_1
:
Query_Q


In the 3-rd through the (Q+2)-th lines, Query_i is one of the following:


1


which means T_i = 1, and:


2 F_i C_i


which means T_i = 2.

Output

Print the resulting string.

Examples

Input

a
4
2 1 p
1
2 2 c
1


Output

cpa


Input

a
6
2 2 a
2 1 b
1
2 2 c
1
1


Output

aabc


Input

y
1
2 1 x


Output

xy
```python
s = input()
q = int(input())
t = 0
f = -1
x = ["",""]
for i in range(q):
    que = input().split()
    if que[0] == "1":
        t += 1
    else:
        x[(int(que[1])-1+t)%2] += que[2]

s = x[0][::-1] + s + x[1]
if t%2 == 1:
    s = s[::-1]

print(s)

```