JOI đang tham dự buổi giao lưu của IOI. Tại buổi giao lưu, những chiếc bánh sandwich được xếp trên một lưới ô vuông gồm \(R\) hàng và \(C\) cột. Mỗi chiếc bánh có dạng tam giác vuông cân với hai cạnh góc vuông có độ dài bằng cạnh của một ô. Trong mỗi ô có hai chiếc bánh được đặt sao cho hai cạnh huyền tiếp xúc với nhau. Hình dưới đây minh họa một cách xếp bánh.

Hình 1. Ví dụ về cách xếp bánh sandwich.

Không thể lấy một chiếc bánh nếu đồng thời thỏa mãn cả hai điều kiện sau:

• Cạnh huyền của nó tiếp xúc với một chiếc bánh khác chưa được lấy đi.
• Ít nhất một trong hai cạnh còn lại của nó tiếp xúc với một chiếc bánh khác chưa được lấy đi.

Mọi chiếc bánh không thỏa mãn đồng thời hai điều kiện trên đều có thể được lấy đi.

Gọi trạng thái chưa có chiếc bánh nào được lấy đi là trạng thái ban đầu. Xuất phát từ trạng thái ban đầu, để lấy một chiếc bánh nào đó, có thể cần phải lấy một số chiếc bánh khác trước. Tùy vào cách xếp bánh, cũng có thể có những chiếc bánh không thể lấy được.

JOI muốn ăn cả hai chiếc bánh nằm trong cùng một ô, nhưng chưa quyết định sẽ chọn ô nào. Cậu muốn biết, xuất phát từ trạng thái ban đầu, số chiếc bánh ít nhất phải lấy để lấy được cả hai chiếc bánh trong một ô nhất định.

Yêu cầu

Cho cách xếp bánh, hãy viết chương trình xác định với mỗi ô xem có thể lấy được cả hai chiếc bánh trong ô đó bằng cách lần lượt lấy một số chiếc bánh từ trạng thái ban đầu hay không. Nếu có thể, hãy tìm số chiếc bánh ít nhất phải lấy. Số lượng này bao gồm cả hai chiếc bánh trong ô cần lấy.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên \(R, C\), cách nhau bởi dấu cách, cho biết bánh được xếp trên một lưới ô vuông gồm \(R\) hàng và \(C\) cột.
• Trong \(R\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le R\)) chứa một xâu gồm \(C\) ký tự, mỗi ký tự là N hoặc Z. Ký tự thứ \(j\) từ trái sang (\(1 \le j \le C\)) mô tả cách xếp bánh trong ô ở hàng thứ \(i\) từ trên xuống, cột thứ \(j\) từ trái sang. Hai ký tự N và Z lần lượt biểu diễn các cách xếp trong hình dưới đây.

Hình 2. Cách xếp bánh sandwich trong mỗi ô: N ở bên trái, Z ở bên phải.

Dữ liệu ra

In ra đầu ra chuẩn \(R\) dòng. Dòng thứ \(i\) (\(1 \le i \le R\)) chứa \(C\) số nguyên, cách nhau bởi dấu cách. Số thứ \(j\) (\(1 \le j \le C\)) là số chiếc bánh ít nhất phải lấy để lấy được cả hai chiếc bánh trong ô ở hàng thứ \(i\) từ trên xuống, cột thứ \(j\) từ trái sang. Nếu không thể lấy được cả hai chiếc bánh trong ô đó, in ra \(-1\).

Ràng buộc

Tất cả dữ liệu vào thỏa mãn các điều kiện sau:

Phân nhóm

1. 35 điểm: \(R \le 50\) và \(C \le 50\).
2. 65 điểm: Không có ràng buộc bổ sung.

Ví dụ

2 3
NZN
ZZN

10 8 2
8 6 4

2 2
NZ
ZN

-1 -1
-1 -1

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