The amazing game Pokenom Go has just been released. Pokenom trainers can now travel the world, capture Pokenom in the wild and battle each other!
Bash and Cee are two students who have recently dropped out of university to pursue their childhood dream of becoming Pokenom trainers. Today their amazing adventures begins!
The world can be considered as a grid with $N$ rows and $M$ columns. Rows are numbered from $1$ to $N$ from bottom to top, and columns are numbered from $1$ to $M$ from left to right. The cell at $r$-th row and $c$-th column is denoted as $(r, c)$.
Bash’s house is located at cell $(r_ B, c_ B)$. Today he will go to the Pokenom Gym located at cell $(r_ G, c_ G)$ where he can battle other Pokenom trainers. On the way to the Pokenom Gym, Bash also wants to visit Cee’s house, located at cell $(r_ C, c_ C)$.
Bash’s university is located at cell $(r_ U, c_ U)$. Bash does not want to pass the university on the path to the Pokenom Gym, as that will trigger Bash’s bad memories.
In each step, Bash can only go in either $4$ directions (up, down, left and right) to a cell which shares exactly one common edge with the current cells. Hence, a path can be uniquely defined by a string consisting of $4$ characters ‘U’, ‘D’, ‘L’, ‘R’ — representing the directions up, down, left and right, respectively.
A simple path is a path where no cells (including the starting and ending cells) are visited more than once.
Bash wants to find a simple path from cell $(r_ B, c_ B)$ to cell $(r_ G, c_ G)$, which passes through cell $(r_ C, c_ C)$ but not cell $(r_ U, c_ U)$. Bash would like to use as few steps as possible. Please help Bash!
The input contains multiple test cases. Each test case is described by $6$ lines:
The first line contains exactly $2$ integers $N$ and $M$, separated by a single space. $(1 \le M, N \le 100)$.
The second line contains exactly $2$ integers $r_ B$ and $c_ B$, separated by a single space.
The third line contains exactly $2$ integers $r_ C$ and $c_ C$, separated by a single space.
The fourth line contains exactly $2$ integers $r_ G$ and $c_ G$, separated by a single space.
The fifth line contains exactly $2$ integers $r_ U$ and $c_ U$, separated by a single space.
The sixth line is a blank line.
$1 \le r_ B, r_ C, r_ G, r_ U \le N, 1 \le c_ B, c_ C, c_ G, c_ U \le M$. The $4$ cells $(r_ B, c_ B)$, $(r_ C, c_ C)$, $(r_ G, c_ G)$ and $(r_ U, c_ U)$ are pairwise different.
The input is terminated by a single line containing two zeros.
The sum of $M \cdot N$ over all test cases does not exceed $10^5$.
For each test case, if it is impossible to find a path satisfying all the given constraints, print exactly one line with the word ‘NO’. Otherwise, print $2$ lines:
The first line contains the word ‘YES’.
The second line contains a string presenting Bash’s shortest simple path.
If there are multiple shortest simple paths, you can output any of them.
Sample Input 1 | Sample Output 1 |
---|---|
3 3 1 1 3 3 2 1 2 2 3 4 1 1 3 4 2 1 1 2 2 2 2 1 2 2 1 2 1 1 0 0 |
YES RRUULLD NO YES RD |