JOI sta partecipando a un incontro sociale delle IOI. All'incontro, dei panini sono disposti lungo una griglia di $R$ righe e $C$ colonne. Ogni panino ha la forma di un triangolo rettangolo isoscele con i due cateti di lunghezza uguale al lato di una cella della griglia, e ogni cella contiene due panini posizionati in modo che le loro ipotenuse si tocchino. La figura sottostante mostra un esempio della disposizione dei panini.

Figura 1. Esempio di disposizione dei panini

Un panino non può essere preso se soddisfa entrambe le seguenti condizioni: La sua ipotenusa tocca un altro panino che non è stato ancora preso. Almeno uno dei suoi due lati diversi dall'ipotenusa tocca un altro panino che non è stato ancora preso.

I panini diversi da questi possono essere presi.

Lo stato in cui nessun panino è stato preso è lo stato iniziale. Per prendere un determinato panino a partire dallo stato iniziale, potrebbe essere necessario prendere prima altri panini. A seconda della disposizione dei panini, alcuni panini potrebbero non poter essere presi affatto.

JOI vuole mangiare entrambi i panini posizionati nella stessa cella. Non ha ancora deciso i panini di quale cella mangiare.

È interessato al numero minimo di panini che devono essere presi per ottenere entrambi i panini di una determinata cella a partire dallo stato iniziale.

Compito

Data la disposizione dei panini, per ciascuna cella determina se è possibile prendere entrambi i panini di quella cella prendendo alcuni panini a partire dallo stato iniziale. Se è possibile, trova il numero minimo di panini che devono essere presi. Si noti che il numero di panini deve includere anche i due panini obiettivo stessi.

Dati in ingresso

Leggi i seguenti dati da standard input: La prima riga contiene due interi $R$ e $C$ separati da uno spazio. Questi indicano che i panini sono disposti lungo una griglia di $R$ righe e $C$ colonne. La $i$-esima riga ($1 \le i \le R$) delle successive $R$ righe contiene una stringa di lunghezza $C$. Ogni carattere è 'N' oppure 'Z'. Il $j$-esimo carattere ($1 \le j \le C$) di questa stringa rappresenta la disposizione dei panini nella cella alla $i$-esima riga dall'alto e $j$-esima colonna da sinistra. 'N' e 'Z' rappresentano rispettivamente le seguenti disposizioni.

Figura 2. Disposizione dei panini in ciascuna cella

Dati in uscita

Stampa $R$ righe su standard output. La $i$-esima riga ($1 \le i \le R$) deve contenere $C$ interi separati da spazi. Il $j$-esimo intero ($1 \le j \le C$) deve essere il numero minimo di panini che devono essere presi per ottenere entrambi i panini nella cella alla $i$-esima riga dall'alto e $j$-esima colonna da sinistra. Se non è possibile prenderli, stampa -1.

Vincoli

Tutti i dati di input soddisfano le seguenti condizioni: $1 \le R \le 400$ $1 \le C \le 400$

Sottoproblemi

Sottoproblema 1 [35 punti]

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

Sottoproblema 2 [65 punti]

• Nessun vincolo aggiuntivo.

Esempi

Input 1

2 3
NZN
ZZN

Output 1

10 8 2
8 6 4

Nota 1

La disposizione dei panini nell'Esempio 1 corrisponde alla Figura 1 nella descrizione del problema. Ad esempio, per prendere i due panini nella cella alla 2ª riga dall'alto e 2ª colonna da sinistra, si possono prendere i panini nel seguente ordine: Prendere il panino in alto a destra della cella alla 1ª riga, 3ª colonna. Prendere il panino in basso a sinistra della cella alla 1ª riga, 3ª colonna. Prendere il panino in alto a destra della cella alla 2ª riga, 3ª colonna. Prendere il panino in basso a sinistra della cella alla 2ª riga, 3ª colonna. Prendere il panino in basso a destra della cella alla 2ª riga, 2ª colonna. Prendere il panino in alto a sinistra della cella alla 2ª riga, 2ª colonna.

Vengono presi in totale 6 panini e, poiché questo è il minimo, viene stampato 6.

Input 2

2 2
NZ
ZN

Output 2

-1 -1
-1 -1

Nota 2

In questo caso, nessuno dei panini può essere preso.

Input 3

5 5
NZZZN
NNNZN
NNZNN
NZNNN
NZZZN

Output 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