407242: GYM102700 L Lonely day

L. Lonely daytime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Graduations at UNAL are coming and due to the quarantine and to avoid crowds, each student was scheduled to go individually to pick up their diploma on the UNAL campus.

Today it's Vitor's time, he is dressed in a fancy suit and ready to go. Let's imagine the university as a grid of $$$N$$$ x $$$M$$$ cells, where the lower-left corner is $$$(1, 1)$$$ and the upper-right corner is $$$(N, M)$$$. Each cell has one of the following characters:

• "." represents a clean cell. Vitor can step on it without ruining his suit
• "X" represents a dirty cell. Vitor can't step on it because it will ruin his suit.
• "S" represents the starting cell, where Vitor is at the beginning. It is also a clean cell. (There will be exactly one cell with this letter).
• "E" represents the final cell, where Vitor will receive his diploma. It is also a clean cell. (There will be exactly one cell with this letter).

Vitor can walk only through clean cells and for each step he can go from one to another cell if they share a side. However, UNAL keeps some secrets, one of them is the existence of tunnels that can take him from one cell to another cell in one step and keep him clean, isn't that magical? More precisely, a clean cell $$$(x_{1}, y_{1})$$$ is connected with another clean cell $$$(x_{2}, y_{2})$$$ by a tunnel if and only if the following conditions are met:

• $$$x_{1} = x_{2}$$$ OR $$$y_{1} = y_{2}$$$.
• When $$$x_{1} = x_{2}$$$, each cell $$$(x_{1}, y)$$$ must be a dirty cell, for all valid $$$y$$$ in $$$min(y_{1}, y_{2}) < y < max(y_{1}, y_{2})$$$.
• When $$$y_{1} = y_{2}$$$, each cell $$$(x, y_{1})$$$ must be a dirty cell, for all valid $$$x$$$ in $$$min(x_{1}, x_{2}) < x < max(x_{1}, x_{2})$$$.

Vitor wants to reach his destination as soon as possible and remain clean at all times. He is asking you to help him accomplish this.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ $$$(2 \leq N, M \leq 2000)$$$ separated by a space.

The following $$$N$$$ lines, each will contain a string with $$$M$$$ characters.

Output

If there is no way to reach the destination print $$$-1$$$.

Otherwise, the output will consist of two lines. The first line will be an integer $$$X$$$ where $$$X$$$ is the minimum number of steps that will take Vitor to reach his destination. The second line will be a string with length X where the ith character describe the direction that Vitor should take in the ith step. The string only contains these characters:

• "L" describes a step from (x, y) to (a, y) where a < x
• "R" describes a step from (x, y) to (a, y) where a > x
• "D" describes a step from (x, y) to (x, b) where b < y
• "U" describes a step from (x, y) to (x, b) where b > y

Print the smallest lexicographical solution if there is more than one.ExamplesInput

3 3
S..
...
..E

Output

4
DDRR

Input

3 3
SX.
XXX
XXE

Output

2
RD

Input

2 2
SX
XE

Output

-1