字符串构造

题目描述

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

他从这个 $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$
$:$
$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

共进行 $Q = 4$ 次操作。最初 $S$ 为 a。

• 操作 $1$:在 $S$ 的开头追加 p,$S$ 变为 pa。
• 操作 $2$:将 $S$ 前后反转,$S$ 变为 ap。
• 操作 $3$:在 $S$ 的末尾追加 c,$S$ 变为 apc。
• 操作 $4$:将 $S$ 前后反转,$S$ 变为 cpa。

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

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

aabc

共进行 $Q = 6$ 次操作。最初 $S$ 为 a。

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

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

y
1
2 1 x

xy

数据范围

• $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$ 是小写英文字母