미르코는 거리에서 $R \times S$개의 칸(단위 정사각형)으로 이루어진 판을 발견했습니다. 이 판은 $R$개의 행과 $S$개의 열로 구성되어 있습니다. 미르코가 판을 발견했을 때, 모든 칸은 흰색으로 칠해져 있었습니다. 미르코는 몇몇 칸을 검은색으로 칠하기로 했습니다. 작업을 마친 후, 그는 친구 슬라브코에게 다음과 같은 메시지와 함께 판을 보냈습니다.
"사랑하는 슬라브코, 모든 검은색 칸을 덮을 수 있는 최소한의 직사각형들을 찾아보게. 이때, 어떤 흰색 칸도 직사각형으로 덮여서는 안 되며, 어떤 검은색 칸도 두 개 이상의 직사각형으로 덮여서는 안 되고, 어떤 직사각형도 판 밖으로 나가서는 안 되네."
아마 짐작하겠지만, 슬라브코는 이 도전을 해결하지 못해 당신에게 도움을 요청했습니다.
입력
첫 번째 줄에는 미르코의 판의 크기를 나타내는 자연수 $R$과 $S$가 주어집니다. 이어지는 $R$개의 각 줄에는 미르코의 판의 상태를 나타내는 $S$개의 문자가 주어집니다. 더 구체적으로, 문자 'B'는 흰색 칸을, 문자 'C'는 검은색 칸을 의미합니다.
출력
$R$개의 각 줄에 미르코의 도전 과제에 대한 해결책을 나타내는 $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