Гном Франек завжди любив усілякі ігри. Одного разу він розбирав на горищі речі свого батька і знайшов стару приставку з грою, схожою на Тетріс (Tetris). Хоча вона нагадувала знайому гру, деякі її правила відрізнялися.
Гра ведеться на початково порожньому полі шириною $10$ і необмеженої висоти. Фігурки падають зверху одна за одною точно в тому порядку, який задано у вхідних даних.
Є лише два типи фігурок:
I-фігурка у формі вертикальної смужки висотою $4$ і шириною $1$.O-фігурка у формі суцільного квадрата висотою $2$ і шириною $2$.
Коли з'являється фігурка, Франек повинен вибрати, куди її скинути:
I-фігурку можна скинути в будь-який із $10$ стовпців.O-фігурку можна скинути так, щоб обидва її стовпці повністю поміщалися в межах поля (тобто починаючи з будь-якого стовпця від $1$ до $9$).
Щойно фігурка починає падати, вона опускається вертикально, доки не приземлиться поверх уже наявних блоків або на дно поля. Фігурки не можна повертати, зсувати вбік у повітрі або розділяти на частини. Після приземлення фігурки всі клітинки, які вона накриває, стають заповненими.
Щоразу, коли горизонтальний ряд поля повністю заповнюється блоками (тобто в усіх $10$ стовпцях на цій висоті є блок), цей ряд зникає. Усі блоки над ним зсуваються на одну одиницю вниз. Якщо одночасно заповнюються кілька рядів, вони зникають усі разом.
Ви отримуєте один тетріс (tetris) щоразу, коли рівно чотири ряди зникають одночасно. Мета гри — набрати якомога більше тетрісів.
На першому полі показано приклад конфігурації фігурок. Після скидання I-фігурки у $8$-й стовпець вона починає падати, як показано на другому та третьому полях. Після цього нижні чотири ряди зникають, приносячи один тетріс і приводячи до четвертого поля.
Будучи азартним маленьким гномом, Франек хоче набрати максимальну кількість очок! Проте він недостатньо добре грає в цю гру, тому ви маєте йому допомогти. Знаючи порядок фігурок заздалегідь, допоможіть Франеку визначити максимальну кількість тетрісів, яку він може набрати за оптимальної гри. Крім того, наведіть послідовність ходів, що дозволяє досягти цього результату.
Вхідні дані
Перший рядок містить одне ціле число $N$ — кількість фігурок. Другий рядок містить рядок довжини $N$, що складається лише із символів I та O, який описує послідовність фігурок від першої до останньої.
Вихідні дані
У першому рядку виведіть одне ціле число — максимальну кількість тетрісів, яку може набрати Франек. У другому рядку виведіть послідовність із $N$ цілих чисел $c_1, c_2, \dots, c_N$, де $c_i$ — номер стовпця, у який слід скинути $i$-ту фігурку ($1$-індексація). Для I-фігурки число $c_i$ повинно задовольняти умову $1 \le c_i \le 10$. Для O-фігурки число $c_i$ позначає її лівий стовпець і повинно задовольняти умову $1 \le c_i \le 9$.
Якщо оптимальних послідовностей декілька, ви можете вивести будь-яку з них.
Обмеження
$1 \le N \le 200\,000$.
Приклади
Вхідні дані 1
10 IIOIOIOOII
Вихідні дані 1
1 1 2 3 5 3 6 7 7 9 10
Примітка
Наведений вивід — лише одна з допустимих послідовностей ходів; інші послідовності також можуть давати ту саму максимальну кількість тетрісів.