P15036 「chaynOI R2 T1」构造字符串

本题字符集 $\Sigma = \{\text{a},\text{b},\text{c}\}$，即默认所有字符为 $\text{a},\text{b},\text{c}$ 中的一个。 flow 有一个字符串 $T$ 和一个初始为空的字符串 $S$，其中 $|T|=n$，为了方便起见，保证 $T_1=\text{a},T_2=\text{b}$。 flow 有两种操作： 1. 向 $S$ 末尾添加一个字符 $x$，需要满足 $\nexists 1\le i\le |S|,S_i=x$。 2. 选择一个位置 $i$ 满足 $2\le i\le |S|$ 且 $S_i\ne S_{i-1}$，将 $S_i$ 修改为 $x$ 满足 $x\not\in\{S_{i-1},S_i\}$（可以注意到，$x$ 唯一）。 请你帮助 flow 在至多 $10^6$ 次操作后将 $S$ 修改为与 $T$ 相同，输出任意一个合法的解均可。 数据保证有解。

一行一个字符串 $T$。

第一行一个正整数 $k$，表示你的操作次数，需要满足 $1\le k\le 10^6$。 接下来 $k$ 行，每行为 `1 x` 或 `2 i`，表示操作 $1$ 加入字符 $x$ 或操作 $2$ 修改位置 $i$。

### 样例 1 解释 $S$ 的变换过程为 $\text{[]}\to\text{[a]}\to\text{[ac]}\to\text{[acb]}\to\text{[aca]}\to\text{[acab]}\to\text{[abab]}\to\text{[abcb]}\to\text{[abca]}$。 ### 数据范围 **本题采用捆绑测试。** 对于 $100\%$ 的数据，$3\le n\le222222$，$T_i\in \Sigma$。 + Subtask1(10pts)：$n\le 5$。 + Subtask2(10pts)：$n\le 1000$。 + Subtask3(10pts)：$\forall 3\le i\le n$，$T_i=\text{c}$。 + Subtask4(20pts)：$n\le 2\times10^5$。 + Subtask5(50pts)：无特殊限制。