Mirko found a board on the street consisting of $R \times S$ fields (unit squares) arranged in $R$ rows and $S$ columns. At the moment Mirko found the board, all its fields were filled with white color. Mirko decided to paint some fields black. After doing so, he sent the board to his friend Slavko along with the following message:
"Dear Slavko, I challenge you to find the smallest number of rectangles that will cover all the black fields. At the same time, no white field may be covered by a rectangle, no black field may be covered by two or more rectangles, and no rectangle may extend outside the board."
As you probably already guessed, Slavko is not up to the challenge, so he asked you for help.
Input
The first line contains the natural numbers $R$ and $S$, which represent the dimensions of Mirko's board.
Each of the following $R$ rows contains $S$ characters representing the fields of Mirko's board. More precisely, the character 'B' denotes a white field, and the character 'C' denotes a black field.
Output
In each of the $R$ rows of the output, it is necessary to print $S$ space-separated numbers representing the solution to Mirko's challenge.
Fields covered by the first rectangle should be marked with the number 1 in the output, fields covered by the second rectangle should be marked with the number 2, and so on, up to the last, $N$-th rectangle, whose covered fields are marked with the number $N$. Fields that are not covered by any rectangle, i.e., white fields, should be marked with the number 0.
Scoring
Test cases where your solution violates any of the conditions from the problem text will be scored with 0 points.
Test cases where your solution correctly covers all black fields but does not use the minimum number of rectangles will be scored with:
$$0.75 \cdot (A / B)^{10} \cdot X$$
points, where $A$ denotes the optimal number of rectangles, $B$ denotes the number of rectangles in your solution, and $X$ denotes the number of points that the mentioned test case carries.
Naturally, test cases where your solution correctly covers all black fields using the optimal number of rectangles will earn you all the allotted points.
| testni primjeri | broj bodova | dodatna ograničenja |
|---|---|---|
| 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$ |
Examples
Input 1
4 5 CCBCB CCBBB CCCBB CCCBB
Output 1
1 1 0 2 0 1 1 0 0 0 3 3 3 0 0 3 3 3 0 0
Input 2
7 5 CCCBB BCBBB BCCCB BCCCB CCCCC BBBBB BCCCB
Output 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
Input 3
5 11 BBCCCBCCCBC BCCBCBBCCCC CCCCBCCCCCC BCBCCCBCCCB CCCCBCBBCCB
Output 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