Mirko は通りで、$R \times S$ 個のマス（単位正方形）からなるボードを見つけました。ボードは $R$ 行 $S$ 列に配置されています。Mirko がボードを見つけたとき、すべてのマスは白色でした。Mirko はいくつかのマスを黒色に塗ることにしました。その後、彼は友人の Slavko にボードを送り、次のようなメッセージを添えました。
「親愛なる Slavko、すべての黒いマスを覆う最小限の数の長方形を見つけることに挑戦してほしい。ただし、白いマスは一つも長方形で覆われてはならず、黒いマスは二つ以上の長方形で覆われてはならず、どの長方形もボードの外にはみ出してはならない。」
おそらく予想されている通り、Slavko はこの挑戦をこなすことができなかったため、あなたに助けを求めました。
入力
最初の行には、Mirko のボードの寸法を表す自然数 $R$ と $S$ が与えられます。 続く $R$ 行のそれぞれには、Mirko のボードのマスを表す $S$ 個の文字が与えられます。具体的には、文字 'B' は白いマスを、文字 'C' は黒いマスを表します。
出力
$R$ 行のそれぞれに、Mirko の挑戦の解を表す $S$ 個の数値をスペース区切りで出力してください。
最初の長方形で覆われるマスは 1、二番目の長方形で覆われるマスは 2、というように、最後の $N$ 番目の長方形まで順に番号を付けます。どの長方形にも覆われないマス、すなわち白いマスは 0 とします。
小課題
提出した解が問題文中の条件のいずれかに違反する場合、そのテストケースの得点は 0 点となります。
提出した解がすべての黒いマスを正しく覆っているものの、長方形の数が最小ではない場合、以下の式で計算される得点が与えられます。
$$0.75 \cdot (A / B)^{10} \cdot X$$
ここで、$A$ は最適な長方形の数、$B$ はあなたの解における長方形の数、$X$ はそのテストケースに割り当てられた配点です。
もちろん、すべての黒いマスを最適な数の長方形で正しく覆うことができた場合、そのテストケースの満点が与えられます。
| テストケース | 配点 | 追加制約 |
|---|---|---|
| 1. – 5. | 25 | $1 \le R, S \le 26$ |
| 6. – 10. | 25 | $1 \le R, S \le 100$ |
| 11. – 15. | 25 | $1 \le R, S \le 250$ |
| 16. – 20. | 25 | $1 \le R, S \le 500$ |
入出力例
入力 1
4 5 CCBCB CCBBB CCCBB CCCBB
出力 1
1 1 0 2 0 1 1 0 0 0 3 3 3 0 0 3 3 3 0 0
入力 2
7 5 CCCBB BCBBB BCCCB BCCCB CCCCC BBBBB BCCCB
出力 2
1 1 1 0 0 0 2 0 0 0 0 3 3 3 0 0 3 3 3 0 4 4 4 4 4 0 0 0 0 0 0 5 5 5 0
入力 3
5 11 BBCCCBCCCBC BCCBCBBCCCC CCCCBCCCCCC BCBCCCBCCCB CCCCBCBBCCB
出力 3
0 0 1 1 1 0 2 2 2 0 3 0 4 4 0 5 0 0 6 6 6 3 7 7 7 7 0 8 8 6 6 6 3 0 9 0 10 10 10 0 6 6 6 0 11 11 11 11 0 12 0 0 13 13 0