JOI 君正在参加 IOI 的联谊会。在联谊会上，三明治沿着 $R$ 行 $C$ 列的方形网格排列。每个三明治的形状都是直角等腰三角形，其两条直角边等于网格的边长，每个网格中放置了两个三明治，使它们的斜边相接。下图展示了三明治排列的一个例子。

图 1. 三明治排列示例

同时满足以下两个条件的三明治无法被取走： 斜边与另一个尚未被取走的三明治相接。 除斜边外的两条边中，至少有一条边与另一个尚未被取走的三明治相接。

除此之外的三明治都可以被取走。

初始状态为没有任何三明治被取走的状态。从初始状态开始，为了取走某个三明治，可能需要先取走其他一些三明治。根据三明治的排列方式，可能存在无法取走的三明治。

JOI 君想吃掉同一个网格中的两个三明治。他还没有决定要吃哪个网格里的三明治。

他想知道，从初始状态开始，要取走某个网格中的两个三明治，所需要取走的三明治数量的最小值是多少。

题目描述

给定三明治的排列，对于每个网格，判断是否可以通过从初始状态开始取走若干个三明治来取走该网格中的两个三明治。如果可以，求出所需取走的三明治数量的最小值。注意，三明治的数量包括目标的那两个三明治。

输入格式

从标准输入读取以下数据： 第 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$ 列网格中的两个三明治时，所需取走的三明治数量的最小值。如果无法取走，则输出 $-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

输出

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

输出

-1 -1
-1 -1

说明： 在这种情况下，任何三明治都无法被取走。

样例 3

输入

5 5
NZZZN
NNNZN
NNZNN
NZNNN
NZZZN

输出

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