题目描述

有 $3^N$ 个人在圆环上跳舞。我们用 $0,1,\\dots, 3^{N}-1$ 来表示圆环中的位置，从任意一个位置开始，顺时针方向绕圈。初始时，圆环上的每个位置都有一个人。

这些人将跳两种舞蹈：salsa 和 rumba。

• 当播放 salsa 时，位于位置 $i$ 的人移动到位置 $j$，其中 $j$ 是将 $i$ 按照三进制读法，将所有的数字 $1$ 替换为 $2$，将所有的数字 $2$ 替换为 $1$ 得到的数（例如，位于位置 $46$ 的人移动到位置 $65$）。
• 当播放 rumba 时，位于位置 $i$ 的人移动到位置 $i+1$（如果 $i+1 = 3^N$，则位置 $3^N$ 等于位置 $0$）。

给定一个字符串 $T=T_1T_2\\cdots T_{|T|}$，其中 $T_i=$S 表示第 $i$ 首歌曲是 salsa，$T_i=$R 表示是 rumba。在所有歌曲播放完毕后，初始时位于位置 $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$ 的人”。

1. 在第一首 salsa 播放后，位置是：$0$，$2$，$1$。
2. 在 rumba 播放后，位置是：$1$，$0$，$2$（因此，第 $0$ 个人位于位置 $1$，第 $1$ 个人位于位置 $0$，第 $2$ 个人位于位置 $2$）。
3. 在第二首 salsa 播放后，位置是：$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