题面翻译

有 $3^n$ 个人在绕圈圈跳舞。我们从任意一个人开始，给这些人环绕标号，记为 $0,1,\dots,3^n-1$。

现在有两种舞 ：

• Salasa 舞。第 $i$ 个人走向第 $j$ 个位置当且仅当他们的三进制表示，$1$ 对应 $2$，$2$ 对应 $1$。比如，46 可以走向 65，当然 65 也走向 46。
• Rumba 舞。所有人走向编号加 $1$ 的位置。如果等于 $3^n-1$，去 $0$ .

现在给你一个 T 序列表示以上两种舞。请问最后每个人站在哪里？

$n \le 12$ , $|T| \le 2 \times 10^5$。

样例 #1

样例输入 #1

1
SRS

样例输出 #1

2 0 1

样例 #2

样例输入 #2

2
RRSRSSSSR

样例输出 #2

3 8 1 0 5 7 6 2 4

样例 #3

样例输入 #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

提示

制約

• $1\ \le\ N\ \le\ 12$
• $1\ \le\ |T|\ \le\ 200,000$