Corner Twist
Contest: Codeforces Round 956 (Div. 2) and ByteRace 2024
Difficulty rating: 1200
Tags: constructive algorithms, greedy, implementation, math

You are given two grids of numbers $$$a$$$ and $$$b$$$, with $$$n$$$ rows and $$$m$$$ columns. All the values in the grid are $$$0$$$, $$$1$$$ or $$$2$$$.

You can perform the following operation on $$$a$$$ any number of times:

- Pick any subrectangle in the grid with length and width $$$\ge 2$$$. You are allowed to choose the entire grid as a subrectangle.
- The subrectangle has four corners. Take any pair of diagonally opposite corners of the chosen subrectangle and add $$$1$$$ to their values modulo $$$3$$$.
- For the pair of corners not picked, add $$$2$$$ to their values modulo $$$3$$$.

Note that the operation only changes the values of the corners of the picked subrectangle.

Is it possible to convert the grid $$$a$$$ into grid $$$b$$$ by applying the above operation any number of times (possibly zero)?

Input format:
The first line contains an integer $$$t$$$, the number of testcases ($$$1 \le t \le 250$$$).

For each testcase:

The first line contains two integers $$$n$$$ and $$$m$$$, the number of rows and columns in the grid ($$$2 \le n,m \le 500$$$).

Each of the next n lines contain m characters — the $$$j$$$-th character of the $$$i$$$-th line represents $$$a_{i,j}$$$.

Each of the next n lines contain m characters — the $$$j$$$-th character of the $$$i$$$-th line represents $$$b_{i,j}$$$ ($$$0 \le a_{i,j}, b_{i,j} \le 2$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases and the sum of $$$m$$$ over all test cases do not exceed $$$500$$$.

Output format:
For each test case print "YES" (without quotes) if it is possible to convert grid $$$a$$$ into grid $$$b$$$ and "NO" (without quotes) otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first testcase, grid $$$a$$$ can be converted into $$$b$$$ in the following manner:

$$$\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{matrix} \Rightarrow \begin{matrix}1 & 1 & 1\\ 1 & \fbox{0} & \fbox{2}\\ 1 & \fbox{2} & \fbox{0}\end{matrix} \Rightarrow \begin{matrix}1 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1\end{matrix}$$$

Here, in each operation, the top-right and bottom-left corners highlighted by a box are incremented by $$$2$$$ modulo $$$3$$$, while the top-left and bottom-right corners are incremented by $$$1$$$ modulo $$$3$$$.

In the fourth testcase, it can be proven that it is not possible to convert grid $$$a$$$ into grid $$$b$$$ using the above-mentioned operations any number of times.

Example input:
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

Example output:
YES
YES
YES
NO
YES
NO
YES

Editorial:
Notice how the operations affect each row and column. The problem offers a really simple solution: the sum of each row and each column modulo $$$3$$$ needs to remain constant throughout all the operations. It is easy to see that this is a necessary condition.
Let's prove that this is sufficient as well.
Notice that using the 2x2 versions of the operations defined in the statement, i.e., addition of $$$\begin{matrix}1 & 2 \\ 2 & 1\end{matrix}$$$ or $$$\begin{matrix}2 & 1 \\ 1 & 2\end{matrix}$$$ along the corners of a 2x2 square can be used to generate the same result as the operation applied on any rectangle. For instance, we can combine two 2x2 operations sideways to get a 2x3 operation:
$$$$$$\begin{matrix}1 & \fbox{2+1} & 2\\ 2 & \fbox{1+2} & 1\end{matrix} \equiv \begin{matrix}1 & 0 & 2\\ 2 & 0 & 1\end{matrix} \pmod{3}$$$$$$ Let the grid $$$a$$$ and $$$b$$$ have $$$n$$$ rows and $$$m$$$ columns, you can iterate over $$$i$$$ thorugh $$$1\ldots n-1$$$ and for $$$i$$$'s each iteration, $$$j$$$ through $$$1\ldots m-1$$$.
• If $$$a[i][j] + 1 \equiv b[i][j] \pmod{3}$$$, add $$$\begin{matrix}1 & 2 \\ 2 & 1\end{matrix}$$$ to the subrectange of $$$a$$$ starting at $$$a[i[j]$$$.
• If $$$a[i][j] + 2 \equiv b[i][j] \pmod{3}$$$, add $$$\begin{matrix}2 & 1 \\ 1 & 2\end{matrix}$$$ to the subrectange of $$$a$$$ starting at $$$a[i[j]$$$.
• Make no changes otherwise.
We see that it is always possible to make all the elements in the first $$$n-1$$$ rows and $$$m-1$$$ columns equal using this method.
Note that the sum of each row and each column stays constant after each operation. If $$$b$$$ is derived from $$$a$$$ using these operations, then all the values for the remaining $$$n + m - 1$$$ elements of the grid can be uniquely determined using the row and column sums and need to be equal. Hence, proving sufficiency.