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

Рисунок 1. Пример расположения сэндвичей.

Нельзя взять сэндвич, для которого одновременно выполнены следующие два условия:

• Его гипотенуза соприкасается с другим сэндвичем, который ещё не взяли.
• Хотя бы один из двух его катетов соприкасается с другим сэндвичем, который ещё не взяли.

Любой другой сэндвич можно взять.

Назовём начальным состояние, в котором ещё не взяли ни одного сэндвича. Чтобы взять определённый сэндвич, начиная с начального состояния, возможно, придётся сначала взять некоторые другие сэндвичи. В зависимости от расположения могут существовать сэндвичи, которые вообще невозможно взять.

JOI 君 хочет съесть оба сэндвича, лежащие в одной клетке. Он ещё не решил, из какой именно клетки взять сэндвичи.

Ему интересно минимальное количество сэндвичей, которые придётся взять, чтобы, начиная с начального состояния, взять оба сэндвича из определённой клетки.

Задание

По заданному расположению сэндвичей для каждой клетки определите, можно ли взять оба сэндвича из этой клетки, последовательно забирая сэндвичи из начального состояния. Если можно, найдите минимальное количество сэндвичей, которые необходимо взять. В это количество включаются и два нужных сэндвича.

Входные данные

Прочитайте следующие данные из стандартного ввода.

• В первой строке записаны целые числа $R,C$, разделённые пробелом. Они означают, что сэндвичи расположены по квадратным клеткам сетки из $R$ строк и $C$ столбцов.
• В строке $i$ ($1 \le i \le R$) из следующих $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 в условии.

Например, чтобы взять оба сэндвича из клетки во второй строке сверху и втором столбце слева, можно брать сэндвичи в следующем порядке:

• Взять верхний правый сэндвич из клетки в первой строке сверху и третьем столбце слева.
• Взять нижний левый сэндвич из клетки в первой строке сверху и третьем столбце слева.
• Взять верхний правый сэндвич из клетки во второй строке сверху и третьем столбце слева.
• Взять нижний левый сэндвич из клетки во второй строке сверху и третьем столбце слева.
• Взять нижний правый сэндвич из клетки во второй строке сверху и втором столбце слева.
• Взять верхний левый сэндвич из клетки во второй строке сверху и втором столбце слева.

Всего берётся 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