给你两个数字 $$$a$$$ 和 $$$b$$$ 网格,其中 $$$n$$$ 行和 $$$m$$$ 列。网格中的所有值均为 $$$0$$$、$$$1$$$ 或 $$$2$$$。
您可以对 $$$a$$$ 执行以下操作任意次:
- 在网格中选取任意长度和宽度为 $$$\ge 2$$$ 的子矩形。您可以选择整个网格作为子矩形。
- 子矩形有四个角。取所选子矩形的任意一对对角,并将 $$$1$$$ 加上它们的值模 $$$3$$$。
- 对于未选取的一对角,将 $$$2$$$ 添加到其值模 $$$3$$$ 中。
请注意,该操作仅更改选取的子矩形的角点的值。
是否可以通过应用上述操作任意次数(可能为零)将网格$$$a$$$转换为网格$$$b$$$?
输入
第一行包含一个整数 $$$t$$$,即测试用例的数量 ($$$1 \le t \le 250$$$)。
对于每个测试用例:
第一行包含两个整数 $$$n$$$ 和 $$$m$$$,即网格中的行数和列数 ($$$2 \le n,m \le 500$$$)。
接下来的 n 行中的每一行都包含 m 个字符 — 第 $$$i$$$ 行的第 $$$j$$$ 字符代表 $$$a_{i,j}$$$。
接下来的 n 行中的每一行都包含 m 个字符 — 第 $$$i$$$ 行的第 $$$j$$$ 个字符表示 $$$b_{i,j}$$$ ($$$0 \le a_{i,j}, b_{i,j} \le 2$$$)。
保证所有测试用例的$$$n$$$总和以及所有测试用例的$$$m$$$总和不超过$$$500$$$。
输出
对于每个测试用例,如果可以将网格 $$$a$$$ 转换为网格 $$$b$$$,则打印“YES”(不带引号),否则打印“NO”(不带引号)。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。
示例
输入 #1
7 3 3 000 000 000 111 111 111 4 4 0000 0000 0000 0000 2100 1200 0012 0021 4 4 1020 1200 1210 0000 0000 1200 2200 0000 3 3 012 012 012 010 111 011 8 8 00000000 00000000 00000000 00000000 00000000 00000000 00000000 10000000 00000000 01200000 02010000 00102000 00020100 00001020 00000210 10000000 2 7 0000000 0000000 2220111 0111222 2 7 0000000 0100010 2220111 1210202
输出 #1
YES YES YES NO YES NO YES
注意
在第一个测试用例中,网格 $$$a$$$ 可以通过以下方式转换为 $$$b$$$:
$$$\begin{matrix}\fbox{0} & 0 & \fbox{0}\\ 0 & 0 & 0\\ \fbox{0} & 0 & \fbox{0}\end{matrix} \Rightarrow \begin{matrix}1 & 0 & 2\\ 0 & \fbox{0} & \fbox{0}\\ 2 & \fbox{0} & \fbox{1}\end{matrix} \Rightarrow \begin{matrix}1 & 0 & 2\\ \fbox{0} & \fbox{1} & 2\\ \fbox{2} & \fbox{2} & 2\end{matrix} \Rightarrow \begin{matrix}1 & \fbox{0} & \fbox{2}\\ 1 & 0 & 2\\ 1 & \fbox{0} & \fbox{2}\end{矩阵} \Rightarrow \begin{矩阵}1 & 1 & 1\\ 1 & \fbox{0} & \fbox{2}\\ 1 & \fbox{2} & \fbox{0}\end{矩阵} \Rightarrow \begin{矩阵}1 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1\end{矩阵}$$$
这里,在每次操作中,框突出显示的右上角和左下角都会以 $$$2$$$ 模 $$$3$$$ 递增,而左上角和右下角会以 $$$1$$$ 模 $$$3$$$ 递增。
在第四个测试用例中,可以证明使用上述操作任意次数都不可能将网格 $$$a$$$ 转换为网格 $$$b$$$。