JOI 君 бере участь у дружній зустрічі IOI. На зустрічі сандвічі розкладено вздовж квадратної сітки з $R$ рядків та $C$ стовпців. Кожен сандвіч має форму рівнобедреного прямокутного трикутника, два катети якого дорівнюють стороні клітинки. У кожній клітинці лежать два сандвічі, що торкаються один одного гіпотенузами. Нижче наведено приклад розташування сандвічів.

Рисунок 1. Приклад розташування сандвічів.

Не можна взяти сандвіч, який одночасно задовольняє обидві наведені нижче умови.

• Його гіпотенуза торкається іншого сандвіча, який ще не взяли.
• Принаймні одна з двох інших його сторін торкається іншого сандвіча, який ще не взяли.

Будь-який інший сандвіч можна взяти.

Початковим станом називатимемо стан, у якому ще не взяли жодного сандвіча. Щоб узяти певний сандвіч із початкового стану, можливо, спершу доведеться взяти кілька інших. Залежно від розташування сандвічів деякі з них, можливо, узагалі не можна буде взяти.

JOI 君 хоче з'їсти обидва сандвічі, що лежать в одній клітинці. Він ще не вирішив, із якої саме клітинки їх з'їсти.

Його цікавить мінімальна кількість сандвічів, які необхідно взяти з початкового стану, щоб узяти обидва сандвічі з певної клітинки.

Завдання

За заданим розташуванням сандвічів напишіть програму, яка для кожної клітинки визначає, чи можна, взявши деякі сандвічі з початкового стану, взяти обидва сандвічі з цієї клітинки. Якщо можна, знайдіть мінімальну кількість сандвічів, які необхідно взяти. До цієї кількості слід включати і два цільові сандвічі.

Вхідні дані

Прочитайте такі дані зі стандартного вводу.

• Перший рядок містить цілі числа $R,C$, розділені пробілом. Вони означають, що сандвічі розкладено вздовж квадратної сітки з $R$ рядків та $C$ стовпців.
• $i$-й із наступних $R$ рядків ($1\le i\le R$) містить рядок із $C$ символів. Кожен символ — N або Z. $j$-й символ зліва ($1\le j\le C$) цього рядка описує розташування сандвічів у клітинці в $i$-му рядку згори та $j$-му стовпці зліва. Символи N та Z позначають відповідно наведені нижче розташування.

Рисунок 2. Розташування сандвічів у кожній клітинці.

Вихідні дані

Виведіть $R$ рядків у стандартний вивід. В $i$-му рядку ($1\le i\le R$) виведіть $C$ цілих чисел, розділених пробілами. Як $j$-те число ($1\le j\le C$) виведіть мінімальну кількість сандвічів, які необхідно взяти, щоб узяти обидва сандвічі з клітинки в $i$-му рядку згори та $j$-му стовпці зліва. Якщо це неможливо, виведіть $-1$.

Обмеження

Усі вхідні дані задовольняють такі умови.

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

Підзадачі

Підзадача 1 [35 балів]

Виконуються такі умови.

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

Підзадача 2 [65 балів]

Додаткових обмежень немає.

Приклади

Вхідні дані 1

2 3
NZN
ZZN

Вихідні дані 1

10 8 2
8 6 4

Примітка

Розташування сандвічів у першому прикладі відповідає рисунку 1 в умові.

Наприклад, щоб узяти обидва сандвічі з клітинки у 2-му рядку згори та 2-му стовпці зліва, можна брати сандвічі в такому порядку.

• Взяти верхній правий сандвіч із клітинки в 1-му рядку згори та 3-му стовпці зліва.
• Взяти нижній лівий сандвіч із клітинки в 1-му рядку згори та 3-му стовпці зліва.
• Взяти верхній правий сандвіч із клітинки у 2-му рядку згори та 3-му стовпці зліва.
• Взяти нижній лівий сандвіч із клітинки у 2-му рядку згори та 3-му стовпці зліва.
• Взяти нижній правий сандвіч із клітинки у 2-му рядку згори та 2-му стовпці зліва.
• Взяти верхній лівий сандвіч із клітинки у 2-му рядку згори та 2-му стовпці зліва.

Усього буде взято 6 сандвічів. Це мінімальна кількість, тому виводимо 6.

Вхідні дані 2

2 2
NZ
ZN

Вихідні дані 2

-1 -1
-1 -1

Примітка

У цьому випадку не можна взяти жодного сандвіча.

Вхідні дані 3

5 5
NZZZN
NNNZN
NNZNN
NZNNN
NZZZN

Вихідні дані 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