题目描述

Takahashi 有一个由小写英文字母组成的字符串 $S$。

从这个字符串开始，按照以下过程生成一个新的字符串。

这个过程由 $Q$ 次操作组成。在第 $i$ 次操作 $(1 \leq i \leq Q)$ 中，提供一个整数 $T_i$，具体含义如下：

• 如果 $T_i = 1$：反转字符串 $S$。

• 如果 $T_i = 2$：额外提供一个整数 $F_i$ 和一个小写英文字母 $C_i$。

  • 如果 $F_i = 1$：将 $C_i$ 添加到字符串 $S$ 的开头。
  • 如果 $F_i = 2$：将 $C_i$ 添加到字符串 $S$ 的末尾。

帮助 Takahashi 找到经过这个过程后得到的最终字符串。

约束条件

• $1 \leq |S| \leq 10^5$
• $S$ 由小写英文字母组成。
• $1 \leq Q \leq 2 \times 10^5$
• $T_i = 1$ 或 $2$。
• 如果提供了，$F_i = 1$ 或 $2$。
• 如果提供了，$C_i$ 是小写英文字母。

输入

输入数据从标准输入读取，以以下格式给出：

$S$ $Q$ $Query_1$ $:$ $Query_Q$

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

$1$

表示 $T_i = 1$，以及：

$2$ $F_i$ $C_i$

表示 $T_i = 2$。

输出

打印结果字符串。

示例输入 1

a
4
2 1 p
1
2 2 c
1

示例输出 1

cpa

将有 $Q = 4$ 次操作。起初，$S$ 是 a。

• 第 1 次操作：将 p 添加到 $S$ 的开头。$S$ 变成 pa。

• 第 2 次操作：反转 $S$。$S$ 变成 ap。

• 第 3 次操作：将 c 添加到 $S$ 的末尾。$S$ 变成 apc。

• 第 4 次操作：反转 $S$。$S$ 变成 cpa。

因此，最终得到的字符串是 cpa。

示例输入 2

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

示例输出 2

aabc

将有 $Q = 6$ 次操作。起初，$S$ 是 a。

• 第 1 次操作：$S$ 变成 aa。

• 第 2 次操作：$S$ 变成 baa。

• 第 3 次操作：$S$ 变成 aab。

• 第 4 次操作：$S$ 变成 aabc。

• 第 5 次操作：$S$ 变成 cbaa。

• 第 6 次操作：$S$ 变成 aabc。

因此，最终得到的字符串是 aabc。

示例输入 3

y
1
2 1 x

示例输出 3

xy