小矮人 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 數量。