406809: GYM102562 J Mousepad

Dorian found an old mouse laying around the house and is now playing around with it. Dorian's mousepad can be modeled as a matrix with $$$N$$$ rows and $$$M$$$ columns such that $$$N * M \leq 10^5$$$. Each cell of the mousepad is either clean which is represented by a $$$0$$$, or dirty which is represented by a $$$1$$$.

He quickly realised $$$2$$$ things: the mouse can only be moved horizontally and vertically and it only registers a movement if it realised between $$$2$$$ adjacent cells that are both clean!

Now Dorian thought of an interesting game: starting from the top left of the matrix, without lifting his mouse from the mousepad and without going outside the bounds, can he trick the mouse into thinking it was moved to some other arbitrary coordinates $$$-10^5 \leq X \leq 10^5$$$ and $$$-10^5 \leq Y \leq 10^5$$$?

You should output a sequence of instruction composed of characters $$$L(eft)$$$, $$$R(ight)$$$, $$$U(p)$$$, $$$D(own)$$$ if it is possible to reach the said coordinates, or $$$-1$$$ otherwise.

Keep in mind the $$$Y$$$ coordinate increases as you go up in the matrix, and the $$$X$$$ coordinate increases as you go right. The mouse initially thinks it is at coordinates $$$(0, 0)$$$ and you start from the top left corner of the matrix.

There is also something strange about Dorian's mousepad, because its extremities are made of a special material, they never get dirty. That is, first and last rows and columns will always be clean.

The first line will contain two integers $$$N$$$ and $$$M$$$: the dimensions of the mousepad.

The following $$$N$$$ lines will each contain a string of $$$M$$$ characters, the description of the mousepad.

The last line will contain two integers $$$X$$$ and $$$Y$$$, the coordinates Dorian wants to reach.

For each testcase, you should output one line either a $$$-1$$$ if there is no solution, or a string of no more than $$$10^6$$$ characters: the instructions for Dorian.

5 5
00000
01000
01000
01000
00000
2 3

DRDDLDRUDRULDRULDRULUURULDRULD

These are the coordinates registered by the mouse after each move:

(1,0), (1,0), (1,0), (1,0), (1,0), (1,1), (1,2), (1,3), (2,3)