Вам даны две бинарные квадратные матрицы \(a\) и \(b\) размера \(n \times n\). Матрица называется бинарной, если каждый её элемент равен \(0\) или \(1\). Вы можете делать следующие операции над матрицей \(a\) произвольное число раз (0 или более):
- вертикальный xor. Вы выбираете число \(j\) (\(1 \le j \le n\)) и для всех \(i\) (\(1 \le i \le n\)) делаете следующее: \(a_{i, j} := a_{i, j} \oplus 1\) (\(\oplus\) — это операция xor (исключающее или)).
- горизонтальный xor. Вы выбираете число \(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} \(\) Тогда следующий набор операций показывает пример преобразований:
- вертикальный xor, \(j=1\). \(\) a= \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} \(\)
- горизонтальный xor, \(i=2\). \(\) a= \begin{pmatrix} 0 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \end{pmatrix} \(\)
- вертикальный xor, \(j=2\). \(\) a= \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix} \(\)
Проверьте, существует ли такая последовательность операций, что матрица \(a\) станет равна матрице \(b\).
Выходные данные
Для каждого набора входных данных в отдельной строке выведите:
- «YES», если существует такая последовательность операций, что матрица \(a\) станет равна матрице \(b\);
- «NO» в противном случае.
Вы можете выводить «YES» и «NO» в любом регистре (например, строки yEs, yes, Yes и YES будут распознаны как положительный ответ).
Примечание
Первый набор входных данных разобран в условии.
Во втором наборе входных данных подходит следующая последовательность операций:
- горизонтальный xor, \(i=1\);
- горизонтальный xor, \(i=2\);
- горизонтальный xor, \(i=3\);
Можно доказать, что в третьем наборе входных данных не существует последовательности операций, так что матрица \(a\) становится равной матрице \(b\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
110
001
110
000
000
000
3
101
010
101
010
101
010
2
01
11
10
10
|
YES
YES
NO
|