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 翻译