小卖部新进了一批印章,广受同学们的欢迎。大家用印章在白纸上印出各种各样的美丽图案。
印章是一个 K \times K 大小的方形,方形的有些位置可以沾染油墨,有些位置是镂空的无法沾染油墨。可以沾染油墨的地方用 *
表示,无法沾染油墨的地方用 .
表示。购买印章赠送一张 N \times N 大小的白纸,大家可以在这张方形白纸上使用印章作画。
方形印章可以将边缘平行于方形白纸的边缘盖到白纸上,也可以顺时针 90 度任意旋转,比如,一个 2 \times 2 的印章的图案如下:
.*
**
由于印章边缘必须平行于白纸边缘盖下去,因此这枚印章的原图和 90 度旋转后,一共可以得到 4 种图案:
.* *. ** **
** ** *. .*
现给出一张 N \times N 大小的方形白纸。你可以选择白纸上的任意点 i,j 作为盖印章的左上角,将印章直接盖到白纸上或者旋转任意多个 90 度后盖到白纸上,但不能让印章盖到白纸的外面。也就是说,印章在白纸上的左上角必须满足 1 \le i \le N-K+1,1 \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 100,1 \le N \le 20,1 \le K \le N。