AT_agc044_c [AGC044C] Strange Dance

[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/A

N/A

### 制約 - $ 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 $ に立っています。