JOI đang tham dự buổi giao lưu của IOI. Tại buổi giao lưu, 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 sandwich có hình tam giác vuông cân với hai cạnh có độ dài bằng cạnh của một ô vuông. Trong mỗi ô có hai chiếc sandwich được đặt sao cho hai cạnh huyền tiếp xúc nhau. Hình dưới đây minh họa một cách xếp sandwich.

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

Không thể lấy một chiếc sandwich 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 sandwich khác chưa được lấy đi.
• Ít nhất một trong hai cạnh không phải cạnh huyền của nó tiếp xúc với một chiếc sandwich khác chưa được lấy đi.

Các chiếc sandwich khác đều có thể được lấy đi.

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

JOI muốn ăn cả hai chiếc sandwich trong cùng một ô. Cậu chưa quyết định sẽ ăn sandwich trong ô nào.

Cậu muốn biết số sandwich ít nhất cần lấy đi từ trạng thái ban đầu để lấy được cả hai chiếc sandwich trong một ô.

Nhiệm vụ

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

Dữ liệu vào

Đọc dữ liệu sau từ đầu vào chuẩn.

• Dòng đầu tiên chứa hai số nguyên $R,C$ cách nhau bởi dấu cách. Chúng cho biết sandwich được xếp trên một lưới ô vuông gồm $R$ hàng và $C$ cột.
• Dòng thứ $i$ ($1 \le i \le R$) trong $R$ dòng tiếp theo chứa một chuỗi 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$) của chuỗi biểu diễn cách xếp sandwich trong ô ở hàng thứ $i$ từ trên xuống và cột thứ $j$ từ trái sang. N và Z lần lượt biểu diễn các cách xếp như dưới đây.

Hình 2. Cách xếp sandwich trong mỗi ô

Dữ liệu ra

In $R$ dòng ra đầu ra chuẩn. 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ố nguyên thứ $j$ ($1 \le j \le C$) là số sandwich ít nhất cần lấy đi để lấy được cả hai chiếc sandwich trong ô ở hàng thứ $i$ từ trên xuống và cột thứ $j$ từ trái sang. Nếu không thể lấy được, hãy in $-1$.

Giới hạn

Mọi dữ liệu vào đều thỏa mãn các điều kiện sau.

• $1 \le R \le 400$.
• $1 \le C \le 400$.

Nhiệm vụ con

Nhiệm vụ con 1 [35 điểm]

Thỏa mãn các điều kiện sau.

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

Nhiệm vụ con 2 [65 điểm]

Không có giới hạn bổ sung.

Ví dụ

Dữ liệu vào 1

2 3
NZN
ZZN

Dữ liệu ra 1

10 8 2
8 6 4

Ghi chú

Cách xếp sandwich trong ví dụ 1 tương ứng với Hình 1 trong đề bài.

Chẳng hạn, để lấy hai chiếc sandwich trong ô ở hàng thứ 2 từ trên xuống và cột thứ 2 từ trái sang, có thể lấy sandwich theo thứ tự sau.

• Lấy chiếc sandwich ở góc trên bên phải của ô ở hàng thứ 1 từ trên xuống và cột thứ 3 từ trái sang.
• Lấy chiếc sandwich ở góc dưới bên trái của ô ở hàng thứ 1 từ trên xuống và cột thứ 3 từ trái sang.
• Lấy chiếc sandwich ở góc trên bên phải của ô ở hàng thứ 2 từ trên xuống và cột thứ 3 từ trái sang.
• Lấy chiếc sandwich ở góc dưới bên trái của ô ở hàng thứ 2 từ trên xuống và cột thứ 3 từ trái sang.
• Lấy chiếc sandwich ở góc dưới bên phải của ô ở hàng thứ 2 từ trên xuống và cột thứ 2 từ trái sang.
• Lấy chiếc sandwich ở góc trên bên trái của ô ở hàng thứ 2 từ trên xuống và cột thứ 2 từ trái sang.

Tổng cộng cần lấy 6 chiếc sandwich. Đây là số lượng ít nhất, nên in 6.

Dữ liệu vào 2

2 2
NZ
ZN

Dữ liệu ra 2

-1 -1
-1 -1

Ghi chú

Trong trường hợp này, không thể lấy bất kỳ chiếc sandwich nào.

Dữ liệu vào 3

5 5
NZZZN
NNNZN
NNZNN
NZNNN
NZZZN

Dữ liệu ra 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