题目描述

$3^N$ 人の人が輪になって踊っています。 輪の中の人がいる位置に、$0,1,\dots,\ 3^{N}-1$ の番号を、適当な場所から始めて時計回りに付けます。はじめ、これらの位置それぞれに一人の人が立っています。

これから二種類の曲、サルサとルンバが流れ、人々はそれに合わせて踊ります。

• サルサが流れたら、位置 $i$ にいる人は以下で述べるような位置 $j$ に移動します。$j$ は、$i$ を $3$ 進法で表記し、$1$ という桁をそれぞれ $2$ に、$2$ という桁をそれぞれ $1$ に置き換えて得られる数です (例えば、位置 $46$ の人は位置 $65$ に移動します)。
• ルンバが流れたら、位置 $i$ にいる人は位置 $i+1$ に移動します。ここで、位置 $3^N$ は位置 $0$ とみなします。

文字列 $T=T_1T_2\cdots\ T_{|T|}$ が与えられます。これは、$T_i=$S なら $i$ 番目に流れる曲がサルサであり、$T_i=$R ならルンバであることを表します。 はじめ位置 $i$ に立っていた人が、すべての曲が流れたあとに位置 $P_i$ に立っているとします。 列 $P_0,P_1,\dots,\ P_{3^N-1}$ を求めてください。

输入格式

入力は標準入力から以下の形式で与えられる。

$N$ $T$

输出格式

以下の形式で標準出力に出力せよ。

$P_0$ $P_1$ $\cdots$ $P_{3^N-1}$

题目大意

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

2 0 1

2
RRSRSSSSR

3 8 1 0 5 7 6 2 4

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 からなる。

Sample Explanation 1

最初の曲が流れる前に位置 $i$ に立っていた人を人 $i$ とします。 1. サルサが一度目に流れたあと、人 $0,\ 1,\ 2$ はそれぞれ位置 $0,\ 2,\ 1$ に立っています。 2. ルンバが流れたあと、人 $0,\ 1,\ 2$ はそれぞれ位置 $1,\ 0,\ 2$ に立っています。 3. サルサが二度目に流れたあと、人 $0,\ 1,\ 2$ はそれぞれ位置 $2,\ 0,\ 1$ に立っています。