J. Fashionable Suit
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Lorenzo is considered one of the most outstanding fashion designers of the last thousand years. Recently, Lorenzo presented his new, truly ingenious creation, a pearl in the fashion industry. He designed a suit entirely made of Velcro. The suit is so unique that no other designer has ever presented anything like it. Unfortunately, the suit turned out to be not very practical. When Lorenzo was heading to a fashion exhibition, he decided to save money and instead of a business-class taxi, he ordered an economy one. As a result, his suit stuck to the fabric interior of the car, and Lorenzo needed the driver's help to get out of the car. After overcoming this difficulty, another one suddenly arose. It turned out that at the exhibition, some of the walls were covered with fabric, and when Lorenzo leaned against one of them, he got stuck again. Now he can only move in three ways: rotate clockwise, rotate counterclockwise, or try to push off the wall with all his might, in which case Lorenzo will fly perpendicular to the wall until he hits another wall or flies out of the exhibition. To overcome this difficulty, he needs to either reach a regular wall (not covered with fabric) or fly out of the exhibition. Note that if Lorenzo sticks to a wall outside the exhibition, it does not mean that he has flown out of it. Unfortunately, since he left the taxi, Lorenzo has not had much strength left, so he wants to make the minimum number of movements to get out of this situation. He turned to you for help and asked to develop a plan so that he can move freely again (without leaning against the wall).

You have a plan of the exhibition, which is a grid of size $$$w$$$ cells in width and $$$h$$$ cells in height. The cells are numbered from top to bottom, left to right, starting from one. There are a total of $$$n$$$ fabric-covered walls and $$$m$$$ regular walls. You know to which wall and from which side Lorenzo got stuck. You need to find the minimum number of actions that Lorenzo needs to perform in order to move freely. There are three types of actions:

  1. Make one clockwise rotation. Then Lorenzo will move to the adjacent side of the wall, or to the opposite side of the wall if there is no adjacent wall.
  2. Make one counterclockwise rotation. Similar to the previous action.
  3. Push off the wall with all his might. In this case, Lorenzo will fly in the opposite direction from the wall, until he hits another wall or flies out of the exhibition.
Figure 1. Examples of possible actions
Input

The first line contains four integers $$$w$$$, $$$h$$$, $$$n$$$, and $$$m$$$ — the width and height of the exhibition, and the number of fabric-covered walls and regular walls, respectively.

The next $$$n$$$ lines contain two integers $$$x$$$ ($$$1 \le x \le w$$$) and $$$y$$$ ($$$1 \le y \le h$$$) and one character $$$t$$$ — the coordinates of the cell and its boundary where the fabric-covered wall is located. The character $$$L$$$ means that the wall is located on the left boundary, $$$R$$$ — on the right, $$$U$$$ — on the top, and $$$D$$$ — on the bottom.

The next $$$m$$$ lines contain the description of regular walls in the same format.

The last line contains two integers $$$sx$$$ ($$$1 \le sx \le w$$$) and $$$sy$$$ ($$$1 \le sy \le h$$$) and one character $$$st$$$ — the coordinates of the cell and its boundary to which Lorenzo got stuck. It is guaranteed that Lorenzo got stuck to a fabric-covered wall.

It is guaranteed that each wall cannot be both fabric-covered and regular (even different sides). Also, note that for example, "1 1 D" and "1 2 U" describe the same wall.

$$$$$$1 \le w, h \le 10^5$$$$$$ $$$$$$1 \le n \le 5 \cdot 10^5$$$$$$ $$$$$$0 \le m \le 5 \cdot 10^5$$$$$$ $$$$$$n + m \le 5 \cdot 10^5$$$$$$

Output

In the first line, output "No" if Lorenzo cannot free himself.

Otherwise, in the first line, output "Yes", and in the next line, output a string describing Lorenzo's route.

The symbol ">" indicates a clockwise rotation, "<" indicates a counterclockwise rotation, and "^{}" means that Lorenzo needs to push off the wall. If there are multiple possible answers, you need to output any of them consisting of the smallest number of actions.

Examples
Input
1 1 3 1
1 1 L
1 1 R
1 1 D
1 1 U
1 1 D
Output
Yes
^
Input
1 1 3 1
1 1 L
1 1 R
1 1 D
1 1 U
1 1 L
Output
Yes
<
Input
2 2 8 0
1 1 U
2 1 U
1 1 L
1 2 L
2 1 R
2 2 R
2 2 D
1 1 D
1 1 U
Output
Yes
^>^
Input
1 1 3 0
1 1 U
1 1 D
1 1 L
1 1 D
Output
Yes
>^
Input
1 1 4 0
1 1 U
1 1 D
1 1 L
1 1 R
1 1 L
Output
No
Note
Figure 2. Visualization for test examples 1-3