Stamp Grid

Interview

Time limit2sMemory limit1024 MB

Summary

Decide whether a K x K stamp, rotated as needed, can be placed on an empty N x N canvas to match a target pattern without inking any blank cell.

Level: Medium4 of 10
Topics: Brute force, Matrix, Simulation
Solved: No attempts yet

Problem

A stamp painting is a black and white painting on an $N \times N$ canvas, where some cells are inked and the rest are blank. It is described by an $N\times N$ array of characters ( $1\le N\le 20$ ). The $i$ th entry of the $j$ th column of the array is * if the canvas has ink at that square, and . otherwise.

Bessie wants to create a certain stamp painting. Farmer John lends her a single $K\times K$ ( $1\le K\le N$ ) stamp and an empty $N \times N$ canvas. Bessie can rotate the stamp clockwise by $90^{\circ}$ between stampings and stamp anywhere on the grid, as long as the stamp lies entirely inside the grid. Formally, she picks integers $i, j$ with $i \in [1, N-K+1]$ and $j \in [1, N-K+1]$ . For each $(i', j')$ with $1 \le i', j' \le K$ , canvas cell $(i+i'-1, j+j'-1)$ is painted black if the stamp has ink at $(i', j')$ . Once a canvas cell is painted black, it stays black.

Input

The first line contains $T$ , the number of test cases.

Each test case starts with an integer $N$ , followed by $N$ lines of * and . characters that describe Bessie's desired painting. The next line contains $K$ , followed by $K$ lines of * and . characters that describe Farmer John's stamp.

Test cases are separated by blank lines.

Output

For each test case, print "YES" or "NO" on its own line.

Examples1

Example 1

Input

4

2
**
*.
1
*

3
.**
.**
***
2
.*
**

3
...
.*.
...
3
.*.
...
...

3
**.
.**
..*
2
.*
*.

Expected output

YES
YES
NO
YES