给定两个二进制方阵 $$$a$$$ 和 $$$b$$$,大小为 $$$n \times n$$$。如果矩阵的每个元素都等于 $$$0$$$ 或 $$$1$$$,则该矩阵称为二元矩阵。您可以对矩阵 $$$a$$$ 执行任意次数(0 次或多次)的以下操作:
- 垂直异或。您选择数字 $$$j$$$ ($$$1 \le j \le n$$$) 并对所有 $$$i$$$ ($$$1 \le i \le n$$$) 执行以下操作: $$$a_{i, j} := a_{i, j} \oplus 1$$$ ($$$\oplus$$$ - 是异或运算(异或))。
- 水平异或。您选择数字 $$$i$$$ ($$$1 \le i \le n$$$) 并对所有 $$$j$$$ ($$$1 \le j \le n$$$) 执行以下操作: $$$a_{i, j} := a_{i, j} \oplus 1$$$。
请注意,$$$a$$$ 矩阵的元素在每次操作后都会发生变化。
例如,如果 $$$n=3$$$ 且矩阵 $$$a$$$ 为: $$$$$$ \begin{pmatrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix} $$$$$$ 那么以下操作序列显示了转换示例:
- 垂直异或,$$$j=1$$$。 $$$$$$ a= \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} $$$$$$
- 水平异或,$$$i=2$$$。 $$$$$$ a= \begin{pmatrix} 0 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \end{pmatrix} $$$$$$
- 垂直异或,$$$j=2$$$。 $$$$$$ a= \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix} $$$$$$
检查是否存在一系列操作使得矩阵 $$$a$$$ 等于矩阵 $$$b$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 1000$$$) — 矩阵的大小。
以下 $$$n$$$ 行包含长度为 $$$n$$$ 的字符串,由字符“0”和“1”组成 - 矩阵 $$$a$$$ 的描述。
后面是一个空行。
以下 $$$n$$$ 行包含长度为 $$$n$$$ 的字符串,由字符“0”和“1”组成 - 矩阵 $$$b$$$ 的描述。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$1000$$$。
输出
对于每个测试用例,在单独的行上输出:
- “是”,存在这样的操作序列,使得矩阵$$$a$$$变得等于矩阵$$$b$$$;
- 否则为“否”。
任何情况下都可以输出“YES”和“NO”(例如,字符串 yEs、yes、Yes 和 YES 将被识别为正数)。
示例
输入 #1
3 3 110 001 110 000 000 000 3 101 010 101 010 101 010 2 01 11 10 10
输出 #1
YES YES NO
注意
第一个测试用例在语句中进行了解释。
在第二个测试用例中,以下操作顺序是合适的:
- 水平异或,$$$i=1$$$;
- 水平异或,$$$i=2$$$;
- 水平异或,$$$i=3$$$;
可以证明,第三个测试用例中不存在操作序列使得矩阵$$$a$$$变得等于矩阵$$$b$$$。