Sandwich

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

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

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

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

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

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

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

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

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

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

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

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

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

• 1 ≦ R ≦ 400．
• 1 ≦ C ≦ 400．