B. Поворот угла
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны две таблицы $$$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 символов — $$$j$$$-й символ $$$i$$$-й строки равен $$$a_{i,j}$$$.

Каждая из следующих n строк содержат по m символов — $$$j$$$-й символ $$$i$$$-й строки равен $$$b_{i,j}$$$ ($$$0 \le a_{i,j}, b_{i,j} \le 2$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных и сумма $$$m$$$ по всем наборам входных данных не превосходят $$$500$$$.

Выходные данные

Для каждого набора входных данных выведите «YES» (без кавычек), если возможно преобразовать таблицу $$$a$$$ в таблицу $$$b$$$, и «NO» (без кавычек) в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
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
Выходные данные
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{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}$$$

Здесь в каждой операции верхний правый и нижний левый углы, выделенные рамкой, увеличиваются на $$$2$$$ по модулю $$$3$$$, а верхний левый и нижний правый углы увеличиваются на $$$1$$$ по модулю $$$3$$$.

Для четвертого набора входных данных можно показать, что невозможно преобразовать таблицу $$$a$$$ в таблицу $$$b$$$ с помощью любого числа вышеупомянутых операций.