分数: 1000 点
问题陈述
有 3^N 人们围成圈跳舞。 我们用 0,1,\dots, 3^{N}-1 圆中的位置,从任意位置开始,顺时针旋转。最初,圆圈中的每个位置都由一个人占据。
人们将跳两种歌曲:萨尔萨舞和伦巴舞。
- 当演奏萨尔萨舞曲时,处于该位置的人 i 转到位置 j,其中 j 是替换所有数字得到的数字 1 与 2 和所有数字 2 与 1 阅读时 i 在基地 3 (例如,处于该位置的人 46 转到位置 65).
- 当演奏伦巴时,在该位置的人 i 移动到位置 i+1 (带有标识 3^N = 0).
给你一个字符串 T=T_1T_2\cdots T_{|T|} 这样 T_i=S 如果 i-th 歌曲是萨尔萨舞曲并且 T_i=R 如果是伦巴舞。
所有歌曲播放完后,最初就位的人 i 就位 P_i。
计算数组 P_0,P_1,\dots, P_{3^N-1}.
约束
- 1 \le N \le 12
- 1 \le |T| \le 200,000
- T 仅包含字符
S和R.
输入
输入由标准输入按以下格式给出:
N T
输出
您应该在标准输出上打印:
P_0 P_1 \cdots P_{3^N-1}
示例输入 1
1 SRS
示例输出 1
2 0 1
在播放任何歌曲之前,位置为: 0, 1, 2.
当我们说“人 i”,我们的意思是“最初处于位置的人 i".
- 在第一个萨尔萨舞之后,位置是: 0, 2, 1.
- 伦巴舞结束后,位置是: 1, 0, 2 (所以,人 0 就位 1, 人 1 就位 0 和人 2 就位 2).
- 第二个萨尔萨舞之后,位置是 2, 0, 1 (所以,人 0 就位 2, 人 1 就位 0 和人 2 就位 1).
示例输入 2
2 RRSRSSSSR
示例输出 2
3 8 1 0 5 7 6 2 4
示例输入 3
3 SRSRRSRRRSRRRR
示例输出 3
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