AT_abc158_d [ABC158D] String Formation

[problemUrl]: https://atcoder.jp/contests/abc158/tasks/abc158_d 高橋君は、英小文字から成る文字列 $ 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 $ は、以下の $ 2 $ つのいずれかである。 > $ 1 $ $ T_i\ =\ 1 $ として操作を行うことを表す。 > $ 2 $ $ F_i $ $ C_i $ $ T_i\ =\ 2 $ として操作を行うことを表す。

手順の後に最終的にできる文字列を出力せよ。

### 制約 - $ 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 $ は英小文字である ### Sample Explanation 1 $ Q\ =\ 4 $ 回の操作を行います。初め $ S $ は `a` です。 - 操作 $ 1 $ : $ S $ の先頭に `p` を追加する。$ S $ は `pa` となる。 - 操作 $ 2 $ : $ S $ の前後を反転する。$ S $ は `ap` となる。 - 操作 $ 3 $ : $ S $ の末尾に `c` を追加する。$ S $ は `apc` となる。 - 操作 $ 4 $ : $ S $ の前後を反転する。$ S $ は `cpa` となる。 よって最終的にできる文字列は `cpa` となります。 ### Sample Explanation 2 $ Q\ =\ 6 $ 回の操作を行います。初め $ S $ は `a` です。 - 操作 $ 1 $ : $ S $ は `aa` となる。 - 操作 $ 2 $ : $ S $ は `baa` となる。 - 操作 $ 3 $ : $ S $ は `aab` となる。 - 操作 $ 4 $ : $ S $ は `aabc` となる。 - 操作 $ 5 $ : $ S $ は `cbaa` となる。 - 操作 $ 6 $ : $ S $ は `aabc` となる。 よって最終的にできる文字列は `aabc` となります。