ドワーフの Franek はいつもあらゆる種類のゲームが大好きでした。ある日、屋根裏部屋で父親の荷物をあさっていたところ、テトリス（Tetris）のようなゲームが入った古いゲーム機を見つけました。見慣れたゲームに似ていましたが、いくつかのルールが異なっていました。

ゲームは、最初は空である幅 $10$、高さ無制限の盤面で行われます。ピースは入力で与えられた通りの順番で、上から $1$ つずつ落ちてきます。

ピースは次の $2$ 種類しかありません：

• I-ピース：高さ $4$、幅 $1$ の縦長の棒のような形をしています。
• O-ピース：高さ $2$、幅 $2$ の中身の詰まった正方形のような形をしています。

ピースが現れると、Franek はそれをどこに落とすかを選ばなければなりません：

• I-ピースは $10$ 個の列のどれにでも落とすことができます。
• O-ピースは、その $2$ つの列が盤面内に完全に収まるように落とすことができます（つまり、$1$ 列目から $9$ 列目までのいずれかの列を左端として落とせます）。

ピースが落下し始めると、既存のブロックの上または盤面の底に着地するまで垂直に降りていきます。ピースを回転させたり、空中で横に動かしたり、複数の部分に分割したりすることはできません。ピースが着地すると、それが覆うすべてのマスが埋められます。

盤面の水平な行がブロックで完全に埋め尽くされると（つまり、その高さで $10$ 列すべてにブロックがある状態になると）、その行は消滅します。それより上にあるすべてのブロックは $1$ 単位下に移動します。複数の行が同時に完成した場合、それらはすべて同時に消滅します。

ちょうど $4$ つの行が同時に消滅するたびに、$1$ テトリス（tetris）を獲得します。ゲームの目的は、できるだけ多くのテトリスを獲得することです。

最初の盤面はピースの配置例を示しています。$8$ 列目に I-ピースを落とすと、$2$ 番目と $3$ 番目の盤面に示されているように落下し始めます。その後、下から $4$ つの行が消滅してテトリスを獲得し、$4$ 番目の盤面のようになります。

負けず嫌いな小さなドワーフである Franek は、最高得点を達成したいと思っています！しかし、彼はゲームが十分に上手ではないので、あなたが彼を助けなければなりません。ピースの順番をあらかじめ知った上で、Franek が最適にプレイした場合に達成できるテトリスの最大数を求めてください。さらに、このスコアを達成する手順を $1$ つ示してください。

入力

$1$ 行目には、ピースの数を表す単一の整数 $N$ が含まれます。$2$ 行目には、文字 I と O のみからなる長さ $N$ の文字列が含まれ、最初から最後までのピースの並びを表します。

出力

$1$ 行目に、Franek が達成できるテトリスの最大数を表す単一の整数を出力してください。$2$ 行目に、$N$ 個の整数からなる列 $c_1, c_2, \dots, c_N$ を出力してください。ここで $c_i$ は $i$ 番目のピースを落とすべき列番号（$1$-indexed）です。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

注記

示されている出力は有効な手順の $1$ つに過ぎません。他の手順でも同じ最大数のテトリスを達成できる場合があります。