#abc307c. [abc307_c]Ideal Sheet

[abc307_c]Ideal Sheet

问题陈述

Takahashi有两张标有黑色方块和透明方块的纸张AABB,还有一张无限大的纸张CC,由透明方块组成。
还有一张理想的纸张XX,由黑色方块和透明方块组成。

纸张AABBXX的尺寸分别为HAH_Atimes\\times WAW_A列、HBH_Btimes\\times WBW_B列和HXH_Xtimes\\times WXW_X列。
纸张AA的方块由HAH_A个长度为WAW_A的字符串A1,A2,ldots,AHAA_1, A_2, \\ldots, A_{H_A}表示,其中包含 .#
如果AiA_i (1leqileqHA)(1\\leq i\\leq H_A)的第jj个字符(1leqjleqWA)(1\\leq j\\leq W_A)., 则从上往下数第ii行、从左往右数第jj列的方块是透明的;如果是 #,则该方块为黑色。
类似地,纸张BBXX的方块分别由HBH_B个长度为WBW_B的字符串B1,B2,ldots,BHBB_1, B_2, \\ldots, B_{H_B}HXH_X个长度为WXW_X的字符串X1,X2,ldots,XHXX_1, X_2, \\ldots, X_{H_X}表示。

Takahashi的目标是使用纸张AABB中的所有黑色方块,按照以下步骤使用纸张AABBCC来创建纸张XX

  1. 将纸张AABB沿着网格粘贴到纸张CC上。每张纸都可以通过平移来粘贴在任何地方,但不可剪切或旋转。
  2. 沿着网格从纸张CC上切出一个 HXtimesWXH_X\\times W_X 的区域。在这里,如果粘贴了纸张AABB的黑色方块,则切割出的纸张上对应方块为黑色,否则为透明。

确定Takahashi是否可以通过适当选择纸张的粘贴位置和切割区域实现他的目标,即是否可以满足以下两个条件。

  • 切割区域包含纸张AABB所有黑色方块。纸张AABB的黑色方块可能在切割区域上重叠。
  • 切割出的纸张与纸张XX完全一致,没有旋转或翻转。

约束条件

  • 1leqHA,WA,HB,WB,HX,WXleq101\\leq H_A, W_A, H_B, W_B, H_X, W_X\\leq 10
  • HA,WA,HB,WB,HX,WXH_A, W_A, H_B, W_B, H_X, W_X都是整数。
  • AiA_i是一个长度为WAW_A的字符串,由 .# 组成。
  • BiB_i是一个长度为WBW_B的字符串,由 .# 组成。
  • XiX_i是一个长度为WXW_X的字符串,由 .# 组成。
  • 纸张AABBXX中至少包含一个黑色方块。

输入格式

输入以以下格式从标准输入中给出:

HAH_A WAW_A A1A_1 A2A_2 vdots\\vdots AHAA_{H_A} HBH_B WBW_B B1B_1 B2B_2 vdots\\vdots BHBB_{H_B} HXH_X WXW_X X1X_1 X2X_2 vdots\\vdots XHXX_{H_X}

输出格式

如果Takahashi能够实现问题描述中的目标,则输出Yes;否则输出No


样例输入1

3 5
#.#..
.....
.#...
2 2
#.
.#
5 3
...
#.#
.#.
.#.
...

样例输出1

Yes

首先,将纸张AA粘贴到纸张CC上,如下图所示。

 $\\vdots$

.......
.#.#...
cdots\\cdots.......cdots\\cdots ..#....
.......
vdots\\vdots

接下来,将纸张BB粘贴到纸张AA的左上角对齐位置,如下图所示。

 $\\vdots$

.......
.#.#...
cdots\\cdots..#....cdots\\cdots ..#....
.......
vdots\\vdots

现在,从上面这个图中切割出一个 5times35\\times 3 的区域,切割出的纸张如下图所示。

...
#.#
.#.
.#.
...

这个切割出的纸张包含了纸张AABB的所有黑色方块,并且与纸张XX完全一致,满足了条件。

因此,输出Yes


样例输入2

2 2
#.
.#
2 2
#.
.#
2 2
##
##

样例输出2

No

请注意,在粘贴纸张时,不能旋转或翻转纸张AABB


样例输入3

1 1
#
1 2
##
1 1
#

样例输出3

No

无论如何粘贴或切割,都无法切割出包含纸张BB的所有黑色方块的纸张,因此无法满足第一个条件。因此,输出No


样例输入4

3 3
###
...
...
3 3
#..
#..
#..
3 3
..#
..#
###

样例输出4

Yes