JOI-kun sedang menghadiri acara ramah tamah IOI. Pada acara tersebut, sandwich disusun pada kisi persegi dengan $R$ baris dan $C$ kolom. Setiap sandwich berbentuk segitiga siku-siku sama kaki dengan kedua kaki sama panjang dengan sisi satu petak. Pada setiap petak terdapat dua sandwich yang saling bersentuhan pada sisi miringnya. Gambar berikut menunjukkan contoh susunan sandwich.

Gambar 1. Contoh susunan sandwich

Sandwich yang memenuhi kedua kondisi berikut sekaligus tidak dapat diambil.

• Sisi miringnya bersentuhan dengan sandwich lain yang belum diambil.
• Setidaknya satu dari dua sisinya selain sisi miring bersentuhan dengan sandwich lain yang belum diambil.

Sandwich selain itu dapat diambil.

Keadaan ketika belum ada sandwich yang diambil disebut keadaan awal. Untuk mengambil suatu sandwich dari keadaan awal, mungkin perlu mengambil beberapa sandwich lain terlebih dahulu. Bergantung pada susunannya, mungkin juga ada sandwich yang tidak dapat diambil.

JOI-kun ingin memakan kedua sandwich yang berada di petak yang sama. Ia belum menentukan petak mana yang sandwich-nya akan dimakan.

Ia ingin mengetahui jumlah minimum sandwich yang harus diambil agar dapat mengambil kedua sandwich pada suatu petak dari keadaan awal.

Tugas

Diberikan susunan sandwich, tulislah program yang, untuk setiap petak, menentukan apakah kedua sandwich di petak tersebut dapat diambil dengan mengambil beberapa sandwich dari keadaan awal. Jika dapat, hitung jumlah minimum sandwich yang perlu diambil. Jumlah ini juga mencakup kedua sandwich yang dituju.

Masukan

Bacalah data berikut dari masukan standar.

• Baris pertama berisi dua bilangan bulat $R,C$ yang dipisahkan oleh spasi. Ini berarti sandwich disusun pada kisi persegi dengan $R$ baris dan $C$ kolom.
• Baris ke-$i$ ($1 \le i \le R$) dari $R$ baris berikutnya berisi string sepanjang $C$ karakter. Setiap karakter adalah N atau Z. Karakter ke-$j$ dari kiri ($1 \le j \le C$) menunjukkan susunan sandwich pada petak di baris ke-$i$ dari atas dan kolom ke-$j$ dari kiri. N dan Z masing-masing menunjukkan susunan berikut.

Gambar 2. Susunan sandwich pada setiap petak

Keluaran

Tulislah $R$ baris ke keluaran standar. Pada baris ke-$i$ ($1 \le i \le R$), tulislah $C$ bilangan bulat yang dipisahkan oleh spasi. Bilangan ke-$j$ ($1 \le j \le C$) harus berupa jumlah minimum sandwich yang perlu diambil agar kedua sandwich pada petak di baris ke-$i$ dari atas dan kolom ke-$j$ dari kiri dapat diambil. Jika tidak dapat diambil, tulislah $-1$.

Batasan

Semua data masukan memenuhi kondisi berikut.

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

Subsoal

Subsoal 1 [35 poin]

Kondisi berikut dipenuhi.

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

Subsoal 2 [65 poin]

Tidak ada batasan tambahan.

Contoh

Masukan 1

2 3
NZN
ZZN

Keluaran 1

10 8 2
8 6 4

Penjelasan

Susunan sandwich pada contoh masukan 1 sesuai dengan Gambar 1 dalam pernyataan soal.

Misalnya, untuk mengambil kedua sandwich pada petak di baris ke-2 dari atas dan kolom ke-2 dari kiri, sandwich dapat diambil dalam urutan berikut.

• Ambil sandwich kanan atas pada petak di baris ke-1 dari atas dan kolom ke-3 dari kiri.
• Ambil sandwich kiri bawah pada petak di baris ke-1 dari atas dan kolom ke-3 dari kiri.
• Ambil sandwich kanan atas pada petak di baris ke-2 dari atas dan kolom ke-3 dari kiri.
• Ambil sandwich kiri bawah pada petak di baris ke-2 dari atas dan kolom ke-3 dari kiri.
• Ambil sandwich kanan bawah pada petak di baris ke-2 dari atas dan kolom ke-2 dari kiri.
• Ambil sandwich kiri atas pada petak di baris ke-2 dari atas dan kolom ke-2 dari kiri.

Totalnya ada $6$ sandwich yang diambil. Karena ini adalah jumlah minimum, keluarkan $6$.

Masukan 2

2 2
NZ
ZN

Keluaran 2

-1 -1
-1 -1

Penjelasan

Dalam kasus ini, tidak ada sandwich yang dapat diambil.

Masukan 3

5 5
NZZZN
NNNZN
NNZNN
NZNNN
NZZZN

Keluaran 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