Dvärgen Franek har alltid älskat alla sorters spel. En dag gick han igenom sin pappas saker på vinden och hittade en gammal spelkonsol med något som verkade vara ett Tetris-spel. Även om det liknade det välbekanta spelet var några av reglerna annorlunda.

Spelet spelas på ett från början tomt bräde med bredden $10$ och obegränsad höjd. Bitarna faller uppifrån, en efter en, i exakt den ordning som anges i indatan.

Det finns bara två typer av bitar:

• I-biten, formad som en vertikal stav med höjden $4$ och bredden $1$.
• O-biten, formad som en fylld kvadrat med höjden $2$ och bredden $2$.

När en bit dyker upp måste Franek välja var han ska släppa den:

• En I-bit kan släppas i vilken som helst av de $10$ kolumnerna.
• En O-bit kan släppas så att dess två kolumner får plats helt inom brädet (det vill säga med start i vilken kolumn som helst från $1$ till $9$).

När en bit börjar falla sjunker den vertikalt tills den landar ovanpå befintliga block eller på botten av brädet. Bitarna kan inte roteras, flyttas i sidled i luften eller delas upp i delar. Efter att biten har landat blir alla rutor den täcker fyllda.

Närhelst en horisontell rad på brädet blir helt fylld med block (vilket betyder att alla $10$ kolumner har ett block på den höjden), försvinner den raden. Alla block ovanför den flyttas ner en enhet. Om flera rader blir klara samtidigt försvinner de alla tillsammans.

Du får en tetris varje gång exakt fyra rader försvinner samtidigt. Målet med spelet är att få så många tetrisar som möjligt.

Det första brädet visar en exempelkonfiguration av bitar. Efter att en I-bit släppts i den $8$:e kolumnen börjar den falla som visas på det andra och tredje brädet. Därefter försvinner de fyra nedersta raderna, vilket ger en tetris och resulterar i det fjärde brädet.

Som den tävlingsinriktade lilla dvärg han är vill Franek uppnå maximal poäng! Han är dock inte tillräckligt bra på spelet, så du måste hjälpa honom. Med kännedom om bitarnas ordning i förväg, hjälp Franek att bestämma det maximala antalet tetrisar han kan uppnå om han spelar optimalt. Ange dessutom en sekvens av drag som uppnår denna poäng.

Indata

Den första raden innehåller ett enda heltal $N$, antalet bitar. Den andra raden innehåller en sträng av längd $N$, som endast består av tecknen I och O, vilken beskriver sekvensen av bitar från den första till den sista.

Utdata

På den första raden ska du skriva ut ett enda heltal som är det maximala antalet tetrisar Franek kan uppnå. På den andra raden ska du skriva ut en sekvens av $N$ heltal $c_1, c_2, \dots, c_N$, där $c_i$ är kolumnen som den $i$-te biten ska släppas i ($1$-indexerad). För en I-bit måste $c_i$ uppfylla $1 \le c_i \le 10$. För en O-bit avser $c_i$ dess vänstra kolumn och måste uppfylla $1 \le c_i \le 9$.

Om det finns flera optimala sekvenser får du skriva ut vilken som helst av dem.

Begränsningar

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

Exempel

Indata 1

10
IIOIOIOOII

Utdata 1

1
1 2 3 5 3 6 7 7 9 10

Förklaring

Utdatan som visas är bara en giltig sekvens av drag; andra sekvenser kan också uppnå samma maximala antal tetrisar.