atcoder#AGC044C. [AGC044C] Strange Dance

[AGC044C] Strange Dance

Score : 10001000 points

Problem Statement

There are 3N3^N people dancing in circle. We denote with 0,1,,3N10,1,\dots, 3^{N}-1 the positions in the circle, starting from an arbitrary position and going around clockwise. Initially each position in the circle is occupied by one person.

The people are going to dance on two kinds of songs: salsa and rumba.

  • When a salsa is played, the person in position ii goes to position jj, where jj is the number obtained replacing all digits 11 with 22 and all digits 22 with 11 when reading ii in base 33 (e.g., the person in position 4646 goes to position 6565).
  • When a rumba is played, the person in position ii moves to position i+1i+1 (with the identification 3N=03^N = 0).

You are given a string T=T1T2TTT=T_1T_2\cdots T_{|T|} such that Ti=T_i=S if the ii-th song is a salsa and Ti=T_i=R if it is a rumba. After all the songs have been played, the person that initially was in position ii is in position PiP_i. Compute the array P0,P1,,P3N1P_0,P_1,\dots, P_{3^N-1}.

Constraints

  • 1N121 \le N \le 12
  • 1T200,0001 \le |T| \le 200,000
  • TT contains only the characters S and R.

Input

Input is given from Standard Input in the following format:

NN

TT

Output

You should print on Standard Output:

P0P_0 P1P_1 \cdots P3N1P_{3^N-1}

1
SRS
2 0 1

Before any song is played, the positions are: 00, 11, 22.

When we say "person ii", we mean "the person that was initially in position ii".

  1. After the first salsa, the positions are: 00, 22, 11.
  2. After the rumba, the positions are: 11, 00, 22 (so, person 00 is in position 11, person 11 is in position 00 and person 22 is in position 22).
  3. After the second salsa, the positions are 22, 00, 11 (so, person 00 is in position 22, person 11 is in position 00 and person 22 is in position 11).
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