Algorithms and Data Structures

Pacman - Get Out Safely

You are playing the game Pacman. You are in a labyrinth with some monsters. You need to reach one of the boundary squares of the labyrinth without sharing a square with a monster.
On each move, you move in some direction (up, left, right, or down) and the monsters move in some direction as well.
If it’s possible to get out of the labyrinth safely, you should print the path that you can follow. The strategy needs to work even if the monsters know your plan.
notion image

Input

The first line of the input contains two integers h and w (1 ≤ h, w ≤ 1000) the height and the width of the labyrinth.
The next h lines contain w symbols describing the labyrinth:
  • . - floor
  • # - wall
  • M - monster
  • Y - your initial position

Output

The first line of the output should contain the number of steps to get out of the maze, and Impossible if it’s not possible to do so.
If it’s possible, the next line should contain any valid path to do so.

Examples

Input

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

5
RRDDR

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in