该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

印章画就是 $N \times N$ 画布上的黑白画，其中有些格子被涂了墨水，其他格子是空的。它可以用一个 $N \times N$ （ $1 ≤ N ≤ 20$ ）的字符数组来描述，如果数组中第 $i$ 行第 $j$ 列的元素为 * 则表示画布中那个格子被涂了墨水，否则为 . 。

Bessie 有一幅想要创作的印章画，所以 Farmer John 借给了她一个 $K \times K$ （ $1 ≤ K ≤ N$ ）的印章用来作画以及一张 $N \times N$ 的空画布。 Bessie 可以反复的将印章顺时针旋转 $90∘$ 或者在网格中的任意地方盖章，但必须保证印章全部在网格内部。严格来说，对于每次盖章， Bessie 可以选择满足 $i ∈ [1, N − K + 1]$ 和 $j ∈ [1, N − K + 1]$ 的整数 $i, j$ ，然后对于 $1 ≤ i′, j′ ≤ K$ 内的每一对整数 $(i′, j′)$ ，如果印章在 $(i′, j′)$ 处有墨水，则画布中 $(i + i′ − 1, j + j′ − 1)$ 处的格子将被涂成黑色。 Bessie 可以在任意时刻旋转印章，画布中的格子一旦被涂成黑色，它将一直保持黑色。

Farmer John 想知道 Bessie 使用这个印章是否能够创造出她想要的印章画。对于 $T$ （ $1 ≤ T ≤ 100$ ）组测试用例，请帮助 Farmer John 对每一组回答这个问题。

输入格式（文件名：stamp.in）

输入的第一行包含 $T$ ，表示测试用例的数量。

对于每组测试用例，首先是整数 $N$ ，接下来 $N$ 行每行包含一个由 * 和 . 组成的字符串，表示 Bessie 想要的印章画。下一行包含 $K$ ，然后是 $K$ 行每行包含一个由 * 和 . 组成的字符串，表示 Farmer John 的印章。

连续的测试用例之间用空行隔开。

输出格式（文件名：stamp.out）

对于每组测试用例，请单独输出一行 YES 或者 NO 。

输入样例

4

2
**
*.
1
*

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

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

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

输出样例

YES
YES
NO
YES

样例解释

在第一个测试用例中， Bessie 可以按照如下顺序进行盖章：

1. 在位置 $(1, 1)$ 盖章。
2. 在位置 $(1, 2)$ 盖章。
3. 在位置 $(2, 1)$ 盖章。

在第二个测试用例中， Bessie 可以按照如下序列进行盖章：

1. 在位置 $(2, 2)$ 盖章。
2. 在位置 $(2, 1)$ 盖章。
3. 旋转 $90∘$ 。
4. 旋转 $90∘$ 。
5. 在位置 $(1, 2)$ 盖章。

在第三个测试用例中，无法对正中间的格子进行涂色。

在第四个测试用例中， Bessie 可以按照如下序列进行盖章：

1. 旋转 $90∘$ 。
2. 在位置 $(1, 1)$ 盖章。
3. 在位置 $(1, 2)$ 盖章。
4. 在位置 $(2, 2)$ 盖章。

下载测试样例

1.in

1.out

4.in

4.out