String Formation

题目描述

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$：在字符串 $S$ 的开头添加 $C_i$。 如果 $F_i = 2$：在字符串 $S$ 的末尾添加 $C_i$。

请帮助 Takahashi 找到该过程中得到的最终字符串。

输入格式

输入从标准输入按以下格式给出： $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

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

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$ 为小写英文字母。将会有 $Q = 4$ 次操作。初始时，$S$ 为 $a$。

操作 1：在 $S$ 的开头添加 $p$。$S$ 变为 $pa$。

操作 2：将 $S$ 反转。$S$ 变为 $ap$。

操作 3：在 $S$ 的末尾添加 $c$。$S$ 变为 $apc$。

操作 4：将 $S$ 反转。$S$ 变为 $cpa$。

因此，结果字符串是 $cpa$。
将会有 $Q = 6$ 次操作。初始时，$S$ 为 $a$。

操作 1：$S$ 变为 $aa$。

操作 2：$S$ 变为 $baa$。

操作 3：$S$ 变为 $aab$。

操作 4：$S$ 变为 $aabc$。

操作 5：$S$ 变为 $cbaa$。

操作 6：$S$ 变为 $aabc$。

因此，结果字符串是 $aabc$。

标签: AtCoder|abc158D

来源

AtCoder|abc158D