Sandwich (Translated)

JOI Spring Training Camp 2015/16
Original Statement / Submission Site

Problem Statement

JOI-kun is attending an IOI social gathering. At the gathering, sandwiches are arranged on a rectangular grid with R rows and C columns.

Each sandwich has the shape of a right isosceles triangle whose two perpendicular sides have the same length as one side of a grid cell. Two sandwiches are placed in each cell so that their hypotenuses touch each other.

Example sandwich arrangement on the grid — Figure 1. Example sandwich arrangement.

A sandwich cannot be taken if both of the following conditions hold:

Its hypotenuse is touching another sandwich that has not yet been taken.
At least one of its two non-hypotenuse sides is touching another sandwich that has not yet been taken.

Any sandwich that does not satisfy both conditions may be taken.

Initially, no sandwiches have been taken. To take a particular sandwich, it may first be necessary to take several other sandwiches. Depending on the arrangement, some sandwiches may never be possible to take.

JOI-kun wants to eat both sandwiches placed in the same cell, but he has not yet decided which cell to choose. For each cell, he wants to know the minimum number of sandwiches that must be taken, starting from the initial state, in order to take both sandwiches in that cell.

Task

Given the sandwich arrangement, determine for every cell whether it is possible to take both sandwiches in that cell. If it is possible, compute the minimum number of sandwiches that must be taken, including the two target sandwiches themselves.

Input

The input is given as follows:

The first line contains two integers R and C, representing the number of rows and columns of the grid.
Each of the next R lines contains a string of C characters. Each character is either N or Z and represents the orientation of the two sandwiches in that cell.

The characters N and Z correspond to the two possible diagonal orientations shown in Figure 2 of the original statement.

The two sandwich orientations represented by N and Z — Figure 2. The sandwich orientations represented by `N` and `Z`.

Output

Output R lines. The i-th line must contain C integers separated by spaces.

The j-th integer on the i-th line should be the minimum number of sandwiches that must be taken in order to take both sandwiches in the cell at row i, column j. Output -1 if it is impossible.

Constraints

1 ≤ R ≤ 400
1 ≤ C ≤ 400

Subtasks

Subtask 1 [35 points]: R ≤ 50 and C ≤ 50.
Subtask 2 [65 points]: No additional constraints.

Sample Input 1

2 3
NZN
ZZN

Sample Output 1

10 8 2
8 6 4

Explanation of Sample Output 1

The sandwich arrangement in Sample Input 1 corresponds to Figure 1 in the original statement.

For example, to take both sandwiches in the cell at row 2, column 2, the sandwiches can be taken in the following order:

Take the upper-right sandwich in the cell at row 1, column 3.
Take the lower-left sandwich in the cell at row 1, column 3.
Take the upper-right sandwich in the cell at row 2, column 3.
Take the lower-left sandwich in the cell at row 2, column 3.
Take the lower-right sandwich in the cell at row 2, column 2.
Take the upper-left sandwich in the cell at row 2, column 2.

A total of 6 sandwiches are taken, and this is the minimum possible number. Therefore, the output for that cell is 6.

Sample Input 2

2 2
NZ
ZN

Sample Output 2

-1 -1
-1 -1

In this case, none of the sandwiches can be taken.

Sample Input 3

5 5
NZZZN
NNNZN
NNZNN
NZNNN
NZZZN

Sample Output 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