AT_agc044_c [AGC044C] Strange Dance

有 $3^N$ 个人围成一圈跳舞。我们从某个位置开始，顺时针依次给圈上的每个人编号为 $0,1,\dots,3^N-1$。一开始，每个编号的位置上都站着一个人。 接下来会播放两种音乐，分别是“萨尔萨”和“伦巴”，人们会根据音乐跳舞。 - 当播放萨尔萨时，编号为 $i$ 的人会移动到编号为 $j$ 的位置。$j$ 的获得方式是：将 $i$ 用三进制表示，把每一位上的 $1$ 替换成 $2$，每一位上的 $2$ 替换成 $1$，然后将结果转回十进制。例如，编号 $46$ 的人会移动到编号 $65$ 的位置。 - 当播放伦巴时，编号为 $i$ 的人会移动到编号为 $i+1$ 的位置。如果 $i+1=3^N$，则回到编号 $0$ 的位置。 给定一个字符串 $T=T_1T_2\dots T_{|T|}$，其中 $T_i=$`S` 表示第 $i$ 首播放的是萨尔萨，$T_i=$`R` 表示第 $i$ 首播放的是伦巴。假设一开始编号为 $i$ 的人是第 $i$ 个人。所有音乐播放结束后，第 $i$ 个人最终站在编号 $P_i$ 的位置。请输出序列 $P_0,P_1,\dots,P_{3^N-1}$。

输入从标准输入读入，格式如下： > $N$ $T$

请按以下格式输出到标准输出： > $P_0$ $P_1$ $\cdots$ $P_{3^N-1}$

### 限制条件 - $1 \le N \le 12$ - $1 \le |T| \le 200,\!000$ - $T$ 由 `S` 和 `R` 组成。 ### 样例解释 1 在第一首音乐播放前，编号为 $i$ 的人是第 $i$ 个人。 1. 播放第一次萨尔萨后，编号 $0,1,2$ 的人分别站在位置 $0,2,1$。 2. 播放伦巴后，编号 $0,1,2$ 的人分别站在位置 $1,0,2$。 3. 播放第二次萨尔萨后，编号 $0,1,2$ 的人分别站在位置 $2,0,1$。 由 ChatGPT 4.1 翻译