JOI está a participar numa confraternização da IOI. Na confraternização, as sanduíches estão dispostas numa grelha de células quadradas com $R$ linhas e $C$ colunas. Cada sanduíche tem a forma de um triângulo retângulo isósceles cujos dois catetos têm o mesmo comprimento que o lado de uma célula. Em cada célula estão colocadas duas sanduíches com as hipotenusas encostadas uma à outra. A figura seguinte mostra um exemplo de disposição das sanduíches.

Figura 1. Exemplo de disposição das sanduíches

Não se pode retirar uma sanduíche que satisfaça simultaneamente as duas condições seguintes.

• A sua hipotenusa está encostada a outra sanduíche que ainda não foi retirada.
• Pelo menos um dos seus dois lados que não são a hipotenusa está encostado a outra sanduíche que ainda não foi retirada.

Qualquer outra sanduíche pode ser retirada.

O estado em que nenhuma sanduíche foi retirada é chamado estado inicial. A partir do estado inicial, para retirar uma determinada sanduíche, pode ser necessário retirar primeiro algumas outras sanduíches. Dependendo da disposição, poderá haver sanduíches que não podem ser retiradas.

JOI quer comer ambas as sanduíches colocadas numa mesma célula. Ainda não decidiu de que célula comerá as sanduíches.

Quer saber o número mínimo de sanduíches que é necessário retirar, a partir do estado inicial, para retirar ambas as sanduíches de uma determinada célula.

Tarefa

Dada a disposição das sanduíches, escreva um programa que determine, para cada célula, se é possível retirar ambas as suas sanduíches retirando algumas sanduíches a partir do estado inicial e, se for possível, calcule o número mínimo de sanduíches que é necessário retirar. A contagem deve incluir também as duas sanduíches pretendidas.

Entrada

Leia os seguintes dados da entrada padrão.

• A primeira linha contém os inteiros $R,C$ separados por um espaço. Estes indicam que as sanduíches estão dispostas numa grelha de células quadradas com $R$ linhas e $C$ colunas.
• A linha $i$ ($1 \le i \le R$) das $R$ linhas seguintes contém uma cadeia de $C$ caracteres. Cada carácter é N ou Z. O carácter $j$ a contar da esquerda ($1 \le j \le C$) indica a disposição das sanduíches na célula da linha $i$ a contar de cima e da coluna $j$ a contar da esquerda. N e Z indicam, respetivamente, as seguintes disposições.

Figura 2. Disposição das sanduíches em cada célula

Saída

Escreva $R$ linhas na saída padrão. Na linha $i$ ($1 \le i \le R$), escreva $C$ inteiros separados por espaços. Como inteiro $j$ ($1 \le j \le C$), escreva o número mínimo de sanduíches que é necessário retirar para retirar ambas as sanduíches da célula da linha $i$ a contar de cima e da coluna $j$ a contar da esquerda. Se não for possível retirá-las, escreva $-1$.

Restrições

Todos os dados de entrada satisfazem as seguintes condições.

• $1 \le R \le 400$.
• $1 \le C \le 400$.

Subtarefas

Subtarefa 1 [35 pontos]

São satisfeitas as seguintes condições.

• $R \le 50$.
• $C \le 50$.

Subtarefa 2 [65 pontos]

Não existem restrições adicionais.

Exemplos

Entrada 1

2 3
NZN
ZZN

Saída 1

10 8 2
8 6 4

Nota

A disposição das sanduíches no Exemplo de Entrada 1 corresponde à Figura 1 do enunciado.

Por exemplo, para retirar as duas sanduíches da célula da segunda linha a contar de cima e da segunda coluna a contar da esquerda, podemos retirar as sanduíches na seguinte ordem.

• Retirar a sanduíche superior direita da célula da primeira linha a contar de cima e da terceira coluna a contar da esquerda.
• Retirar a sanduíche inferior esquerda da célula da primeira linha a contar de cima e da terceira coluna a contar da esquerda.
• Retirar a sanduíche superior direita da célula da segunda linha a contar de cima e da terceira coluna a contar da esquerda.
• Retirar a sanduíche inferior esquerda da célula da segunda linha a contar de cima e da terceira coluna a contar da esquerda.
• Retirar a sanduíche inferior direita da célula da segunda linha a contar de cima e da segunda coluna a contar da esquerda.
• Retirar a sanduíche superior esquerda da célula da segunda linha a contar de cima e da segunda coluna a contar da esquerda.

São retiradas 6 sanduíches no total. Como este é o mínimo, a saída é $6$.

Entrada 2

2 2
NZ
ZN

Saída 2

-1 -1
-1 -1

Nota

Neste caso, não se pode retirar nenhuma sanduíche.

Entrada 3

5 5
NZZZN
NNNZN
NNZNN
NZNNN
NZZZN

Saída 3

10 12 14 16 2
8 -1 -1 -1 4
6 -1 -1 -1 6
4 -1 -1 -1 8
2 16 14 12 10