题目描述

有 $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

输入

1
SRS

输出

2 0 1

样例 2

输入

2
RRSRSSSSR

输出

3 8 1 0 5 7 6 2 4

样例 3

输入

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 组成。

样例解释 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 翻译