25032번 - Young Zebra

문제

요즘 젊은 얼룩말 사이에서는, 가죽의 흑백 무늬를 새롭게 바꾸는 수술이 대인기다. 젊은 얼룩말인 정우도 이 수술로 가죽의 무늬를 바꾸는 것에 관심이 많다.

이 수술을 받기 전에 수술을 받는 얼룩말이 원하는 크기의 흑백 패턴을 준비 해야 하고, 수술은 이 패턴을 무한히 이어 붙인 것을 기준으로 한다. 예를 들어, 2ドル \times 3$크기의 패턴과 이 패턴을 이어 붙인 그림이다.

그림 1: 2ドル \times 3$크기의 패턴

그림 2 : 위의 패턴을 무한히 이어 붙인 것의 일부. 빨간 직사각형은 위의 패턴을 나타내며, 뒤틀림 없이 그대로 맞춰서 이어 붙인다.

격자는 시술할 때 없어지므로 이상하게 시술이 될 것 같다는 걱정은 하지 않으셔도 됩니다.

정우는 먼저 패턴을 정한 후, 무한히 이어 붙여보는 것을 해보려고 한다. 이 때, 중요한 것은 무한히 이어 붙인 다음 각 칸이 이루는 연결 성분의 크기이다. 이것은 미관상 매우 중요한 문제다. 만약 색이 같은 두 칸이 상하좌우로 붙어있다면 그 두 칸은 같은 연결 성분에 들어가는 것이다.

그림 2에서 각 칸이 속한 연결 성분의 크기를 구해보면, 검은색 칸이 속한 연결 성분의 크기는 모두 24ドル$이고, 흰색 칸이 속한 연결 성분에는 무한히 많은 칸이 포함된다. 즉, 크기가 무한대이다. 주어진 패턴을 무한히 이어 붙인 다음 각 칸이 속한 연결 성분의 크기를 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 얼룩 패턴의 크기를 나타내는 두 정수 $N,ドル $M$(1ドル ≤ N, M ≤ 400$)이 공백 하나로 구분되어 주어진다.

다음 $N$개 줄의 각 줄에는 길이가 $M$인 문자열이 주어진다. 모든 문자열은 ‘B’또는 ‘W’로 이루어진 문자열이다. ‘B’는 검은색, ‘W’는 흰색을 나타낸다.

출력

총 $N$개의 줄에 걸쳐 정답을 출력한다. $i$번째 줄에는 $M$개의 수가 공백 하나로 구분되어 출력되어야 하고, 그 중 $j$번째 수는 입력에서 $i$번째 행 $j$번째 열에 주어진 칸이 속한 연결 성분의 크기여야 한다. 만약 그 크기가 무한히 크다면 -1로 출력해야 한다.

제한

힌트