JOI 君正參加 IOI 嘅聯誼會。會上嘅三文治沿住一個 $R$ 行、$C$ 列嘅正方形方格擺放。每件三文治都係等腰直角三角形，兩條直角邊嘅長度等於方格嘅邊長。每格放咗兩件三文治，兩件嘅斜邊互相貼住。下圖係三文治擺放方式嘅一個例子。

圖 1：三文治擺放方式嘅例子

同時符合以下兩個條件嘅三文治，唔可以攞走。

• 斜邊貼住另一件仲未攞走嘅三文治。
• 除咗斜邊之外，另外兩條邊之中至少有一條貼住另一件仲未攞走嘅三文治。

其餘三文治都可以攞走。

將完全未攞走任何三文治嘅狀態叫做初始狀態。由初始狀態開始，要攞走某件三文治，可能要先攞走其他幾件三文治。視乎擺放方式，亦可能有啲三文治係無法攞走嘅。

JOI 君想食晒同一格入面嘅兩件三文治，但仲未決定食邊一格。

佢想知道，由初始狀態開始，要將某一格入面嘅兩件三文治都攞走，最少要攞走幾多件三文治。

任務

畀定三文治嘅擺放方式，請寫一個程式，對每一格判斷可唔可以由初始狀態開始，透過攞走一啲三文治，將嗰格入面嘅兩件三文治都攞走。如果可以，就求出最少要攞走幾多件三文治。計算件數時，亦要包括目標嗰兩件三文治。

輸入格式

由標準輸入讀取以下資料。

• 第一行有兩個以空格分隔嘅整數 $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$ 列嗰格嘅兩件三文治都攞走，最少要攞走幾多件三文治。如果無法攞走，就輸出 -1。

資料範圍

所有輸入資料都符合以下條件。

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

子任務

子任務 1 [35 分]

符合以下條件。

• $R\le50$。
• $C\le50$。

子任務 2 [65 分]

冇額外限制。

樣例

輸入格式 1

2 3
NZN
ZZN

輸出格式 1

10 8 2
8 6 4

說明

樣例 1 嘅三文治擺放方式對應題目入面嘅圖 1。

例如，要攞走由上面數第 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