Le nain Franek a toujours aimé toutes sortes de jeux. Un jour, alors qu'il fouillait dans les affaires de son père au grenier, il a trouvé une vieille console contenant ce qui ressemblait à un jeu de Tetris. Bien qu'il ressemble au jeu familier, certaines de ses règles étaient différentes.

Le jeu se déroule sur une grille initialement vide de largeur $10$ et de hauteur illimitée. Les pièces tombent d'en haut, une par une, dans l'ordre exact donné dans l'entrée.

Il n'y a que deux types de pièces :

• La pièce I, en forme de barre verticale de hauteur $4$ et de largeur $1$.
• La pièce O, en forme de carré plein de hauteur $2$ et de largeur $2$.

Lorsqu'une pièce apparaît, Franek doit choisir où la faire tomber :

• Une pièce I peut être lâchée dans n'importe laquelle des $10$ colonnes.
• Une pièce O peut être lâchée de sorte que ses deux colonnes tiennent entièrement dans la grille (c'est-à-dire en commençant à n'importe quelle colonne de $1$ à $9$).

Une fois qu'une pièce commence à tomber, elle descend verticalement jusqu'à ce qu'elle atterrisse sur des blocs existants ou au fond de la grille. Les pièces ne peuvent pas être tournées, déplacées latéralement en plein vol ou divisées en plusieurs parties. Une fois la pièce posée, toutes les cases qu'elle couvre deviennent remplies.

Chaque fois qu'une ligne horizontale de la grille est complètement remplie de blocs (ce qui signifie que les $10$ colonnes ont toutes un bloc à cette hauteur), cette ligne disparaît. Tous les blocs situés au-dessus descendent d'une unité. Si plusieurs lignes sont complétées en même temps, elles disparaissent toutes ensemble.

Vous marquez un tetris chaque fois qu'exactement quatre lignes disparaissent simultanément. Le but du jeu est de marquer autant de tetris que possible.

La première grille montre un exemple de configuration de pièces. Après avoir lâché une pièce I dans la $8$-ème colonne, elle commence à tomber comme indiqué sur les deuxième et troisième grilles. Après cela, les quatre lignes du bas disparaissent, marquant un tetris, ce qui donne la quatrième grille.

Étant un petit nain compétitif, Franek veut atteindre le score maximum ! Cependant, il n'est pas assez bon à ce jeu, vous devez donc l'aider. Connaissant l'ordre des pièces à l'avance, aidez Franek à déterminer le nombre maximum de tetris qu'il peut réaliser s'il joue de manière optimale. De plus, fournissez une séquence de coups permettant d'atteindre ce score.

Entrée

La première ligne contient un seul entier $N$, le nombre de pièces. La deuxième ligne contient une chaîne de longueur $N$, composée uniquement des caractères I et O, décrivant la séquence de pièces de la première à la dernière.

Sortie

Sur la première ligne, affichez un seul entier étant le nombre maximum de tetris que Franek peut réaliser. Sur la deuxième ligne, affichez une séquence de $N$ entiers $c_1, c_2, \dots, c_N$, où $c_i$ est la colonne dans laquelle la $i$-ème pièce doit être lâchée (indexée à partir de $1$). Pour une pièce I, $c_i$ doit satisfaire $1 \le c_i \le 10$. Pour une pièce O, $c_i$ désigne sa colonne de gauche et doit satisfaire $1 \le c_i \le 9$.

S'il existe plusieurs séquences optimales, vous pouvez afficher n'importe laquelle d'entre elles.

Contraintes

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

Exemples

Entrée 1

10
IIOIOIOOII

Sortie 1

1
1 2 3 5 3 6 7 7 9 10

Note

La sortie affichée n'est qu'une séquence valide de coups ; d'autres séquences peuvent également atteindre le même nombre maximum de tetris.