小西和秀苑酱饼

题号：NC215150
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

这样的叫主对角线：

这样的叫副对角线，不是方阵的情况下和主对角线同理：

小西一直都很喜欢吃秀苑的早餐酱饼，这里我们假设酱饼都是整齐的方形。

现在她买了 $n\times m$ 张酱饼整齐的拼成了一个 $n\times m$ 的矩阵，每张酱饼都可以被从主对角线或者副对角线切一刀变成两张小酱饼。

如果小酱饼同时满足以下条件那么就不能被吃：

1. 与该小酱饼在同一个酱饼中的另一个小酱饼还没被吃掉；

2. 与该小酱饼两条直角边相邻的另外两个小酱饼中至少有一个没有被吃掉。

现在小西想知道对于桌子上这些酱饼而言，在吃完每个位置的酱饼时，最少已经吃了多少个小酱饼。

注意，分析题目后你会发现应当存在吃的顺序，所以才有“吃完第 $(i,j)$ 位置的酱饼时，已经吃了多少个小酱饼”的问题。这里的结果是对于所有可能的顺序而言，每个位置的答案。如果对于所有可能的顺序都不可能吃到 $(i,j)$ ，那么输出-1。

第一行输入两个整数和
接下来行，每行有个字符，其中第行的第个如果为N就表示把的酱饼按主对角线切，如果是Z就按副对角线切。
切酱饼的操作都只作用于当前的这个位置的酱饼。

输出行，每行有个空格分隔的整数表示答案，

示例1

复制

2 3
NZN
ZZN

复制

10 8 2
8 6 4

吃的顺序可以是或者

示例2

复制

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