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

Даны две матрицы $$$A$$$ и $$$B$$$ размером $$$n \times m$$$, заполненные целыми числами от $$$0$$$ до $$$10^9$$$. Вы можете выполнять следующие операции над матрицей $$$A$$$ в любом порядке любое количество раз:

  • &=: выбрать два целых числа $$$i$$$ и $$$x$$$ ($$$1 \le i \le n$$$, $$$x \ge 0$$$) и заменить каждый элемент в строке $$$i$$$ на результат побитового И между числом $$$x$$$ и этим элементом. Формально, для каждого $$$j \in [1, m]$$$ элемент $$$A_{i,j}$$$ заменяется на $$$A_{i,j} \text{ & } x$$$;
  • |=: выбрать два целых числа $$$j$$$ и $$$x$$$ ($$$1 \le j \le m$$$, $$$x \ge 0$$$) и заменить каждый элемент в столбце $$$j$$$ на результат побитового ИЛИ между числом $$$x$$$ и этим элементом. Формально, для каждого $$$i \in [1, n]$$$ элемент $$$A_{i,j}$$$ заменяется на $$$A_{i,j} \text{ | } x$$$;

В разных операциях можно выбирать разные значения $$$x$$$.

Определите, возможно ли преобразовать матрицу $$$A$$$ в матрицу $$$B$$$ с помощью нескольких (возможно, нуля) указанных операций.

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

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

Каждый набор входных данных задается следующим образом:

  • первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 10^3$$$; $$$n \cdot m \le 10^3$$$) — размеры матриц $$$A$$$ и $$$B$$$;
  • в следующих $$$n$$$ строках содержится описание матрицы $$$A$$$, где $$$i$$$-я строка содержит $$$m$$$ целых чисел $$$A_{i,1}, A_{i,2}, \dots, A_{i,m}$$$ ($$$0 \le A_{i,j} \le 10^9$$$);
  • в следующих $$$n$$$ строках содержится описание матрицы $$$B$$$, где $$$i$$$-я строка содержит $$$m$$$ целых чисел $$$B_{i,1}, B_{i,2}, \dots, B_{i,m}$$$ ($$$0 \le B_{i,j} \le 10^9$$$).
Выходные данные

Для каждого набора входных данных выведите Yes, если можно преобразовать $$$A$$$ в $$$B$$$, или No в противном случае. Каждую букву можно выводить в любом регистре.

Пример
Входные данные
4
1 1
12
13
2 2
10 10
42 42
21 21
21 21
2 2
74 10
42 106
21 85
85 21
2 4
1 2 3 4
5 6 7 8
3 2 3 4
1 0 1 0
Выходные данные
Yes
Yes
No
Yes
Примечание

Рассмотрим второй набор входных данных и приведем последовательность операций, позволяющих получить из матрицы $$$A$$$ матрицу $$$B$$$:

Изначально матрица выглядит так:

$$$\begin{bmatrix} 10&10\\ 42&42\\ \end{bmatrix}$$$

Применим операцию первого типа с параметрами $$$i = 1$$$ и $$$x = 0$$$. В результате получим матрицу:

$$$\begin{bmatrix} 0&0\\ 42&42\\ \end{bmatrix}$$$

Применим операцию первого типа с параметрами $$$i = 2$$$ и $$$x = 0$$$. В результате получим матрицу:

$$$\begin{bmatrix} 0&0\\ 0&0\\ \end{bmatrix}$$$

Применим операцию второго типа с параметрами $$$j = 1$$$ и $$$x = 21$$$. В результате получим матрицу:

$$$\begin{bmatrix} 21&0\\ 21&0\\ \end{bmatrix}$$$

Применим операцию второго типа с параметрами $$$j = 2$$$ и $$$x = 21$$$. В результате получим матрицу:

$$$\begin{bmatrix} 21&21\\ 21&21\\ \end{bmatrix}$$$

Таким образом, мы преобразовали матрицу $$$A$$$ в матрицу $$$B$$$.