Hanimon

Time Limit : 3 sec, Memory Limit : 262144 KB

Problem J: Hanimon

ハニカムモンスターはハニカム模様の六角形状の不思議な生き物である。

ハニカムモンスターには様々なサイズのものがあり、一辺がN個の正六角形のマスから成るハニカムモンスターをサイズNのハニカムモンスターとする。

一方、聖なる模様はハニカムモンスターと同じく、六角形として定義され1辺がP個の正六角形のマスから成る聖なる模様をサイズPの聖なる模様とする。

ハニカムモンスターと聖なる模様の形の例を以下に示す。サイズは1辺の正六角形のマスの数に対応する。

sample1.png
図1:サイズの例

sample2.png
図2:ハニカムモンスターと聖なる模様の例 (Sample Input 1)

ハニカムモンスターと聖なる模様の各マスには色が着いており0と1によって表される。

サイズPQ個の聖なる模様のすべてを含むハニカムモンスターは伝説のハニモンと呼ばれている。

サイズNのハニカムモンスターとその模様、Q個のサイズPの聖なる模様が与えられるので、 そのハニカムモンスターが伝説のハニモンであるかどうかを判定するプログラムを作成せよ。

Input

入力は次の形式で表される。

N P Q
(空行)
ハニカムモンスターの模様の情報
(空行)
1つ目の聖なる模様の情報
(空行)
2つ目の聖なる模様の情報
(空行)
...
Qつ目の聖なる模様の情報

N,P,Qはそれぞれハニカムモンスターのサイズ,聖なる模様のサイズ,聖なる模様の個数を表す。

サイズNのハニカムモンスターの模様の情報は以下の様に2×N-1行で与えられる。

N個のマス
N+1個のマス
N+2個のマス
.
.
2×N-2個のマス
2×N-1個のマス
2×N-2個のマス
.
.
N+2個のマス
N+1個のマス
N個のマス

サイズPの聖なる模様の情報は以下の様に2×P-1行で与えられる。

P個のマス
P+1個のマス
P+2個のマス
.
.
2×P-2個のマス
2×P-1個のマス
2×P-2個のマス
.
.
P+2個のマス
P+1個のマス
P個のマス

それぞれのマスの間には1つの空白が入り、マスには0か1が入る。

Constraints

  • 1 ≤ N ≤ 1000
  • 1 ≤ P ≤ 50
  • 1 ≤ Q ≤ 100
  • 同じ模様の聖なる模様が複数個与えられることは無い。
  • ハニカムモンスターのあるマスについて、2つ以上の聖なる模様の一部分であることがある。
  • ハニカムモンスターと聖なる模様は回転できない。

Output

伝説のハニモンなら YES を、そうでなければ NO を一行に出力せよ。

Sample Input 1

6 2 2

1 1 1 1 1 1
1 0 0 0 0 1 0
1 0 1 0 0 1 0 1
1 1 1 1 1 1 1 0 0
0 0 1 0 0 0 1 0 1 1
1 1 1 0 1 0 0 1 1 0 1
0 1 0 1 0 0 1 1 1 0
0 1 1 1 1 0 0 1 1
0 0 0 0 1 0 1 0
1 1 1 0 1 1 0
0 1 1 0 0 1

0 1
1 1 1
1 0

0 0
0 1 0
1 1

Sample Output 1

YES

Sample Input 2

6 2 2

0 0 0 1 0 0
1 0 1 1 0 0 1
1 0 1 0 0 1 1 0
0 1 0 1 0 0 0 0 0
0 0 1 1 1 1 0 0 1 1
0 0 0 1 0 0 1 1 0 0 0
0 0 1 0 0 1 1 0 1 1
1 0 0 1 1 1 1 1 1
0 1 0 0 1 0 0 0
0 0 1 0 1 0 0
0 1 1 0 1 0

1 0
1 0 0
1 1

0 1
0 0 1
0 1

Sample Output 2

NO