Al enano Franek siempre le han encantado todo tipo de juegos. Un día estaba revisando las cosas de su papá en el ático y encontró una vieja consola con lo que parecía un juego de Tetris. Aunque se parecía al juego familiar, algunas de sus reglas eran diferentes.

El juego se desarrolla en un tablero inicialmente vacío de ancho $10$ y altura ilimitada. Las piezas caen desde arriba, una por una, en el orden exacto dado en la entrada.

Solo hay dos tipos de piezas:

• La pieza I, con forma de barra vertical de altura $4$ y ancho $1$.
• La pieza O, con forma de cuadrado sólido de altura $2$ y ancho $2$.

Cuando aparece una pieza, Franek debe elegir dónde dejarla caer:

• Una pieza I puede dejarse caer en cualquiera de las $10$ columnas.
• Una pieza O puede dejarse caer de modo que sus dos columnas quepan completamente dentro del tablero (es decir, comenzando en cualquier columna de la $1$ a la $9$).

Una vez que una pieza comienza a caer, desciende verticalmente hasta que aterriza sobre bloques existentes o en el fondo del tablero. Las piezas no se pueden rotar, mover hacia los lados en el aire ni dividir en partes. Después de que la pieza aterriza, todas las celdas que cubre quedan llenas.

Cada vez que una fila horizontal del tablero se llena completamente de bloques (lo que significa que las $10$ columnas tienen un bloque a esa altura), esa fila desaparece. Todos los bloques por encima de ella bajan una unidad. Si se completan varias filas al mismo tiempo, todas desaparecen juntas.

Anotas un tetris cada vez que exactamente cuatro filas desaparecen simultáneamente. El objetivo del juego es anotar tantos tetris como sea posible.

El primer tablero muestra una configuración de ejemplo de las piezas. Después de dejar caer una pieza I en la $8$-ª columna, comienza a caer como se muestra en el segundo y tercer tablero. Después de eso, las cuatro filas inferiores desaparecen, anotando un tetris y dando como resultado el cuarto tablero.

Como buen enanito competitivo, ¡Franek quiere lograr la puntuación máxima! Sin embargo, no es lo suficientemente bueno en el juego, así que tienes que ayudarlo. Conociendo el orden de las piezas de antemano, ayuda a Franek a determinar el número máximo de tetris que puede lograr si juega de manera óptima. Además, proporciona una secuencia de movimientos que logre esta puntuación.

Entrada

La primera línea contiene un solo entero $N$, el número de piezas. La segunda línea contiene una cadena de longitud $N$, que consta únicamente de los caracteres I y O, describiendo la secuencia de piezas desde la primera hasta la última.

Salida

En la primera línea, imprime un solo entero que sea el número máximo de tetris que Franek puede lograr. En la segunda línea, imprime una secuencia de $N$ enteros $c_1, c_2, \dots, c_N$, donde $c_i$ es la columna en la que se debe dejar caer la $i$-ésima pieza (indexada desde $1$). Para una pieza I, $c_i$ debe satisfacer $1 \le c_i \le 10$. Para una pieza O, $c_i$ se refiere a su columna izquierda y debe satisfacer $1 \le c_i \le 9$.

Si hay múltiples secuencias óptimas, puedes imprimir cualquiera de ellas.

Límites

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

Ejemplos

Entrada 1

10
IIOIOIOOII

Salida 1

1
1 2 3 5 3 6 7 7 9 10

Nota

La salida mostrada es solo una secuencia válida de movimientos; otras secuencias también pueden lograr el mismo número máximo de tetris.