小矮人 Franek 一直都好鍾意各種遊戲。有一日，佢喺閣樓度摷緊阿爸啲舊嘢嗰陣，發現咗一部舊遊戲機，上面好似行緊隻俄羅斯方塊（Tetris）遊戲。雖然睇落好似我哋熟悉嘅遊戲，但係入面有啲規則係唔同嘅。

遊戲喺一個最初係空嘅、闊度為 $10$、高度無限嘅棋盤上面進行。方塊會按照輸入畀出嘅確切順序，一個接一個噉由上面跌落嚟。

方塊只有兩種類型：

• I 型方塊，形狀係高 $4$、闊 $1$ 嘅垂直長條。
• O 型方塊，形狀係高 $2$、闊 $2$ 嘅實心正方形。

當一個方塊出現嗰陣，Franek 必須選擇將佢擺喺邊度跌落去：

• I 型方塊可以擺入 $10$ 列之中嘅任意一列。
• O 型方塊可以擺喺令佢佔據嘅兩列完全位於棋盤入面嘅位置（即係由第 $1$ 列到第 $9$ 列嘅任意一列開始）。

一旦方塊開始下落，佢就會垂直下降，直到落喺現有方塊嘅頂部或者棋盤底部為止。方塊唔可以旋轉、喺半空中橫向移動或者拆開成幾部分。方塊落地之後，佢所覆蓋嘅所有格仔都會被填滿。

每當棋盤上面嘅一行水平行被方塊完全填滿（即係全部 $10$ 列喺該高度都有方塊）嗰陣，嗰一行就會消失。佢上面嘅所有方塊都會向下移動一個單位。如果同時有多行被填滿，佢哋會一齊消失。

每當恰好有四行同時消失嗰陣，你就會得到一個 tetris（一分）。遊戲嘅目標係獲得盡可能多嘅 tetris。

第一塊棋盤展示咗一個方塊配置示例。喺第 $8$ 列擺入一個 I 型方塊之後，佢開始下落，如第二同第三塊棋盤所示。之後，底部嘅四行消失，獲得一個 tetris，結果如第四塊棋盤所示。

作為一個好勝嘅小矮人，Franek 想要獲得最高分！不過佢玩呢隻遊戲唔夠叻，所以你要幫下佢。喺預先知道方塊順序嘅情況下，請幫 Franek 計出如果佢用最優策略去玩，最多可以獲得幾多個 tetris。另外，請提供一個可以達到呢個分數嘅操作序列。

輸入格式

第一行包含一個整數 $N$，代表方塊嘅數量。第二行包含一個長度為 $N$ 嘅字串，只由字符 I 同 O 組成，描述由第一個到最後一個方塊嘅順序。

輸出格式

喺第一行，輸出一個整數，代表 Franek 最多可以獲得嘅 tetris 數量。喺第二行，輸出一個包含 $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

說明

上面展示嘅輸出只係其中一個有效嘅操作序列；其他序列亦可能達到相同嘅最大 tetris 數量。