Гном Франек всегда любил всевозможные игры. Однажды он разбирал на чердаке вещи своего отца и нашел старую приставку с игрой, похожей на Тетрис (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

Примечание

Приведенный вывод — лишь одна из допустимых последовательностей ходов; другие последовательности также могут давать то же максимальное количество тетрисов.