Le robot inarrêtable

Un groupe d’étudiants a développé un robot capable de se déplacer dans un labyrinthe. Cependant, ce robot n’est pas parfait : il ne peut pas changer de direction ni s’arrêter tant qu’il n’a pas atteint un mur ou un obstacle. Ainsi, lorsqu’il entame un mouvement, il doit d’abord rejoindre le mur le plus proche dans la direction où il se déplace, puis décider d’une nouvelle direction.

Votre tâche est de déterminer le nombre minimal de déplacements nécessaires pour que le robot aille de la position de départ S à la position d’arrivée E, puis d’afficher les commandes que les étudiants doivent envoyer au robot pour y parvenir :

L - se déplacer vers la gauche

U - se déplacer vers le haut

R - se déplacer vers la droite

D - se déplacer vers le bas

Entrée

La première ligne de l’entrée contient deux nombres h et w (2 ≤ h, w ≤ 100), qui représentent la hauteur et la largeur de la grille.

Les h lignes suivantes comprennent chacune w caractères décrivant la grille :

. indique le sol

# indique un mur

S indique la position de départ

E indique la position d’arrivée

On garantit que la grille est entourée de murs, ce qui empêche le robot de sortir du cadre.

Sortie

Le programme doit afficher sur la première ligne le nombre minimum de déplacements nécessaires pour aller de la position de départ à la position d’arrivée. La deuxième ligne doit contenir toutes les commandes que les étudiants doivent envoyer au robot. S’il existe plusieurs manières de réussir, le programme peut afficher n’importe laquelle d’entre elles.

S’il est impossible pour le robot d’atteindre la fin, le programme doit afficher Impossible.

Exemples

Input

7 9
#########
#.......#
#.S.....#
#.......#
#.#E....#
#.#.....#
#########

Output

4
RDLU

Conseil

Vous pouvez considérer que la position de départ est simplement un sol (.) et que la position d’arrivée agit comme un mur (#).

Entrée

Sortie

Exemples

Constraints

To check your solution you need to sign in

Sign in to continue