F. Необычная матрица
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны две бинарные квадратные матрицы $$$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$$$.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.

Первая строка каждого набор входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 1000$$$) — размер матриц.

Следующие $$$n$$$ строк содержат строки длины $$$n$$$, состоящие из символов '0' и '1' — описание матрицы $$$a$$$.

Далее следует пустая строка.

Следующие $$$n$$$ строк содержат строки длины $$$n$$$, состоящие из символов '0' и '1' — описание матрицы $$$b$$$.

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

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

Для каждого набора входных данных в отдельной строке выведите:

  • «YES», если существует такая последовательность операций, что матрица $$$a$$$ станет равна матрице $$$b$$$;
  • «NO» в противном случае.

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

Пример
Входные данные
3
3
110
001
110

000
000
000
3
101
010
101

010
101
010
2
01
11

10
10
Выходные данные
YES
YES
NO
Примечание

Первый набор входных данных разобран в условии.

Во втором наборе входных данных подходит следующая последовательность операций:

  • горизонтальный xor, $$$i=1$$$;
  • горизонтальный xor, $$$i=2$$$;
  • горизонтальный xor, $$$i=3$$$;

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