[AGC044C] Strange Dance

有 $3^n$ 个人在绕圈圈跳舞。我们从任意一个人开始，给这些人环绕标号，记为 $0,1,\dots,3^n-1$。 现在有两种舞 ： - Salasa 舞。第 $i$ 个人走向第 $j$ 个位置当且仅当他们的三进制表示，$1$ 对应 $2$，$2$ 对应 $1$。比如，46 可以走向 65，当然 65 也走向 46。 - Rumba 舞。所有人走向编号加 $1$ 的位置。如果等于 $3^n-1$，去 $0$ . 现在给你一个 T 序列表示以上两种舞。请问最后每个人站在哪里？ $n \le 12$ , $|T| \le 2 \times 10^5$。

[problemUrl]: https://atcoder.jp/contests/agc044/tasks/agc044_c $ 3^N $ 人の人が輪になって踊っています。 輪の中の人がいる位置に、$ 0,1,\dots,\ 3^{N}-1 $ の番号を、適当な場所から始めて時計回りに付けます。はじめ、これらの位置それぞれに一人の人が立っています。 これから二種類の曲、サルサとルンバが流れ、人々はそれに合わせて踊ります。 - サルサが流れたら、位置 $ i $ にいる人は以下で述べるような位置 $ j $ に移動します。$ j $ は、$ i $ を $ 3 $ 進法で表記し、$ 1 $ という桁をそれぞれ $ 2 $ に、$ 2 $ という桁をそれぞれ $ 1 $ に置き換えて得られる数です (例えば、位置 $ 46 $ の人は位置 $ 65 $ に移動します)。 - ルンバが流れたら、位置 $ i $ にいる人は位置 $ i+1 $ に移動します。ここで、位置 $ 3^N $ は位置 $ 0 $ とみなします。 文字列 $ T=T_1T_2\cdots\ T_{|T|} $ が与えられます。これは、$ T_i= $`S` なら $ i $ 番目に流れる曲がサルサであり、$ T_i= $`R` ならルンバであることを表します。 はじめ位置 $ i $ に立っていた人が、すべての曲が流れたあとに位置 $ P_i $ に立っているとします。 列 $ P_0,P_1,\dots,\ P_{3^N-1} $ を求めてください。

入力は標準入力から以下の形式で与えられる。 > $ N $ $ T $

以下の形式で標準出力に出力せよ。 > $ P_0 $ $ P_1 $ $ \cdots $ $ P_{3^N-1} $

1
SRS

2 0 1

2
RRSRSSSSR

3 8 1 0 5 7 6 2 4

3
SRSRRSRRRSRRRR

23 9 22 8 3 7 20 24 19 5 18 4 17 12 16 2 6 1 14 0 13 26 21 25 11 15 10

### 制約 - $ 1\ \le\ N\ \le\ 12 $ - $ 1\ \le\ |T|\ \le\ 200,000 $ - $ T $ は `S`、`R` からなる。 ### Sample Explanation 1 最初の曲が流れる前に位置 $ i $ に立っていた人を人 $ i $ とします。 1. サルサが一度目に流れたあと、人 $ 0,\ 1,\ 2 $ はそれぞれ位置 $ 0,\ 2,\ 1 $ に立っています。 2. ルンバが流れたあと、人 $ 0,\ 1,\ 2 $ はそれぞれ位置 $ 1,\ 0,\ 2 $ に立っています。 3. サルサが二度目に流れたあと、人 $ 0,\ 1,\ 2 $ はそれぞれ位置 $ 2,\ 0,\ 1 $ に立っています。