配点 : $1000$ 点

問題文

$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}$ を求めてください。

制約

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

2 0 1

最初の曲が流れる前に位置 $i$ に立っていた人を人 $i$ とします。

1. サルサが一度目に流れたあと、人 $0, 1, 2$ はそれぞれ位置 $0, 2, 1$ に立っています。
2. ルンバが流れたあと、人 $0, 1, 2$ はそれぞれ位置 $1, 0, 2$ に立っています。
3. サルサが二度目に流れたあと、人 $0, 1, 2$ はそれぞれ位置 $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