3249 - 印章游戏

题目描述

小卖部新进了一批印章,广受同学们的欢迎。大家用印章在白纸上印出各种各样的美丽图案。

印章是一个 K \times K 大小的方形,方形的有些位置可以沾染油墨,有些位置是镂空的无法沾染油墨。可以沾染油墨的地方用 * 表示,无法沾染油墨的地方用 . 表示。购买印章赠送一张 N \times N 大小的白纸,大家可以在这张方形白纸上使用印章作画。

方形印章可以将边缘平行于方形白纸的边缘盖到白纸上,也可以顺时针 90 度任意旋转,比如,一个 2 \times 2 的印章的图案如下:

.*
**

由于印章边缘必须平行于白纸边缘盖下去,因此这枚印章的原图和 90 度旋转后,一共可以得到 4 种图案:

.*   *.   **   **
**   **   *.   .*

现给出一张 N \times N 大小的方形白纸。你可以选择白纸上的任意点 i,j 作为盖印章的左上角,将印章直接盖到白纸上或者旋转任意多个 90 度后盖到白纸上,但不能让印章盖到白纸的外面。也就是说,印章在白纸上的左上角必须满足 1 \le i \le N-K+11 \le j \le N-K+1。白纸上已经盖过印章的地方,也可以重复的盖

因此,上述的 2 \times 2 大小的印章,在 3 \times 3 大小的白纸上作画,通过旋转盖 4 次,可以盖出下面这张美丽的印章画。

.*.
***
.*.

现给出一张 N \times N 大小的盖好的方形印章画,并给出一枚 K \times K 大小的方形印章图案,请编程计算该印章画是否可能由这枚印章盖出来?

输入

本题有多组测试数据。

1 行读入整数 T 表示测试数据的组数。

对于每组测试数据,先给出一个整数 N ,表示盖好的方形印章画的边长。

再给出 N 行,每行有 N 个字符的盖好的印章画。

再给出整数 K ,表示方形印章的边长。

再给出 K 行,每行有 K 个字符的印章图案。

每组测试数据前都会有一个空行和之前的数据分隔。

输出

输出 T 行,对于每组测试数据,如果该印章画可以由这枚印章盖出来,请输出 YES,否则请输出 NO

样例

输入

5

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

2
**
*.
1
*

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

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

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

输出

YES
YES
YES
NO
YES
说明

数据范围

对于 100\% 的数据,满足 1 \le T \le 1001 \le N \le 201 \le K \le N

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 143
通过人数 56
金币数量 0 枚
难度 基础


上一题 下一题