题目描述

题目译自 JOISC 2016 Day2 T2 「サンドイッチ」

JOI 君去参加了 IOI 联♂谊会，会场有一张桌子，桌上有 $R \times C$ 个三明治被摆放成 $R$ 行 $C$ 列。每个三明治都被沿主对角线或者次对角线分割成两个小三明治。

一个小三明治仅当以下两种情况都满足时才不能被吃掉：

1. 与该小三明治在同一个三明治中的另一个三明治还没被吃掉；
2. 与该小三明治两条直角边相邻的另外两个小三明治中有一个没有被吃掉。

现在 JOI 君想问你，他吃掉每一个三明治时最少要吃掉多少个小三明治？

输入格式

第一行有两个整数 $R$ 和 $C$ ，表示三明治桌子有 $R$ 行 $C$ 列。
之后的 $R$ 行，每行 $C$ 个字母，其中字母 N 表示沿主对角线切割，Z 表示沿次对角线切割。

输出格式

输出包括 $R$ 行，每行 $C$ 个数字，第 $i$ 行 $j$ 列表示吃完第 $i$ 行 $j$ 列的三明治时最少吃了几个小三明治，如果吃不到，输出 $-1$。

样例 1

input

2 3
NZN
ZZN

output

10 8 2
8 6 4

大概吃的顺序是这样的： $(1,3)$ $\rightarrow$ $(2,3)$ $\rightarrow$ $(2,2)$ $\rightarrow$ $(1,2)$ $\rightarrow$ $(1,1)$ 或者： $(1,3)$ $\rightarrow$ $(2,3)$ $\rightarrow$ $(2,2)$ $\rightarrow$ $(2,1)$ $\rightarrow$ $(1,1)$

样例 2

input

5 5
NZZZN
NNNZN
NNZNN
NZNNN
NZZZN

output

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

数据范围与提示

对于全部的数据，$1 \leq R,C \leq 400 $。

具体子任务限制及得分情况如下表：