두 배 놀이

두 배 놀이는 게임이라기보다 퍼즐에 가깝다. 놀이판은 단위 정사각형 칸으로 나뉜 직사각형이다. 처음에 어떤 칸에는 토큰이 하나 놓여 있고, 나머지 칸은 비어 있다.

목표는 한 칸에 토큰을 최대한 많이 쌓는 것이다. 할 수 있는 동작은 하나뿐이다. 변을 맞대고 있는 두 칸의 토큰 개수가 같고 그 개수가 1 이상이면, 한 칸의 토큰을 모두 다른 칸으로 옮길 수 있다.

놀이판의 처음 상태가 주어지면 칸마다 그 칸에 모을 수 있는 토큰의 최대 개수를 구하는 프로그램을 작성하시오.

첫 줄에 놀이판의 행 개수 $n$과 열 개수 $m$이 주어진다 ($1 \le n, m \le 200$).

다음 $n$개 줄에는 각각 0과 1로 이루어진 길이 $m$의 문자열이 주어진다. 1은 토큰이 놓인 칸, 0은 빈 칸이다.

$n$개 줄에 각각 $m$개의 정수를 공백 하나로 구분해 출력한다. $i$번째 줄의 $j$번째 수는 주어진 처음 상태에서 시작해 $i$행 $j$열 칸에 모을 수 있는 토큰의 최대 개수다.

칸마다 답을 따로 세며, 어느 칸이든 같은 처음 상태에서 시작한다. 동작을 한 번도 하지 않아도 되므로 토큰이 놓인 칸의 답은 1 이상이고, 빈 칸의 답은 0이다.

첫 번째 예제의 놀이판에서 둘째 줄 넷째 칸에 토큰 4개를 모으는 과정이다. 먼저 첫째 줄 셋째 칸의 토큰을 넷째 칸으로 옮기면 첫째 줄 넷째 칸에 2개가 쌓인다. 다음으로 둘째 줄 셋째 칸의 토큰을 넷째 칸으로 옮기면 둘째 줄 넷째 칸에도 2개가 쌓인다. 이제 두 칸은 세로로 맞닿아 있고 개수가 같으므로, 첫째 줄 넷째 칸의 2개를 둘째 줄 넷째 칸으로 옮겨 4개를 만든다.