Little Johny has just learned to play around with a photo editing tool. He has become quite an expert in a very short time. His signature works are some wonderful collages created by pasting clipped parts of different photographs one on top of another. While we dont have the time and tool to play like Johny, we do have the luxury to simplify the task to mold it into a rather simple problem. Our clipped photographs are fixed sized character grids representing some patterns. Parts of the grids may be filled with the dot . character representing transparent pixels, and the remaining opaque pixels would be represented with lower case letters. Here are two sample grids representing some patterns: ..xxx ..... .x..x ..... ....x .oo.. x...x ..o.. .xx.. ..o.. Grid 1 Grid 2 To keep it simple, we would use the same lower case letter in one grid. The lower case letter in one grid may or may not be used in another grid. Our task is to place these grids one on top of another in such a way that we can come up with a target pattern (possibly of different size). Placing the grids one on another is simple, we dont have to bother about rotation, reflection, or any such transformation except for translation. We need to ensure that an opaque pixel does not hide another opaque pixel. Some part of a grid may be outside the Target Image when the part outside, contains only transparent pixels. The following example shows valid and invalid merging of Grid 1 and Grid 2: ..xxx. ..xxx. .x..x. .xoox. ..oox. ...ox. x..ox. x..ox. .xxo.. .xx... ..xxx. .oo.x. ..o.x. x.o.x. .xx... Target 1 Target 2 Target 3 Valid Valid Invalid Given the grids representing the patterns and a grid representation of the target pattern itself, we want to know whether it is possible to produce the target. As we can see, given Grid 1 and Grid 2, we could produce Target 1 and Target 2, but not Target 3. Input There can be several test cases. The first line of input gives you the number of test cases, T (1 ≤ T ≤ 1000). Then T test cases follow. Each test case starts with the number of grids N (1 ≤ N ≤ 14) representing the given patterns. Each of the patterns is represented by a 5 × 5 grid containing lower case letters and dots only. A blank line would follow every pattern. At the end of the N patterns, the target pattern would be given. Two integers R, C (1 ≤ R, C ≤ 20) will give the dimension of the grid representing the target. In the next R lines, the R × C grid would present the target pattern. As with the N patterns, the target would contain lower case letters and dots only. There will be a blank line following this pattern.
2/3 Output For each of the test cases, youd have to print the serial number (Case x:) of the test case followed by ‘Yes’ or ‘No’ depending on whether the target can be reached or not. You should note that to achieve the target you must use each and every given pattern for that test case exactly once. If there are duplicate patterns in a test case, you must treat them as separate entities. Sample Input 2 2 ..... .x... ..x.. .xxx. ..xx. ..... ...yy ....y y.... yy... 57 ...yy.. ..x.y.. y..x... yyxxx.. ...xx.. 2 ..... .x... ..x.. .xxx. ..xx. ..... ...yy ..y.y y.... yy... 57 ...yy.. ..y.y.. y..x... yyxxx.. ...xx..
3/3 Sample Output Case 1: Yes Case 2: No