Вам даны две таблицы \(a\) и \(b\) с \(n\) строками и \(m\) столбцами. Все значения в таблицах равны \(0\), \(1\) или \(2\).
Вы можете выполнить следующую операцию над \(a\) любое количество раз:
- Выберите в таблице любой подпрямоугольник с длиной и шириной \(\ge 2\). Вы можете выбрать в качестве подпрямоугольника всю таблицу.
- У подпрямоугольника есть четыре угла. Выберите любую пару диагонально противоположных углов выбранного подпрямоугольника и прибавьте к их значениям \(1\) по модулю \(3\).
- Для оставшейся пары углов, прибавьте к их значениям \(2\) по модулю \(3\).
Обратите внимание, что эта операция изменяет значения только углов выбранного подпрямоугольника.
Можно ли преобразовать таблицу \(a\) в таблицу \(b\), применив описанную выше операцию любое количество раз (возможно, ноль)?
Выходные данные
Для каждого набора входных данных выведите «YES» (без кавычек), если возможно преобразовать таблицу \(a\) в таблицу \(b\), и «NO» (без кавычек) в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «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\) с помощью любого числа вышеупомянутых операций.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
YES
YES
YES
NO
YES
NO
YES
|