AT_abc158_d [ABC158D] String Formation

题目描述

高桥君有一个由小写英文字母组成的字符串 $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$
$\vdots$
$Query_Q$

第 $3$ 行到第 $Q+2$ 行的 $Query_i$，有以下两种形式之一：

$1$

表示进行 $T_i = 1$ 的操作。

$2\ F_i\ C_i$

表示进行 $T_i = 2$ 的操作。

输出格式

请输出经过所有操作后最终得到的字符串。

输入输出样例 #1

输入 #1

a
4
2 1 p
1
2 2 c
1

输出 #1

cpa

输入输出样例 #2

输入 #2

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

输出 #2

aabc

输入输出样例 #3

输入 #3

y
1
2 1 x

输出 #3

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

样例解释 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。

由 ChatGPT 4.1 翻译