小矮人 Franek 一直很喜欢各种游戏。有一天，他在阁楼里翻找父亲的旧物时，发现了一台旧游戏机，上面似乎运行着一款俄罗斯方块游戏。虽然它看起来很像我们熟悉的游戏，但其中一些规则有所不同。

游戏在一个初始为空、宽度为 10、高度无限的棋盘上进行。方块会按照输入给出的确切顺序，一个接一个地从上方落下。

方块只有两种类型：

• I 型方块：形状为高 4、宽 1 的垂直长条。
• O 型方块：形状为高 2、宽 2 的实心正方形。

当一个方块出现时，Franek 必须选择将其投放在哪里：

• I 型方块可以投放到 10 列中的任意一列。
• O 型方块可以投放到其占据的两列完全位于棋盘内的位置（即从第 1 列到第 9 列的任意起始列）。

一旦方块开始下落，它会垂直下降，直到落在现有方块的顶部或棋盘底部。方块不能旋转、在空中横向移动或拆分。方块落地后，它所覆盖的所有单元格都会被填满。

每当棋盘上的一行被方块完全填满（即所有 10 列在该高度都有方块）时，该行就会消失。其上方的所有方块都会向下移动一个单位。如果有多行同时被填满，它们会一起消失。

每当恰好有四行同时消失时，你就会获得一分（即一个“俄罗斯方块”）。游戏的目标是尽可能多地获得分数。

第一张棋盘显示了一个方块配置示例。在第 8 列投放一个 I 型方块后，它开始下落，如图中第二和第三张棋盘所示。此后，底部的四行消失，获得一个“俄罗斯方块”，结果如第四张棋盘所示。

作为一个好胜的小矮人，Franek 想要获得最高分！然而，他的游戏水平不够，所以你需要帮助他。在预先知道方块顺序的情况下，请帮助 Franek 确定他以最优策略游玩时能获得的最高分数。此外，请提供一个能够达到该分数的落点序列。

输入格式

第一行包含一个整数 $N$，表示方块的数量。第二行包含一个长度为 $N$ 的字符串，仅由字符 I 和 O 组成，描述了从第一个到最后一个方块的顺序。

输出格式

第一行输出一个整数，表示 Franek 能获得的最高分数。第二行输出一个包含 $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

说明

输出展示的仅为一种有效的落点序列；其他序列也可能达到相同的最高分数。