There is a long gap with fixed width of 1 unit in the ground with N + 1 vertices, which is composed of N segments with same width. A segment connects to at most one segment on its head and tail vertically or horizontally, that is, it can connect to at most two segments. The long gap formed by those segments is simply a open polyline. Duck doesn't like the gap, he is given a set of tiles and wants to know if the long gap can be tiled by the limited number of tiles. There are M distinct tiles, each with K_i and has C_i segments. It is not necessary to use all tiles, and Duck can rotate the tile to fill the gap. It is guaranteed that both long gap and tiles are open polyline with fixed width of 1 unit. Can you help him check if he is possible to do so.

Input

The first line is the number of test cases T. (1 ≤ T ≤ 25)

For each test case, it starts with the number of segments of the long gap N. (1 ≤ N ≤ 20)

Following N lines, each consisting of one uppercase character W1_i, either up (U), down(D), left(L) or right(R), and one integer F1_i, indicating the direction to turn to and the length of that segment. (1 ≤ ∑ⁿ_i=1 F1_i ≤ 100)

Next line is the number of distinct tiles M. (1 ≤ M ≤ 15)

For each distinct tile, it starts with two integers, the available amount of that tile K_i and number of segments C_i. (1 ≤ K_i, ∑^M_i=1 K_i ≤ 15, 1 ≤ C_i ≤ 20)

Following C_i lines, same as above, one uppercase character W2_i and one integer F2_i indicating the direction and the length of that segment.

Output

If it is possible to tile the gap with given tiles, print "YES", else "NO". (without quotes)

Example

Input:
2
16
L 4
U 2
L 7
U 2
L 4
D 4
R 2
D 2
L 3
D 2
R 6
U 1
R 2
D 4
L 3
U 1
7
2 5
D 6
L 2
U 3
L 2
D 2
1 2
D 7
L 2
2 2
D 2
R 2
1 1
R 8
3 1
U 3
4 1
D 4
2 2
R 3
U 1

2
R 6
U 2
2
1 2
D 3
L 2
1 1
U 2

Output:
YES
NO

Explanation