Il nano Franek ha sempre amato tutti i tipi di giochi. Un giorno stava frugando tra le cose di suo padre in soffitta e ha trovato una vecchia console con quello che sembrava un gioco di Tetris. Sebbene somigliasse al gioco familiare, alcune delle sue regole erano diverse.

Il gioco si svolge su una griglia inizialmente vuota di larghezza $10$ e altezza illimitata. I pezzi cadono dall'alto, uno alla volta, nell'esatto ordine fornito in input.

Ci sono solo due tipi di pezzi:

• Il pezzo I, a forma di barra verticale di altezza $4$ e larghezza $1$.
• Il pezzo O, a forma di quadrato pieno di altezza $2$ e larghezza $2$.

Quando appare un pezzo, Franek deve scegliere dove lasciarlo cadere:

• Un pezzo I può essere lasciato cadere in una qualsiasi delle $10$ colonne.
• Un pezzo O può essere lasciato cadere in modo che le sue due colonne entrino interamente nella griglia (cioè a partire da una qualsiasi colonna da $1$ a $9$).

Una volta che un pezzo inizia a cadere, scende verticalmente fino ad atterrare sopra i blocchi esistenti o sul fondo della griglia. I pezzi non possono essere ruotati, spostati lateralmente a mezz'aria o divisi in parti. Dopo che il pezzo è atterrato, tutte le celle che copre diventano piene.

Ogni volta che una riga orizzontale della griglia viene completamente riempita di blocchi (il che significa che tutte le $10$ colonne hanno un blocco a quell'altezza), quella riga scompare. Tutti i blocchi sopra di essa scendono di un'unità. Se più righe vengono completate contemporaneamente, scompaiono tutte insieme.

Si ottiene un tetris ogni volta che esattamente quattro righe scompaiono contemporaneamente. L'obiettivo del gioco è ottenere il maggior numero possibile di tetris.

La prima griglia mostra una configurazione di esempio dei pezzi. Dopo aver lasciato cadere un pezzo I nell'$8$-ava colonna, esso inizia a cadere come mostrato nella seconda e nella terza griglia. Dopodiché, le quattro righe inferiori scompaiono, segnando un tetris e portando alla quarta griglia.

Essendo un piccolo nano competitivo, Franek vuole ottenere il punteggio massimo! Tuttavia, non è abbastanza bravo nel gioco, quindi devi aiutarlo. Conoscendo in anticipo l'ordine dei pezzi, aiuta Franek a determinare il numero massimo di tetris che può ottenere giocando in modo ottimale. Inoltre, fornisci una sequenza di mosse che permetta di ottenere questo punteggio.

Input

La prima riga contiene un singolo intero $N$, il numero di pezzi. La seconda riga contiene una stringa di lunghezza $N$, composta solo dai caratteri I e O, che descrive la sequenza di pezzi dal primo all'ultimo.

Output

Nella prima riga, stampa un singolo intero pari al numero massimo di tetris che Franek può ottenere. Nella seconda riga, stampa una sequenza di $N$ interi $c_1, c_2, \dots, c_N$, dove $c_i$ è la colonna in cui deve essere lasciato cadere l'$i$-esimo pezzo (indicizzata da $1$). Per un pezzo I, $c_i$ deve soddisfare $1 \le c_i \le 10$. Per un pezzo O, $c_i$ si riferisce alla sua colonna di sinistra e deve soddisfare $1 \le c_i \le 9$.

Se esistono più sequenze ottimali, puoi stamparne una qualsiasi.

Limiti

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

Esempi

Input 1

10
IIOIOIOOII

Output 1

1
1 2 3 5 3 6 7 7 9 10

Note

L'output mostrato è solo una sequenza valida di mosse; altre sequenze possono comunque raggiungere lo stesso numero massimo di tetris.