JOI participe à la réception de l'IOI. Des sandwichs y sont disposés sur une grille de cases carrées comportant $R$ lignes et $C$ colonnes. Chaque sandwich a la forme d'un triangle rectangle isocèle dont les deux côtés de l'angle droit ont la même longueur que le côté d'une case. Chaque case contient deux sandwichs dont les hypoténuses se touchent. La figure ci-dessous montre un exemple de disposition.

Figure 1. Exemple de disposition des sandwichs

On ne peut pas prendre un sandwich qui satisfait simultanément les deux conditions suivantes.

• Son hypoténuse touche un autre sandwich qui n'a pas encore été pris.
• Au moins un de ses deux autres côtés touche un autre sandwich qui n'a pas encore été pris.

Tout autre sandwich peut être pris.

L'état dans lequel aucun sandwich n'a encore été pris est appelé l'état initial. Pour prendre un sandwich donné à partir de cet état, il peut être nécessaire d'en prendre d'autres auparavant. Selon la disposition, certains sandwichs peuvent être impossibles à prendre.

JOI souhaite manger les deux sandwichs d'une même case. Il n'a pas encore choisi cette case.

Il se demande quel est le nombre minimal de sandwichs à prendre, à partir de l'état initial, pour obtenir les deux sandwichs d'une case donnée.

Tâche

Étant donnée la disposition des sandwichs, écrivez un programme qui détermine, pour chaque case, s'il est possible de prendre ses deux sandwichs en prenant un certain nombre de sandwichs à partir de l'état initial et, si c'est possible, calcule le nombre minimal de sandwichs à prendre. Ce nombre doit inclure les deux sandwichs recherchés.

Entrée

Lisez les données suivantes sur l'entrée standard.

• La première ligne contient deux entiers $R,C$ séparés par un espace. Ils indiquent que les sandwichs sont disposés sur une grille de cases carrées comportant $R$ lignes et $C$ colonnes.
• La $i$-ème ligne ($1 \le i \le R$) parmi les $R$ lignes suivantes contient une chaîne de $C$ caractères. Chaque caractère est N ou Z. Le $j$-ème caractère en partant de la gauche ($1 \le j \le C$) décrit la disposition des sandwichs dans la case de la $i$-ème ligne depuis le haut et de la $j$-ème colonne depuis la gauche. N et Z correspondent aux dispositions suivantes.

Figure 2. Disposition des sandwichs dans chaque case

Sortie

Écrivez $R$ lignes sur la sortie standard. La $i$-ème ligne ($1 \le i \le R$) doit contenir $C$ entiers séparés par des espaces. Le $j$-ème entier ($1 \le j \le C$) doit être le nombre minimal de sandwichs à prendre pour obtenir les deux sandwichs de la case de la $i$-ème ligne depuis le haut et de la $j$-ème colonne depuis la gauche. Si cela est impossible, écrivez $-1$.

Contraintes

Toutes les données d'entrée satisfont les conditions suivantes.

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

Sous-tâches

Sous-tâche 1 [35 points]

Les conditions suivantes sont satisfaites.

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

Sous-tâche 2 [65 points]

Il n'y a pas de contrainte supplémentaire.

Exemples

Entrée 1

2 3
NZN
ZZN

Sortie 1

10 8 2
8 6 4

Remarque

La disposition des sandwichs du premier exemple correspond à la figure 1 de l'énoncé.

Par exemple, pour prendre les deux sandwichs de la case de la deuxième ligne depuis le haut et de la deuxième colonne depuis la gauche, on peut procéder dans l'ordre suivant.

• Prendre le sandwich en haut à droite de la case de la première ligne et de la troisième colonne.
• Prendre le sandwich en bas à gauche de la case de la première ligne et de la troisième colonne.
• Prendre le sandwich en haut à droite de la case de la deuxième ligne et de la troisième colonne.
• Prendre le sandwich en bas à gauche de la case de la deuxième ligne et de la troisième colonne.
• Prendre le sandwich en bas à droite de la case de la deuxième ligne et de la deuxième colonne.
• Prendre le sandwich en haut à gauche de la case de la deuxième ligne et de la deuxième colonne.

On prend ainsi 6 sandwichs au total. Ce nombre étant minimal, on affiche 6.

Entrée 2

2 2
NZ
ZN

Sortie 2

-1 -1
-1 -1

Remarque

Dans ce cas, aucun sandwich ne peut être pris.

Entrée 3

5 5
NZZZN
NNNZN
NNZNN
NZNNN
NZZZN

Sortie 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