JOI is attending an IOI social gathering. At the gathering, sandwiches are arranged along a grid of $R$ rows and $C$ columns. Each sandwich is in the shape of a right isosceles triangle with two sides equal to the length of a grid cell side, and each cell contains two sandwiches placed such that their hypotenuses are touching. The figure below shows an example of the sandwich arrangement.

Figure 1. Example of sandwich arrangement

A sandwich cannot be taken if it satisfies both of the following conditions: Its hypotenuse is touching another sandwich that has not been taken yet. At least one of its two sides other than the hypotenuse is touching another sandwich that has not been taken yet.

Sandwiches other than these can be taken.

The state where no sandwiches have been taken is the initial state. To take a certain sandwich from the initial state, it may be necessary to take other sandwiches first. Depending on the arrangement of the sandwiches, some sandwiches may not be able to be taken at all.

JOI wants to eat both sandwiches placed in the same cell. He has not yet decided which cell's sandwiches to eat.

He is interested in the minimum number of sandwiches that must be taken to obtain both sandwiches in a certain cell from the initial state.

Task

Given the arrangement of the sandwiches, for each cell, determine if it is possible to take both sandwiches in that cell by taking some sandwiches from the initial state. If it is possible, find the minimum number of sandwiches that need to be taken. Note that the number of sandwiches should include the two target sandwiches themselves.

Input

Read the following data from standard input: The first line contains two space-separated integers $R$ and $C$. These represent that the sandwiches are arranged along a grid of $R$ rows and $C$ columns. The $i$-th line ($1 \le i \le R$) of the following $R$ lines contains a string of length $C$. Each character is either 'N' or 'Z'. The $j$-th character ($1 \le j \le C$) of this string represents the arrangement of the sandwiches in the cell at the $i$-th row from the top and $j$-th column from the left. 'N' and 'Z' represent the following arrangements, respectively.

Figure 2. Sandwich arrangement in each cell

Output

Output $R$ lines to standard output. The $i$-th line ($1 \le i \le R$) should contain $C$ space-separated integers. The $j$-th integer ($1 \le j \le C$) should be the minimum number of sandwiches that need to be taken to obtain both sandwiches in the cell at the $i$-th row from the top and $j$-th column from the left. If it is not possible to take them, output -1.

Constraints

All input data satisfies the following conditions: $1 \le R \le 400$ $1 \le C \le 400$

Subtasks

Subtask 1 [35 points]

• $R \le 50$
• $C \le 50$

Subtask 2 [65 points]

• No additional constraints.

Examples

Input 1

2 3
NZN
ZZN

Output 1

10 8 2
8 6 4

Note 1

The sandwich arrangement in Example 1 corresponds to Figure 1 in the problem description. For example, to take the two sandwiches in the cell at the 2nd row from the top and 2nd column from the left, one can take the sandwiches in the following order: Take the top-right sandwich of the cell at the 1st row, 3rd column. Take the bottom-left sandwich of the cell at the 1st row, 3rd column. Take the top-right sandwich of the cell at the 2nd row, 3rd column. Take the bottom-left sandwich of the cell at the 2nd row, 3rd column. Take the bottom-right sandwich of the cell at the 2nd row, 2nd column. Take the top-left sandwich of the cell at the 2nd row, 2nd column.

A total of 6 sandwiches are taken, and since this is the minimum, 6 is output.

Input 2

2 2
NZ
ZN

Output 2

-1 -1
-1 -1

Note 2

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

Input 3

5 5
NZZZN
NNNZN
NNZNN
NZNNN
NZZZN

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