L. Legends: Are You Serious?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Once again, Cindy finds herself playing a game that Alice recommended to her, in the hopes that they can get closer by bonding over their experiences in their playthroughs. That's not to say that the game isn't fun, though! There's lots to do in the world of Sushii, including a decent customization system which can let you try on a lot of different outfits.

The next map, the Scarlet Swamp, is a marshland and is full of lots of puddles of mud. A cool detail is that when Cindy's character steps into the mud, her outfit actual gets dirty, and stays dirty for a while too. Wow, realism! Well, unfortunately, Cindy loves her outfit so much that she would hate for it to get covered in mud...

The map of the Scarlet Swamp is represented as a grid with $$$R$$$ rows and $$$C$$$ columns. We let $$$(i, j)$$$ denote the square in the $$$i$$$th row from the top, and the $$$j$$$th column from the left. Each square can be one of three different types of terrain:

  • . denotes open space which can be freely traversed
  • # denotes a lava tile which will instantly kill Cindy if she walks into it
  • $$$\tilde{}$$$ denotes a muddy tile which can be freely traversed, but doing so would make Cindy muddy as well.
Cindy's character spawns in square $$$(r_s, c_s)$$$, and is always initially facing South. Her character navigates the world with three simple commands: turn left; turn right; and take a step forward.

In order to avoid getting muddy, Cindy can use any of the $$$k$$$ wooden planks that are littered around the world map. The squares $$$(i_1, j_1)$$$, $$$(i_2, j_2)$$$, $$$\dots$$$, $$$(i_k, j_k)$$$ each initially contain a single wooden plank.

Wooden planks can be placed on open space and muddy tiles, and Cindy can still walk on such tiles even if there are planks on them; in fact, if there is a wooden plank on a muddy tile, then when Cindy moves to that square, she steps on the plank, avoiding sinking into the mud. This is the only way to walk into muddy tiles without getting dirty.

Thus, Cindy's character also has access to two more helpful commands: get the wooden plank from the square she is facing; and put down the wooden plank she is holding onto the square she is facing. Note that after Cindy puts down a wooden plank somewhere, she is free to come back to it later and pick it up again.

Each square may only contain at most one wooden plank at a time. Cindy may only hold onto one wooden plank at a time, and she spawns into the world not initially holding a wooden plank.

Starting from her spawn point of $$$(r_s, c_s)$$$, Cindy needs to make it to the objective at $$$(r_t, c_t)$$$ without getting dirty. Can you help her figure out what to do? Of course, if the task is impossible, you should tell her so.

Input

The first line of input contains the space-separated integers $$$R$$$ and $$$C$$$, the number of rows and columns in the grid.

The second line of input contains the space-separated integers $$$r_s$$$, $$$c_s$$$, $$$r_t$$$, and $$$c_t$$$, encoding the coordinates of the starting tile and the target tile.

Then, $$$R$$$ lines follow, each containing a string of length $$$C$$$. This encodes the world map of Sushii as a grid, with the meanings of each character described above.

Then, the next line contains a single integer $$$k$$$, the number of wooden planks in the world.

Then, $$$k$$$ lines follow, each containing a pair of space-separated integers $$$i$$$ and $$$j$$$ that describe the coordinates of some plank.

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq R, C \leq 100 \\ \text{All wooden planks initially appear on distinct squares, and none are on lava tiles.} \\ \text{$(r_s, c_s) \neq (r_t, c_t)$ and both are guaranteed to be open space.} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{20} & k = 0 \\ \hline 2 & \mathbf{26} & k \leq 1 \\ \hline 3 & \mathbf{23} & \text{The map has no lava tiles.} \\ \hline 4 & \mathbf{11} & R = 1 \\ \hline 5 & \mathbf{20} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Output

If the task is impossible, output a line containing NO. Otherwise, output YES.

Furthermore, if your answer was YES, you should output another line containing a "command string," describing the moves that Cindy must perform so that she reaches the objective.

Each character in the command string corresponds to a certain action that Cindy's character can take:

  • L: Cindy turns $$$90^\circ$$$ counterclockwise.
  • R: Cindy turns $$$90^\circ$$$ clockwise.
  • F: Cindy takes a single step forward in the direction she is facing. If this action would cause any of the following to happen, then you get an immediate Game Over (i.e. Wrong Answer)
    • Cindy exits the bounds of the map
    • Cindy steps into a lava tile
    • Cindy steps into a muddy tile that doesn't have a wooden plank in it.
  • G: If Cindy is currently not holding a wooden plank, and there is a wooden plank on the square she is facing: the wooden plank is removed from that square, and Cindy is now holding a wooden plank.
    • In any other case, this command causes an immediate Game Over.
  • P: If Cindy is currently holding a wooden plank, the square in front of her exists and is not a lava tile, and there is no wooden plank on the square she is facing: Cindy is no longer holding a wooden plank, and the square in front of her now contains a wooden plank.
    • In any other case, this command causes an immediate Game Over.
These commands are performed in sequence, in the order that they appear in the command string. You are reminded that Cindy begins the game at $$$(r_s, c_s)$$$, and is always initially facing South.

Your command string will be accepted if it successfully brings Cindy to $$$(r_t, c_t)$$$ (it doesn't matter what direction she's facing) and if it is no more than $$$2 \times 10^5$$$ characters long. Note that the number of commands doesn't have to be minimized. It can be shown that, given the constraints, if a solution exists, then one exists that uses $$$2 \times 10^5$$$ commands or fewer.

Examples
Input
2 3
1 1 2 3
.~.
.#.
2
2 1
1 3
Output
YES
GLPFFRF
Input
2 3
1 1 2 3
.~.
.#.
2
1 1
1 3
Output
YES
FLLGFRPFFRF
Input
4 3
4 1 1 2
#..
~#.
.#~
.~.
1
2 1
Output
YES
RRFGRRFLPFFRRGRPFFFLF
Input
2 2
2 2 1 1
.~
#.
0
Output
NO