Zwerg Franek hat schon immer alle Arten von Spielen geliebt. Eines Tages durchstöberte er auf dem Dachboden die Sachen seines Vaters und fand eine alte Konsole mit etwas, das wie ein Tetris-Spiel aussah. Obwohl es dem bekannten Spiel ähnelte, waren einige der Regeln anders.

Das Spiel wird auf einem anfangs leeren Spielfeld der Breite $10$ und unbegrenzter Höhe gespielt. Die Spielsteine fallen einzeln nacheinander von oben herab, genau in der in der Eingabe angegebenen Reihenfolge.

Es gibt nur zwei Arten von Spielsteinen:

• Den I-Stein, geformt wie ein vertikaler Balken der Höhe $4$ und Breite $1$.
• Den O-Stein, geformt wie ein ausgefülltes Quadrat der Höhe $2$ und Breite $2$.

Wenn ein Spielstein erscheint, muss Franek wählen, wo er ihn fallen lässt:

• Ein I-Stein kann in jede beliebige der $10$ Spalten fallen gelassen werden.
• Ein O-Stein kann so fallen gelassen werden, dass seine beiden Spalten vollständig in das Spielfeld passen (d. h. beginnend bei einer beliebigen Spalte von $1$ bis $9$).

Sobald ein Spielstein zu fallen beginnt, sinkt er senkrecht nach unten, bis er auf bereits vorhandenen Blöcken oder auf dem Boden des Spielfelds landet. Spielsteine können nicht gedreht, in der Luft seitwärts bewegt oder in Teile zerlegt werden. Nachdem der Spielstein gelandet ist, werden alle Felder, die er bedeckt, gefüllt.

Immer wenn eine horizontale Reihe des Spielfelds vollständig mit Blöcken gefüllt wird (was bedeutet, dass alle $10$ Spalten in dieser Höhe einen Block haben), verschwindet diese Reihe. Alle Blöcke darüber bewegen sich um eine Einheit nach unten. Wenn mehrere Reihen gleichzeitig vervollständigt werden, verschwinden sie alle zusammen.

Man erzielt einen Tetris, wann immer genau vier Reihen gleichzeitig verschwinden. Das Ziel des Spiels ist es, so viele Tetrises wie möglich zu erzielen.

Das erste Spielfeld zeigt eine Beispielkonfiguration von Spielsteinen. Nachdem ein I-Stein in die $8$-te Spalte fallen gelassen wurde, beginnt er zu fallen, wie im zweiten und dritten Spielfeld gezeigt. Danach verschwinden die unteren vier Reihen, was einen Tetris einbringt und zum vierten Spielfeld führt.

Da Franek ein ehrgeiziger kleiner Zwerg ist, möchte er die maximale Punktzahl erreichen! Allerdings ist er nicht gut genug in dem Spiel, also musst du ihm helfen. Da du die Reihenfolge der Spielsteine im Voraus kennst, hilf Franek dabei, die maximale Anzahl an Tetrises zu bestimmen, die er bei optimalem Spiel erreichen kann. Gib außerdem eine Zugfolge an, die diese Punktzahl erreicht.

Eingabe

Die erste Zeile enthält eine einzige ganze Zahl $N$, die Anzahl der Spielsteine. Die zweite Zeile enthält einen String der Länge $N$, der nur aus den Zeichen I und O besteht und die Reihenfolge der Spielsteine vom ersten bis zum letzten beschreibt.

Ausgabe

Gib in der ersten Zeile eine einzige ganze Zahl aus, welche die maximale Anzahl an Tetrises darstellt, die Franek erreichen kann. Gib in der zweiten Zeile eine Folge von $N$ ganzen Zahlen $c_1, c_2, \dots, c_N$ aus, wobei $c_i$ die Spalte ist, in die der $i$-te Spielstein fallen gelassen werden soll ($1$-indexiert). Für einen I-Stein muss $c_i$ die Bedingung $1 \le c_i \le 10$ erfüllen. Für einen O-Stein bezieht sich $c_i$ auf seine linke Spalte und muss $1 \le c_i \le 9$ erfüllen.

Wenn es mehrere optimale Folgen gibt, kannst du eine beliebige davon ausgeben.

Einschränkungen

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

Beispiele

Eingabe 1

10
IIOIOIOOII

Ausgabe 1

1
1 2 3 5 3 6 7 7 9 10

Hinweis

Die gezeigte Ausgabe ist nur eine gültige Zugfolge; andere Folgen können ebenfalls dieselbe maximale Anzahl an Tetrises erreichen.