Dvergen Franek har alltid elsket alle slags spill. En dag gikk han gjennom tingene til faren sin på loftet og fant en gammel spillkonsoll med det som så ut som et Tetris-spill. Selv om det lignet på det kjente spillet, var noen av reglene annerledes.

Spillet spilles på et i utgangspunktet tomt brett med bredde $10$ og ubegrenset høyde. Brikkene faller ovenfra, én etter én, i nøyaktig den rekkefølgen som er gitt i inndataene.

Det finnes bare to typer brikker:

• I-brikken, formet som en vertikal stang med høyde $4$ og bredde $1$.
• O-brikken, formet som et massivt kvadrat med høyde $2$ og bredde $2$.

Når en brikke dukker opp, må Franek velge hvor han vil slippe den:

• En I-brikke kan slippes i hvilken som helst av de $10$ kolonnene.
• En O-brikke kan slippes slik at de to kolonnene dens får plass helt innenfor brettet (det vil si med start i hvilken som helst kolonne fra $1$ til $9$).

Når en brikke begynner å falle, synker den vertikalt til den lander oppå eksisterende blokker eller på bunnen av brettet. Brikker kan ikke roteres, flyttes sidelengs i luften eller deles opp i deler. Etter at brikken har landet, blir alle ruter den dekker fylt.

Hver gang en horisontal rad på brettet blir helt fylt med blokker (som betyr at alle $10$ kolonnene har en blokk i den høyden), forsvinner den raden. Alle blokker over den flyttes én enhet ned. Hvis flere rader fullføres samtidig, forsvinner de alle sammen.

Du scorer én tetris hver gang nøyaktig fire rader forsvinner samtidig. Målet med spillet er å score så mange tetriser som mulig.

Det første brettet viser en eksempelkonfigurasjon av brikker. Etter å ha sluppet en I-brikke i den $8$. kolonnen, begynner den å falle som vist på det andre og tredje brettet. Etter det forsvinner de fire nederste radene, noe som gir én tetris og resulterer i det fjerde brettet.

Som en konkurranselysten liten dverg ønsker Franek å oppnå maksimal poengsum! Han er imidlertid ikke god nok i spillet, så du må hjelpe ham. Når du kjenner rekkefølgen på brikkene på forhånd, hjelp Franek med å finne det maksimale antallet tetriser han kan oppnå hvis han spiller optimalt. I tillegg skal du oppgi en sekvens av trekk som oppnår denne poengsummen.

Inndata

Den første linjen inneholder ett enkelt heltall $N$, antallet brikker. Den andre linjen inneholder en streng av lengde $N$, som kun består av tegnene I og O, og som beskriver sekvensen av brikker fra første til siste.

Utdata

På den første linjen skal du skrive ut ett enkelt heltall som er det maksimale antallet tetriser Franek kan oppnå. På den andre linjen skal du skrive ut en sekvens av $N$ heltall $c_1, c_2, \dots, c_N$, der $c_i$ er kolonnen som den $i$-te brikken skal slippes i ($1$-indeksert). For en I-brikke må $c_i$ tilfredsstille $1 \le c_i \le 10$. For en O-brikke refererer $c_i$ til dens venstre kolonne og må tilfredsstille $1 \le c_i \le 9$.

Hvis det finnes flere optimale sekvenser, kan du skrive ut hvilken som helst av dem.

Begrensninger

$1 \le N \le 200\,000$.

Eksempler

Inndata 1

10
IIOIOIOOII

Utdata 1

1
1 2 3 5 3 6 7 7 9 10

Forklaring

Utdataene som vises er bare én gyldig sekvens av trekk; andre sekvenser kan også oppnå det samme maksimale antallet tetriser.