406774: GYM102536 M Thin Ice

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

M. Thin Icetime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

So you, as well as every member of the Penguin Secret Agency (PSA), have successfully sunk the evil genius's secret iceberg base by dancing on it until it flipped. He's pretty mad about that and went back to his igloo as a result. However, intelligence reports say that he has a special ice farm to create a second Iceberg Base.

You move to his ice farm and realize that you don't have anything to melt the ice with. You did however, bring your Puffle. After giving it a berry, it bursts into flames, ready to melt the ice for you, turning it into water. There is a problem though: if the Puffle is forced to go into the water, it cannot melt any more ice blocks. Also, you must melt all the ice to prevent the second Iceberg Base. Lastly, you need to give your Puffle instructions on how to move. They aren't known for their puzzle solving skills, but their memory is excellent. Don't forget to pick up your Puffle after it's done. Good luck!

The area to solve is an $$$r\times c$$$ grid. We denote by $$$(i, j)$$$ the cell at the $$$i$$$th row (from the top) and the $$$j$$$th column (from the left). In particular, $$$(1, 1)$$$ is the top-left corner of the area.

Your starting position is cell $$$(i, j)$$$, and your ending position can be anywhere.

Determine if a path that goes through each cell exactly once is possible. You are considered to have already passed the starting cell at the beginning. If it is possible, give a sequence that will do so.

Output your instructions as a sequence of directions: up, down, left, or right.

Should it be impossible, say so as well.

Input

The first line of input contains $$$t$$$, the number of test cases.

Each test case consists of a single line containing four space-separated integers $$$r, c, i, j$$$.

Constraints

  • $$$1 \le t \le 10^5$$$
  • $$$1 \le r, c \le 100$$$
  • $$$1 \le i \le r$$$
  • $$$1 \le j \le c$$$
  • $$$rc > 1$$$
  • It is guaranteed that the output file is at most 10 Megabytes ($$$10^7$$$ bytes).
Output

For each test case, output a single line containing a single string which is either:

  • a string consisting of the following characters:

    • U - Moves your position up by 1
    • L - Moves your position left by 1
    • D - Moves your position down by 1
    • R - Moves your position right by 1

  • the string "IMPOSSIBLE" (without the quotes) if the task is impossible.
For example, if an answer requires you to move right, then down, then left, then the output will be RDL. There may be multiple answers; any one will be accepted.ExampleInput
2
2 3 1 1
3 3 1 2
Output
DRRUL
IMPOSSIBLE

加入题单

上一题 下一题 算法标签: