染色矩阵

题目描述

给定两个 $N \times N$ 的矩阵 $A$ 和 $B$,其中每个元素都是 $0$ 或 $1$。

设 $A_{i,j}$、$B_{i,j}$ 分别表示 $A$、$B$ 的第 $i$ 行第 $j$ 列的元素。

判断是否可以通过旋转 $A$,使得对所有满足 $A_{i,j}=1$ 的整数对 $(i,j)$,都有 $B_{i,j}=1$。

这里,「旋转 $A$」指执行以下操作零次或多次:

对所有满足 $1 \le i,j \le N$ 的整数对 $(i,j)$,同时将 $A_{i,j}$ 替换为 $A_{N+1-j,i}$。

输入格式

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

$N$
$A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,N}$
$\vdots$
$A_{N,1}$ $A_{N,2}$ $\ldots$ $A_{N,N}$
$B_{1,1}$ $B_{1,2}$ $\ldots$ $B_{1,N}$
$\vdots$
$B_{N,1}$ $B_{N,2}$ $\ldots$ $B_{N,N}$

输出格式

如果可以通过旋转 $A$,使得对所有满足 $A_{i,j}=1$ 的整数对 $(i,j)$,都有 $B_{i,j}=1$,则输出 Yes;否则输出 No。

样例

3
0 1 1
1 0 0
0 1 0
1 1 0
0 0 1
1 1 1

Yes

初始时,$A$ 为:

0 1 1
1 0 0
0 1 0

执行一次操作后,$A$ 为:

0 1 0
1 0 1 
0 0 1

再执行一次操作后,$A$ 为:

0 1 0
0 0 1
1 1 0

此时,对所有满足 $A_{i,j}=1$ 的整数对 $(i,j)$,都有 $B_{i,j}=1$,因此应输出 Yes。

2
0 0
0 0
1 1
1 1

Yes

5
0 0 1 1 0
1 0 0 1 0
0 0 1 0 1
0 1 0 1 0
0 1 0 0 1
1 1 0 0 1
0 1 1 1 0
0 0 1 1 1
1 0 1 0 1
1 1 0 1 0

No

数据范围

• $1 \le N \le 100$
• $A$ 和 $B$ 的每个元素都是 $0$ 或 $1$。
• 输入中的所有值均为整数。