Lego Brick Walls

You have just joined a brick-modeling company on the team that writes instruction booklets. The senior designers create exciting new brick models but do not have time to work out every detail. Your job is to check their partial models to see whether they can be built completely from the bricks in a given set.

A common task is building a flat rectangular wall. This happens so often that it is worth writing a program to do the checking. Your program must decide whether a rectangular wall can be built from a given set of bricks of three kinds — R1, R2, and R3 — which are 1, 2, and 3 units wide respectively.

Walls must obey the brick rule: the vertical joints between bricks in two adjacent rows must never be aligned. In the diagram below are two 2-by-3 (rows by columns) walls, each made from 2 R1 and 2 R2 bricks. The left one obeys the brick rule; the right one does not (the oval marks the illegal vertical alignment).

For each wall you must build, you are given its dimensions (the number of rows and columns in brick units) and some known brick positions that the designer has already fixed (these occur where the wall connects to other parts of a model). When the wall is wide (more than 10 columns), the designer usually fixes most of the bricks along the top row. You are also given the set of bricks from which the wall must be built.

Notes: you do not need to use every brick in the set, and the pre-fixed bricks are not taken from the set.

As an illustration, consider building a 3-row by 5-column wall that has a fixed R1 brick at row 2, column 3, using a set of 5 R1's, 5 R2's, and 5 R3's. One valid solution uses 4 R1's, 2 R2's, and 2 R3's, as shown below.

The input describes several walls. Each wall begins with a line containing the number of rows and the number of columns; both are between 1 and 30 inclusive. A line 0 0 ends the input.

The second line of each wall holds three numbers: the number of R1's, the number of R2's, and the number of R3's available.

The third line holds the number N of pre-fixed bricks (N may be 0). Then follow N lines, each describing one pre-fixed brick by three numbers S, R, C: S is the brick size (1, 2, or 3), and R and C are the row and the leftmost column of the brick. The top-left corner of the wall is row 1, column 1.

For each wall, print one line containing Yes if the wall can be built, or No otherwise.