Canoes
Description
Cimrman had built a whole fleet of special weather prediction molybdenum canoes. Each canoe was separately built in its own dry dock. Consequently, the shore is littered with dug out patterns of dry docks, some of them even intersect each other, some of them are separate.
A dry dock is a rectangle with width of one standard unit and its length is a few standard units, always at least two. Each dock runs either in vertical or horizontal direction. Consequently, each two docks run either in a parallel direction or in directions perpendicular to each other. The width of each canoe is the same as the width of the dock and the length of the canoe is just one unit shorter than the length of its dock.
Next week, a hurricane is expected in the area, and Cimrman wants each canoe to be put back to the dock in which it was created. However, it is not immediately clear whether such universal storage plan can be accomplished.
And, by the way, are there any square shaped canoes? Yes, Cimrman is capable of building square molybdenum canoes.
The shore with docks is modelled as a rectangular grid, the size of its each elementary square is equal to one standard unit. The first input line contains three positive integers $H, W, N$ ($1 \leq H, W \leq 500, 1 \leq N \leq 250\,000$), giving the height of the grid, the width of the grid and the number of docks in the grid.
Each of the following $N$ lines specifies one dock. The dock is defined by four entries separated by spaces. The first three entries $X, Y , K$ are integers specifying the coordinates $(X, Y)$ of one end of the dock and the dock length $K$ (number of grid squares occupied by the dock). It holds that $1 \leq X \leq H, 1 \leq Y \leq W$, and $2 \leq K \leq 500$. The fourth entry on a row is one of characters "L", "R", "U", "D" and it specifies in which direction runs the dock from its start coordinate ("L" - Left, "R" - Right, "U" - Up, "D" - Down ). Moreover, no dock runs out of the bounds of the shore, e.g. for a dock which runs Down with one end on coordinates $(X, Y)$, it additionally holds $1 \leq X + (K - 1) \leq H$ (and analogously for other directions).
Output one line "Yes" if all canoes can be stored back in their docks or "No" otherwise.
Input
The shore with docks is modelled as a rectangular grid, the size of its each elementary square is equal to one standard unit. The first input line contains three positive integers $H, W, N$ ($1 \leq H, W \leq 500, 1 \leq N \leq 250\,000$), giving the height of the grid, the width of the grid and the number of docks in the grid.
Each of the following $N$ lines specifies one dock. The dock is defined by four entries separated by spaces. The first three entries $X, Y , K$ are integers specifying the coordinates $(X, Y)$ of one end of the dock and the dock length $K$ (number of grid squares occupied by the dock). It holds that $1 \leq X \leq H, 1 \leq Y \leq W$, and $2 \leq K \leq 500$. The fourth entry on a row is one of characters "L", "R", "U", "D" and it specifies in which direction runs the dock from its start coordinate ("L" - Left, "R" - Right, "U" - Up, "D" - Down ). Moreover, no dock runs out of the bounds of the shore, e.g. for a dock which runs Down with one end on coordinates $(X, Y)$, it additionally holds $1 \leq X + (K - 1) \leq H$ (and analogously for other directions).
Output
Output one line "Yes" if all canoes can be stored back in their docks or "No" otherwise.
5 3 4
1 1 4 D
3 1 3 R
5 1 2 U
5 3 3 L
5 5 5
1 1 5 R
1 1 5 D
5 5 5 L
5 5 5 U
5 3 5 U
Yes
No
Note
Figure 1: Illustration of Sample Input 1