409045: GYM103427 D Cross the Maze

"Ad astra abyssoque."

The adventurers from Teyvat are trapped in a rectangular maze of $$$a \times b$$$ square cells, which is surrounded by walls from the outside. The floorboards of the maze are so fragile that no two adventurers are allowed moving to or staying in the same cell of the maze anytime.

When they are trying to cross the maze, they find $$$n$$$ escape ropes in the maze and realize that the number of the escape ropes in the maze is exactly the same as the number of the adventurers trapped in the maze. However, the escape ropes are of low quality that a rope breaks immediately when an adventurer escape from the maze with it.

In every second, each of the adventurers can independently and simultaneously move from the cell $$$(x,y)$$$ to left cell $$$(x,y-1)$$$, the right cell $$$(x,y+1)$$$, the upper cell $$$(x-1,y)$$$, the lower cell $$$(x+1,y)$$$ in the maze, or just stay in place. When reaching a cell contains an intact escape rope after moving, an adventurer can decide to get out of the maze with the help of the escape rope immediately and then the rope breaks, or stay in the maze and leave the escape rope for others. Note that an adventurer can also leave the maze before moving if the adventurer has already located at a cell contains an escape rope.

Lumine the traveller wants to guide all the trapped adventurers cross the maze as soon as possible that she can continue searching for her family.

The first line contains three positive integers $$$n$$$ $$$(1 \le n \le 100)$$$, $$$a$$$ and $$$b$$$ $$$(1 \le a, b \le 100, 1 \le a \times b \le 100)$$$, denoting the number of the adventurers trapped in the maze as well as the number of the escape ropes in the maze and the number of rows and columns in the maze.

Then follow $$$n$$$ lines, each of which contains two integers $$$s_x$$$ $$$(1 \le s_x \le a)$$$ and $$$s_y$$$ $$$(1 \le s_y \le b)$$$, denoting an adventurer located at the cell $$$(s_x,s_y)$$$ in the maze initially. All the adventurers are located at different cells initially.

Then again follow $$$n$$$ lines, each of which contains two integers $$$e_x$$$ $$$(1 \le e_x \le a)$$$ and $$$e_y$$$ $$$(1 \le e_y \le b)$$$, denoting an escape rope located at the cell $$$(e_x,e_y)$$$ in the maze. All the escape ropes are located at different cells.

It is guaranteed that at least one adventurer located at the cell without escape ropes initially.

The first line contains an integer $$$t$$$, denoting the minimum time in seconds needed for all the trapped adventurers crossing the maze.

Then output $$$n$$$ lines, each of which contains four integers $$$s_x$$$, $$$s_y$$$, $$$e_x$$$ and $$$e_y$$$, followed by a string of length $$$t$$$. It means that an adventurer located at the cell $$$(s_x, s_y)$$$ initially will get out of the maze with the escape rope located at the cell $$$(e_x, e_y)$$$ by taking actions according to the string. The $$$i$$$-th character in the string points out the action taken in the $$$i$$$-th second, where L means going to the left cell, R means going to the right cell, U means going to the upper cell, D means going to the lower cell, S means staying in place, and P means the adventurer has left the maze and never goes back.

If there are multiple solutions, you may output any.

3 4 4
1 1
1 4
4 4
1 3
2 3
2 4

2
1 1 1 3 RR
1 4 2 3 DL
4 4 2 4 UU

3 2 2
1 1
1 2
2 2
1 1
2 1
2 2

1
1 1 1 1 P
1 2 2 2 D
2 2 2 1 L

2 3 3
1 1
1 3
1 2
2 2

2
1 1 2 2 DR
1 3 1 2 LP