JOI 君は IOI の懇親会に参加している．懇親会ではサンドイッチが縦 $R$ 行，横 $C$ 列の正方形のマス目に沿って配置されていた．サンドイッチは $2$ 辺がマス目の $1$ 辺の長さに等しい直角二等辺三角形の形をしており，それぞれのマスには $2$ 個のサンドイッチが斜辺が接するように置かれている．下図はサンドイッチの配置の例を表している．

図 1. サンドイッチの配置の例

以下の 2 つの条件を同時に満たすサンドイッチは，取ることができない．

• 斜辺が，まだ取られていない他のサンドイッチに接している．
• 斜辺以外の $2$ 本の辺のうち少なくとも $1$ 本が，まだ取られていない他のサンドイッチに接している．

これ以外のサンドイッチは取ることができる．

サンドイッチが全く取られていない状態を初期状態とする．初期状態から，あるサンドイッチを取るためには，他のいくつかのサンドイッチを取らなければいけないかもしれない．サンドイッチの配置によっては，取ることができないサンドイッチもあるかもしれない．

JOI 君は，同じマスに置かれている $2$ 個のサンドイッチを両方とも食べたいと思っている．どのマスに置かれているサンドイッチを食べるかは，まだ決めていない．

初期状態から，あるマスの $2$ 個のサンドイッチを両方取るときに，取らなければならないサンドイッチの個数の最小値が気になる．

課題

サンドイッチの配置が与えられたとき，それぞれのマスについて，そのマスの $2$ 個のサンドイッチを，初期状態からいくつかのサンドイッチを取ることによって両方取ることができるか判定し，もし取ることができる場合は取る必要のあるサンドイッチの個数の最小値を求めるプログラムを作成せよ．ただし，サンドイッチの個数には，目的の $2$ 個のサンドイッチも含めて数える．

入力

標準入力から以下のデータを読み込め．

• 1 行目には，整数 $R,C$ が空白を区切りとして書かれている．これらは，サンドイッチが縦 $R$ 行，横 $C$ 列の正方形のマス目に沿って配置されていることを表す．
• 続く $R$ 行のうちの $i$ 行目（$1 \le i \le R$）には，$C$ 文字からなる文字列が書かれている．各文字は ‘N’ または ‘Z’ である．この文字列の左から $j$ 文字目（$1 \le j \le C$）は，上から $i$ 行目，左から $j$ 列目のマスのサンドイッチの配置を表している．‘N’, ‘Z’ はそれぞれ以下のような配置を表している．

図 2. 各マスのサンドイッチの配置

出力

標準出力に $R$ 行で出力せよ．$i$ 行目（$1 \le i \le R$）には，$C$ 個の整数を空白を区切りとして出力せよ．$j$ 番目（$1 \le j \le C$）の整数として，上から $i$ 行目，左から $j$ 列目のマスのサンドイッチ $2$ 個を両方取るときに取る必要があるサンドイッチの個数の最小値を出力せよ．もし，取ることができない場合は，$-1$ を出力せよ．

制約

すべての入力データは以下の条件を満たす．

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

小課題

小課題 1 [35 点]

以下の条件を満たす．

• $R \le 50$．
• $C \le 50$．

小課題 2 [65 点]

追加の制限はない．

入出力例

入力 1

2 3
NZN
ZZN

出力 1

10 8 2
8 6 4

注記

入力例 1 のサンドイッチの配置は，問題文中の図 1 に対応する．

例えば，上から $2$ 行目，左から $2$ 列目のマスの $2$ 個のサンドイッチを取るには，以下の順にサンドイッチを取っていけばよい．

• 上から $1$ 行目，左から $3$ 列目のマスの右上のサンドイッチを取る．
• 上から $1$ 行目，左から $3$ 列目のマスの左下のサンドイッチを取る．
• 上から $2$ 行目，左から $3$ 列目のマスの右上のサンドイッチを取る．
• 上から $2$ 行目，左から $3$ 列目のマスの左下のサンドイッチを取る．
• 上から $2$ 行目，左から $2$ 列目のマスの右下のサンドイッチを取る．
• 上から $2$ 行目，左から $2$ 列目のマスの左上のサンドイッチを取る．

合計で $6$ 個のサンドイッチを取ることになり，これが最小であるため $6$ を出力する．

入力 2

2 2
NZ
ZN

出力 2

-1 -1
-1 -1

注記

この場合，いずれのサンドイッチも取ることができない．

入力 3

5 5
NZZZN
NNNZN
NNZNN
NZNNN
NZZZN

出力 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