LNTILING - Long Tiling

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 Ki and has Ci 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 W1i, either up (U), down(D), left(L) or right(R), and one integer F1i, indicating the direction to turn to and the length of that segment. (1 ≤ ∑ni=1 F1i ≤ 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 Ki and number of segments Ci. (1 ≤ Ki, ∑Mi=1 Ki ≤ 15, 1 ≤ Ci ≤ 20)

Following Ci lines, same as above, one uppercase character W2i and one integer F2i 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


Added by:him0727
Date:2018-10-25
Time limit:0.200s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own problem

hide comments
2020-05-05 12:23:00
Can there be 2 consecutive segments with same direction?

RE: No

Last edit: 2020-05-07 17:46:45
2019-08-24 21:08:31 Simes
Thoroughly enjoyed solving it! Many thanks for creating the problem.
2019-07-04 11:56:21 :D
Very nice DP problem.
2019-06-12 17:28:37 Aleksei
Hello.

I've made a solution using DP. I'm quite confident in it, but I get WA.

Can you please provide a test case when it fails?

TY

RE: just quickly created a case..
1
3
R 1
D 1
R 1
1
1 2
R 2
D 1
Your ans gives NO, while it should be YES

Last edit: 2019-06-13 19:26:18
2018-10-26 12:32:21 :D
Can the tiles also be flipped or only rotated?

Re: rotate only

Last edit: 2018-10-26 13:35:13
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.