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 \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$ 行的方格中的兩個三明治，可以依照以下順序取走三明治。

• 取走從上數第 $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