题目描述

小高有一个由小写英文字母组成的字符串 $S$。从这个字符串开始，他将按照以下过程生成一个新的字符串。该过程包含 $Q$ 个操作。在第 $i$ 个操作中 $( 1 \leq i \leq Q )$，会提供一个整数 $T_{i}$，具体含义如下：

• 如果 $T_{i} = 1$：反转字符串 $S$。
• 如果 $T_{i} = 2$：额外提供一个整数 $F_{i}$ 和一个小写英文字母 $C_{i}$。
• 如果 $F_{i} = 1$：在字符串 $S$ 的开头添加 $C_{i}$。
• 如果 $F_{i} = 2$：在字符串 $S$ 的末尾添加 $C_{i}$。

请帮助小高找出这个过程最终得到的字符串。

输入格式

输入按以下格式从标准输入给出：

$S$

$Q$

$Query_1$

$\vdots$

$Query_Q$

在第3行到第$(Q+2)$行，$Query_i$ 是以下之一：

$1$ 表示 $T_i = 1$，
以及：$2$ $F_i$ $C_i$ 表示 $T_i = 2$。

输出格式

输出最终得到的字符串。

样例

a
4
2 1 p
1
2 2 c
1

cpa

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

aabc

y
1
2 1 x

xy

样例解释

【 样例说明1】
将有 $Q = 4$ 个操作。初始时，$S$ 是 a。

• 操作 $1$：在 $S$ 的开头添加 p。$S$ 变成 pa。
• 操作 $2$：反转 $S$。$S$ 变成 ap。
• 操作 $3$：在 $S$ 的末尾添加 c。$S$ 变成 apc。
• 操作 $4$：反转 $S$。$S$ 变成 cpa。

因此，最终得到的字符串是 cpa。
【样例说明2】
将有 $Q = 6$ 个操作。初始时，$S$ 是 a。

• 操作 $1$：$S$ 变成 aa。
• 操作 $2$：$S$ 变成 baa。
• 操作 $3$：$S$ 变成 aab。
• 操作 $4$：$S$ 变成 aabc。
• 操作 $5$：$S$ 变成 cbaa。
• 操作 $6$：$S$ 变成 aabc。

因此，最终得到的字符串是 aabc。
【 数据范围】

• $1 \leq | S | \leq 10^{5}$
• $1 \leq Q \leq 2 \times 10^{5}$

来源

• AtCoder ABC158D