理想纸片

题目描述

高桥君有两张由黑色方格和透明方格组成的纸片 $A$ 和 $B$,以及一张由透明方格组成的无限大的纸片 $C$。

此外,还有一张高桥君的「理想纸片」$X$,它由黑色方格和透明方格组成。

纸片 $A$、$B$、$X$ 的大小分别为 $H_A$ 行 $\times$ $W_A$ 列、$H_B$ 行 $\times$ $W_B$ 列、$H_X$ 行 $\times$ $W_X$ 列。

纸片 $A$ 的方格用 $H_A$ 个长度为 $W_A$ 的、由 . 和 # 组成的字符串 $A_1, A_2, \ldots, A_{H_A}$ 表示。

如果 $A_i$ $(1\leq i\leq H_A)$ 的第 $j$ 个字符 $(1\leq j\leq W_A)$ 是 .,则该方格为透明;如果是 #,则该方格为黑色。

同样,纸片 $B$ 和 $X$ 的方格分别用 $H_B$ 个长度为 $W_B$ 的字符串 $B_1, B_2, \ldots, B_{H_B}$,以及 $H_X$ 个长度为 $W_X$ 的字符串 $X_1, X_2, \ldots, X_{H_X}$ 表示。

高桥君的目标是按照以下步骤,在纸片 $A$、$B$、$C$ 上操作,使用纸片 $A$ 和 $B$ 中的所有黑色方格,制作出纸片 $X$。

1. 将纸片 $A$ 和 $B$ 沿网格贴在纸片 $C$ 上。各纸片可以通过平移贴在任意位置,但不能剪开或旋转。
2. 从纸片 $C$ 中沿网格剪出一个 $H_X\times W_X$ 的区域。此时,剪出的纸片的方格,如果该位置贴有纸片 $A$ 或 $B$ 的黑色方格则为黑色,否则为透明。

请判断高桥君能否通过适当选择纸片的粘贴位置和剪出的区域来实现目标,即能否同时满足以下两个条件。

• 剪出的纸片包含纸片 $A$ 和 $B$ 的全部黑色方格。纸片 $A$ 和 $B$ 的黑色方格在剪出的纸片上可以重叠。
• 剪出的纸片与纸片 $X$ 完全一致(不进行旋转或翻转)。

输入格式

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

$H_A$ $W_A$
$A_1$
$A_2$
$\vdots$
$A_{H_A}$
$H_B$ $W_B$
$B_1$
$B_2$
$\vdots$
$B_{H_B}$
$H_X$ $W_X$
$X_1$
$X_2$
$\vdots$
$X_{H_X}$

输出格式

如果高桥君能实现题目描述的目标,输出 Yes;否则输出 No。

样例

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

Yes

首先,将纸片 $A$ 贴在纸片 $C$ 上,如下图所示。

     ⋮
  .......  
  .#.#...  
⋯.......⋯
  ..#....  
  .......  
     ⋮

接下来,将纸片 $B$ 与纸片 $A$ 的左上角对齐贴上,如下图所示。

     ⋮
  .......  
  .#.#...  
⋯..#....⋯
  ..#....  
  .......  
     ⋮

然后,以上图所示区域第 1 行第 2 列的方格为左上角,剪出一个 $5\times 3$ 的区域,如下图所示。

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

这包含了纸片 $A$ 和 $B$ 的全部黑色方格,并与纸片 $X$ 一致,满足条件。

因此输出 Yes。

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

No

注意粘贴时不能旋转或翻转纸片 $A$ 和 $B$。

1 1
#
1 2
##
1 1
#

No

无论怎样粘贴和剪取,都无法剪出包含纸片 $B$ 全部黑色方格的纸片,因此无法满足第一个条件。

因此输出 No。

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

Yes

数据范围

• $1 \le H_A, W_A, H_B, W_B, H_X, W_X \le 10$
• $H_A, W_A, H_B, W_B, H_X, W_X$ 是整数
• $A_i$ 是由 . 和 # 组成的长度为 $W_A$ 的字符串
• $B_i$ 是由 . 和 # 组成的长度为 $W_B$ 的字符串
• $X_i$ 是由 . 和 # 组成的长度为 $W_X$ 的字符串
• 纸片 $A$、$B$、$X$ 各自至少包含一个黑色方格