Pacman - Uscire in Sicurezza

Stai giocando a Pacman. Ti trovi in un labirinto con alcuni mostri. Devi raggiungere una delle caselle sul bordo del labirinto senza mai condividere una casella con un mostro.

A ogni mossa, ti sposti in una direzione (su, sinistra, destra o giù), e anche i mostri si muovono in una direzione.

Se è possibile uscire dal labirinto incolume, dovresti stampare il percorso da seguire. La strategia deve funzionare anche se i mostri conoscono il tuo piano.

Input

La prima riga dell'input contiene due interi h e w (1 ≤ h, w ≤ 1000), che indicano l'altezza e la larghezza del labirinto.

Le successive h righe contengono w simboli che descrivono il labirinto:

• . - pavimento

• # - muro

• M - mostro

• Y - la tua posizione iniziale

Output

La prima riga dell'output deve contenere il numero di passi necessari per uscire dal labirinto, oppure Impossible se non è possibile farlo.

Se è possibile, la riga successiva deve contenere un qualunque percorso valido per farlo.

Esempi

Input

5 8
########
#M..Y..#
#.#.M#.#
#M#..#..
#.######

Output

5
RRDDR