Problem I
Patchwork

Picture by North Sea Quilters via Wikimedia Commons, cc by-sa

Adam’s grandmother has a birthday coming up and he wants to make her a beautiful patchwork quilt as a present. He has created a collection of patch designs that he will sew onto the quilt. However, he is having trouble deciding exactly where to place his patches. His current procedure is to sew on all patches in a given configuration, determine if he likes the way it looks, and cut them all off if he doesn’t. This is highly inefficient and Adam is running out of time.

Adam starts with a rectangular white cloth to be used as the base for his quilt and has a collection of possible patch types. Each patch type is a rectangular piece of cloth with a specified design. Fortunately, Adam has come prepared and he has an unlimited quantity of every patch type. Adam has asked you to write a program to determine what the cloth will look like after sewing the patches on in a specific order and in specific locations. Note that Adam cuts off excess fabric that hangs off the edge of the quilt’s base so your program should do the same.

Help Adam by writing a program to output the completed quilt.

Input

The first line of input consists of two integers $R, C$ ($1 \leq R, C \leq 100$) giving the dimensions of the quilt. Initially, this quilt is white and is represented by a grid with $R$ rows and $C$ columns where each entry is the character ‘.’ (a period) representing white.

The second line contains a single integer $N$ ($1 \leq N \leq 100$), which is the number of different patch types. The following describes the patches:

• The first line in the description of the $i$th patch type consists of two integers $r_ i, c_ i$ ($1 \leq r_ i, c_ i \leq 100$) giving the number of rows $r_ i$ and columns $c_ i$ in this patch.

• Then $r_ i$ lines follow, each containing $c_ i$ non-whitespace ASCII characters which describes the $i$th patch type.

The next line contains a single integer $M$ ($1 \leq M \leq 100$), which is the number of patches that Adam wishes to sew onto the quilt.

The next $M$ lines of input describe the placement and types of these patches. The $j$th such line contains three integers $q_ j$ ($0 \leq q_ j < R$), $t_ j$ ($0 \leq t_ j < C$), and $p_ j$ ($1 \leq p_ j \leq N$). This means that the $p_ j$th patch is sewn onto the quilt with its top-left corner on the $q_ j, t_ j$ row/column position of the quilt. This list is given in the order that they are sewn onto the quilt.

Output

Display the completed quilt. That is, display $R$ rows and $C$ columns of ASCII characters where each position is the pattern of the quilt after sewing on the given patches whilst removing excess fabric.

7 13
3
4 4
...#
../.
./..
#...
4 4
#...
.\..
..\.
...#
1 5
*****
9
3 0 1
3 3 2
6 1 3
3 6 1
3 9 2
6 7 3
0 3 1
0 6 2
3 4 3

......#......
...../.\.....
..../...\....
...#*****#...
../.\.../.\..
./...\./...\.
#*****#*****#

2 4
5
1 4
ADAM
1 6
CRAFTS
1 7
UNUSUAL
1 7
PATCHES
1 2
20
7
0 0 3
0 1 1
0 2 4
0 3 2
1 0 5
1 2 5
1 3 5

UAPC
2022