La festivitatea de deschidere a ONI Ploieşti, Gigel, mare amator de probleme de logică a observat că primul rând din sală este format din 2*N+2 scaune, numerotate de la stânga la dreapta de la 1 la 2*N+2. Pe acest rând s-au aşezat, într-o ordine oarecare, N băieţi şi N fete, cele două scaune rămase libere fiind alăturate.
Imediat Gigel inventează o problemă. Să considerăm că singura mutare posibilă este ca doi elevi care stau pe scaune alăturate să se ridice şi să se aşeze (în aceeaşi ordine) pe cele două locuri libere.
Problema constă în determinarea unei secvenţe de mutări după executarea cărora toate fetele să fie grupate în stânga rândului, toţi băieţii să fie grupaţi în dreapta, iar cele două locuri libere să separe fetele de băieţi.
Cerinţă
Cunoscându-se valoarea N, precum şi aranjarea iniţială a elevilor, să se determine o secvenţă de mutări care să conducă în final la aranjarea descrisă în enunţul problemei.
Date de intrare
Fişierul de intrare aranjare.in conţine pe prima linie numărul natural N. Linia a doua a fişierului de intrare conţine un şir de 2*N+2 caractere (N caractere F, N caractere B şi două caractere alăturate S) care reprezintă aranjarea iniţială a elevilor pe rând şi cele două locuri libere. Mai exact, F indică un loc ocupat de o fată, B un loc ocupat de un băiat, iar SS reprezintă cele două scaune libere.
Date de ieşire
Fişierul de ieşire aranjare.out va conţine mutările din secvenţa determinată, în ordine, câte o mutare pe o linie. O mutare este descrisă printr-o valoare naturală K (1≤K<2*N+2) cu semnificaţia ″se vor muta pe scaunele libere elevii situaţi pe scaunele K şi K+1″.
Restricţii
3 ≤ N ≤ 5000
Pentru datele de test există totdeauna soluţie. Soluţia nu este unică.
Exemple
aranjare.in
aranjare.out
Explicaţii
3
FBSSFBFB
7
2
5
3
6
1
7
3
6
4
Se vor obţine pe rând configuraţiile: FBFBFBSS
FSSBFBBF
FFBBSSBF
FFSSBBBF
FFBBBSSF
SSBBBFFF
FFBBBFSS
FFSSBFBB
FFFBBSSB
FFFSSBBB