Arrow Maze (Hard)

Apart from the input limits, difficulty does not change the problem.

Mingyu became a wizard after 25 years of lonely training. His dream was to build a magical, spectacular theme park. For its first attraction, Mingyu opened the "Arrow Maze."

The Arrow Maze is quite different from an ordinary maze. It consists of R×C rooms. Walls block every side of every room, so no two rooms can be reached by walking. Each room is decorated with a unique and dazzling theme.

If walls block every side, how do visitors move between rooms? Mingyu drew a magic circle in each room, and the circle teleports the visitor exactly one cell in the direction of its arrow. The outer wall of the maze is surrounded by magma, so no one can leave the maze by crossing the outermost wall.

Visitors enter at room (1,1), the top-left room, and must reach the exit at room (R,C), the bottom-right room, to finish the maze. If they fail, they wander the Arrow Maze forever! Naturally, depending on the arrow directions in the magic circles Mingyu first drew, a visitor may never reach the exit.

To let guests enjoy the maze safely, Mingyu sells special scrolls at the entrance. There are two kinds: the L scroll rotates an arrow counterclockwise, and the R scroll rotates it clockwise. Using a scroll turns the arrow 90 degrees in that direction. Several scrolls can be used in a row on one magic circle to rotate it 180 or 270 degrees. To maximize profit, Mingyu sells only sets that contain one L scroll and one R scroll each.

Visitors receive the map only after they enter the maze. To avoid wandering forever, they had to buy large numbers of scroll sets, which they disliked. Junseo, a longtime visitor and Mingyu's friend, also suffered from this inconvenience.

Junseo: Well, at least tell me whether what I have right now is enough!!

Tired of Junseo's complaints, Mingyu agreed to answer one question for Junseo alone. The question is whether the scroll sets Junseo owns are enough to reach the exit. The answer is "Yes" or "No". Answering accurately is very hard for Mingyu, so he asked you to write a program that answers the question for him.

The first line contains the number of rows R, the number of columns C, and the number of scroll sets K that Junseo owns.

From the second line onward, the map of the Arrow Maze is given over R lines. Each line is a string of length C consisting only of the characters "UDLR". U means the circle lets you move up, D down, L left, and R right.

Print "Yes" or "No" as the answer to Junseo's question.

1 ≤ R, C ≤ 150

0 ≤ K ≤ 1500