#abc054b. [abc054_b]Template Matching

[abc054_b]Template Matching

問題文

NN 行、横 NN 列に画素が並んだ画像Aと、縦 MM 行、横 MM 列に画素が並んだテンプレート画像Bが与えられます。
画素は画像を構成する最小単位であり、ここでは 1×11×1 の正方形とします。
また、与えられる画像は全て2値画像であり、各画素の色は白と黒の2種類で表されます。

入力において、全ての画素は文字で表されており、.は白色の画素、 # は黒色の画素に対応します。
画像Aは NN 個の文字列 A1,...,ANA_1,...,A_N で表されます。
文字列 AiA_ijj 文字目は、画像Aの上から ii 番目、左から jj 番目の画素に対応します。(1i,jN)(1≦i,j≦N)
同様に、テンプレート画像Bは MM 個の文字列 B1,...,BMB_1,...,B_M で表されます。
文字列 BiB_ijj 文字目は、テンプレート画像Bの上から ii 番目、左から jj 番目の画素に対応します。(1i,jM)(1≦i,j≦M)

画像の平行移動のみ許されるとき、テンプレート画像Bが画像Aの中に含まれているかを判定してください。

制約

  • 1MN501≦M≦N≦50
  • AiA_i#. からなる長さ NN の文字列
  • BiB_i#. からなる長さ MM の文字列

入力

入力は以下の形式で標準入力から与えられる。

NN MM A1A_1 A2A_2 ::
ANA_N B1B_1 B2B_2 ::
BMB_M

出力

画像Aの中にテンプレート画像Bを含む場合は Yes、含まない場合は No を出力せよ。


入力例 1

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

出力例 1

Yes

テンプレート画像Bが、画像A中の左上の 2×22 × 2 の部分画像と右下の 2×22 × 2 の部分画像に一致するため、Yes と出力します。


入力例 2

4 1
....
....
....
....
#

出力例 2

No

画像Aは白色の画素、テンプレート画像Bは黒色の画素で構成されるため、含まれることはありません。