Description

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

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

1. 与该小三明治在同一个三明治中的另一个三明治还没被吃掉；

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

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

1<=R,C<=400

Input Format

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

Output Format

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

2 3
NZN
ZZN​

10 8 2
8 6 4​

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

Hint

样例1大概吃的顺序是这样的：

(1,3)→(2,3)→(2,2)→(1,2)→(1,1)或者:

(1,3)→(2,3)→(2,2)→(2,1)→(1,1)