1255 : Palindrome Path

Description

Given an \(n\times m\) grid maze, each cell \((i,j)\) is either blank or blocked. Now, George is in the maze and the start cell is \((sr,sc)\), he needs to visit all the blank cells in the maze and go to the exit cell \((er,ec)\) finally. George can do \(4\) kinds of moves to travel the maze, assuming George is on cell \((i,j)\) currently:

1. Try to move left(denoted as L). If \(j>1\) and cell \((i,j-1)\) is blank, George will move to cell \((i,j-1)\), or George will stay at \((i,j)\).
2. Try to move right(denoted as R). If \(j<m\) and cell \((i,j+1)\) is blank, George will move to cell \((i,j+1)\), or George will stay at \((i,j)\).
3. Try to move up(denoted as U). If \(i>1\) and cell \((i-1,j)\) is blank, George will move to cell \((i-1,j)\), or George will stay at \((i,j)\).
4. Try to move down(denoted as D). If \(i<n\) and cell \((i+1,j)\) is blank, George will move to cell \((i+1,j)\), or George will stay at \((i,j)\).

So his task is to do several moves to visit all blank cells and go to the exit cell finally, where the start cell is considered to be visited in the beginning. To make it more fun, he wants to make his move sequence palindrome. Formally, denote his move sequence is \(M_1, M_2, \cdots, M_k\,(M_i \in \{L, R, U, D\})\), then for all integers \(i\,(1\le i \le k)\), \(M_i\) and \(M_{k-i+1}\) should be the same.

Please help him find a palindrome move sequence to visit all blank cells and go to the exit cell finally. If multiple solutions exist, print any one of them. If no solution, report it.

Input

The first line contains two integers \(n, m\,(1 \le n,m \le 30)\), denoting the size of the maze.

The following \(n\) lines each contains a binary string, denoting the given maze. The \(j\)-th character in the string in the \(i\)-th line will be 1 if cell \((i,j)\) blank, while it will be 0 if cell \((i, j)\) is blocked.

The next line contains four integers \(sr, sc, er, ec\,(1 \le sr, er \le n, 1 \le sc, ec \le m)\), denoting the positions of the start cell and the exit cell.

It is guaranteed that the start cell \((sr, sc)\) and exit cell \((er, ec)\) are both blank.

Output

If solution exists, print the move string \(S\,(0 \le |S| \le 10^6)\) in one line, or print -1 in one line.

If the goal could be achived by doing no operations in a test case, outputing an empty string is ok. But you should output an empty line in this situation.

DO NOT add extra space at the end of your output, or you will get “Wrong Answer” verdict.

Sample

2 2
11
11
1 1 2 2
##CASE##
2 2
10
01
1 1 2 2

RDLUULDR
##CASE##
-1

Hint

• For the first case, the path based on the move sequence is as follows:

1. Try to move right from \((1,1)\), since \(j = 1 < m\) and \((1,2)\) is blank, George will move to \((1,2)\)
2. Try to move down from \((1,2)\), since \(i = 1 < n\) and \((2,2)\) is blank, George will move to \((2,2)\)
3. Try to move left from \((2,2)\), since \(j = 2 > 1\) and \((2,1)\) is blank, George will move to \((2,1)\)
4. Try to move up from \((2,1)\), since \(i = 2 > 1\) and \((1,1)\) is blank, George will move to \((1,1)\)
5. Try to move up from \((1,1)\), since \(i = 1\), George will stay at \((1,1)\)
6. Try to move left from \((1,1)\), since \(j = 1\), George will stay at \((1,1)\)
7. Try to move down from \((1,1)\), since \(i = 1 < n\) and \((2,1)\) is blank, George will move to \((2,1)\)
8. Try to move right from \((2,1)\), since \(j = 1 < m\) and \((2,2)\) is blank, George will move to \((2,2)\)

It can be seen that all blank cells are visited and the ending cell is exactly the exit cell \((2,2)\).

• For the second case, George from \((1,1)\) can never reach \((2,2)\), so print -1 in one line.

Source

Author

FUDAN