Krasnolud Franek od zawsze uwielbiał wszelkiego rodzaju gry. Pewnego dnia przeglądał na strychu rzeczy swojego taty i znalazł starą konsolę z czymś, co wyglądało jak gra Tetris. Chociaż przypominała ona znaną grę, niektóre jej zasady były inne.

Gra toczy się na początkowo pustej planszy o szerokości $10$ i nieograniczonej wysokości. Klocki spadają z góry, jeden po drugim, dokładnie w takiej kolejności, jaka została podana na wejściu.

Są tylko dwa rodzaje klocków:

• Klocek I, w kształcie pionowego paska o wysokości $4$ i szerokości $1$.
• Klocek O, w kształcie pełnego kwadratu o wysokości $2$ i szerokości $2$.

Gdy pojawia się klocek, Franek musi wybrać, gdzie go zrzucić:

• Klocek I można zrzucić do dowolnej z $10$ kolumn.
• Klocek O można zrzucić tak, aby jego dwie kolumny mieściły się całkowicie w obrębie planszy (to znaczy zaczynając od dowolnej kolumny od $1$ do $9$).

Gdy klocek zaczyna spadać, opada pionowo, aż wyląduje na wierzchu istniejących już bloków lub na dnie planszy. Klocków nie można obracać, przesuwać na boki w powietrzu ani dzielić na części. Po wylądowaniu klocka wszystkie pola, które przykrywa, stają się zapełnione.

Ilekroć poziomy wiersz planszy zostanie całkowicie zapełniony blokami (co oznacza, że wszystkie $10$ kolumn ma blok na tej wysokości), wiersz ten znika. Wszystkie bloki znajdujące się nad nim przesuwają się o jedną jednostkę w dół. Jeśli kilka wierszy zostanie zapełnionych jednocześnie, wszystkie znikają naraz.

Zdobywasz jeden punkt tetris, gdy dokładnie cztery wiersze znikają jednocześnie. Celem gry jest zdobycie jak największej liczby tetrisów.

Pierwsza plansza przedstawia przykładową konfigurację klocków. Po zrzuceniu klocka I w $8$-ej kolumnie zaczyna on spadać, jak pokazano na drugiej i trzeciej planszy. Następnie dolne cztery wiersze znikają, dając jednego tetrisa i prowadząc do czwartej planszy.

Jako ambitny mały krasnolud, Franek chce osiągnąć maksymalny wynik! Nie jest jednak wystarczająco dobry w tej grze, więc musisz mu pomóc. Znając z góry kolejność klocków, pomóż Frankowi wyznaczyć maksymalną liczbę tetrisów, jaką może uzyskać, grając optymalnie. Dodatkowo podaj ciąg ruchów, który pozwala osiągnąć ten wynik.

Wejście

Pierwszy wiersz zawiera jedną liczbę całkowitą $N$, oznaczającą liczbę klocków. Drugi wiersz zawiera napis długości $N$, składający się wyłącznie ze znaków I oraz O, opisujący ciąg klocków od pierwszego do ostatniego.

Wyjście

W pierwszym wierszu wypisz jedną liczbę całkowitą będącą maksymalną liczbą tetrisów, jaką może uzyskać Franek. W drugim wierszu wypisz ciąg $N$ liczb całkowitych $c_1, c_2, \dots, c_N$, gdzie $c_i$ oznacza numer kolumny, do której należy zrzucić $i$-ty klocek (numeracja od $1$). Dla klocka I wartość $c_i$ musi spełniać $1 \le c_i \le 10$. Dla klocka O wartość $c_i$ oznacza jego lewą kolumnę i musi spełniać $1 \le c_i \le 9$.

Jeśli istnieje wiele optymalnych ciągów ruchów, możesz wypisać dowolny z nich.

Ograniczenia

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

Przykłady

Wejście 1

10
IIOIOIOOII

Wyjście 1

1
1 2 3 5 3 6 7 7 9 10

Uwaga

Pokazane wyjście to tylko jeden z poprawnych ciągów ruchów; inne ciągi również mogą dawać tę samą maksymalną liczbę tetrisów.