JOI está participando en una reunión social de la IOI. En la reunión, los sándwiches estaban dispuestos sobre una cuadrícula de celdas cuadradas de $R$ filas y $C$ columnas. Cada sándwich tiene forma de triángulo rectángulo isósceles, con sus dos catetos de la misma longitud que el lado de una celda. En cada celda hay dos sándwiches colocados de modo que sus hipotenusas se tocan. La figura siguiente muestra un ejemplo de disposición.

Figura 1. Ejemplo de disposición de los sándwiches

No se puede retirar un sándwich que cumpla simultáneamente las dos condiciones siguientes.

• Su hipotenusa está en contacto con otro sándwich que todavía no se ha retirado.
• Al menos uno de sus otros dos lados está en contacto con otro sándwich que todavía no se ha retirado.

Se puede retirar cualquier otro sándwich.

Llamamos estado inicial al estado en el que no se ha retirado ningún sándwich. Para retirar un sándwich determinado desde el estado inicial, puede ser necesario retirar antes otros sándwiches. Dependiendo de la disposición, también puede haber sándwiches que no se puedan retirar.

JOI quiere comerse los dos sándwiches de una misma celda. Todavía no ha decidido de qué celda los comerá.

Quiere saber el número mínimo de sándwiches que deben retirarse para retirar los dos sándwiches de una determinada celda desde el estado inicial.

Tarea

Dada la disposición de los sándwiches, escribe un programa que determine, para cada celda, si es posible retirar sus dos sándwiches retirando algunos sándwiches desde el estado inicial y, si es posible, calcule el número mínimo de sándwiches que deben retirarse. En ese número también se incluyen los dos sándwiches deseados.

Entrada

Lee los siguientes datos de la entrada estándar.

• La primera línea contiene los enteros $R,C$ separados por un espacio. Indican que los sándwiches están dispuestos en una cuadrícula de celdas cuadradas de $R$ filas y $C$ columnas.
• La línea $i$ ($1\le i\le R$) de las siguientes $R$ líneas contiene una cadena de $C$ caracteres. Cada carácter es N o Z. El carácter $j$ ($1\le j\le C$) desde la izquierda representa la disposición de los sándwiches en la celda de la fila $i$ desde arriba y la columna $j$ desde la izquierda. N y Z representan, respectivamente, las disposiciones siguientes.

Figura 2. Disposición de los sándwiches en cada celda

Salida

Escribe $R$ líneas en la salida estándar. En la línea $i$ ($1\le i\le R$), escribe $C$ enteros separados por espacios. El entero $j$ ($1\le j\le C$) debe ser el número mínimo de sándwiches que deben retirarse para retirar los dos sándwiches de la celda de la fila $i$ desde arriba y la columna $j$ desde la izquierda. Si no es posible, escribe $-1$.

Restricciones

Todos los datos de entrada cumplen las siguientes condiciones.

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

Subtareas

Subtarea 1 [35 puntos]

Se cumplen las siguientes condiciones.

• $R\le50$.
• $C\le50$.

Subtarea 2 [65 puntos]

No hay restricciones adicionales.

Ejemplos

Entrada 1

2 3
NZN
ZZN

Salida 1

10 8 2
8 6 4

Nota

La disposición de los sándwiches de la entrada 1 corresponde a la figura 1 del enunciado.

Por ejemplo, para retirar los dos sándwiches de la celda de la fila $2$ desde arriba y la columna $2$ desde la izquierda, basta con retirarlos en el siguiente orden:

• Retira el sándwich superior derecho de la celda de la fila $1$ y la columna $3$.
• Retira el sándwich inferior izquierdo de la celda de la fila $1$ y la columna $3$.
• Retira el sándwich superior derecho de la celda de la fila $2$ y la columna $3$.
• Retira el sándwich inferior izquierdo de la celda de la fila $2$ y la columna $3$.
• Retira el sándwich inferior derecho de la celda de la fila $2$ y la columna $2$.
• Retira el sándwich superior izquierdo de la celda de la fila $2$ y la columna $2$.

En total se retiran 6 sándwiches y este es el mínimo, por lo que se escribe 6.

Entrada 2

2 2
NZ
ZN

Salida 2

-1 -1
-1 -1

Nota

En este caso, no se puede retirar ningún sándwich.

Entrada 3

5 5
NZZZN
NNNZN
NNZNN
NZNNN
NZZZN

Salida 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