Matrix Transformation
Contest: Educational Codeforces Round 173 (Rated for Div. 2)
Difficulty rating: 2300
Tags: bitmasks, brute force, data structures, dfs and similar, graphs, greedy, implementation

You are given two matrices $$$A$$$ and $$$B$$$ of size $$$n \times m$$$, filled with integers between $$$0$$$ and $$$10^9$$$. You can perform the following operations on matrix $$$A$$$ in any order and any number of times:

- &=: choose two integers $$$i$$$ and $$$x$$$ ($$$1 \le i \le n$$$, $$$x \ge 0$$$) and replace each element in row $$$i$$$ with the result of the bitwise AND operation between $$$x$$$ and that element. Formally, for every $$$j \in [1, m]$$$, the element $$$A_{i,j}$$$ is replaced with $$$A_{i,j} \text{ & } x$$$;
- |=: choose two integers $$$j$$$ and $$$x$$$ ($$$1 \le j \le m$$$, $$$x \ge 0$$$) and replace each element in column $$$j$$$ with the result of the bitwise OR operation between $$$x$$$ and that element. Formally, for every $$$i \in [1, n]$$$, the element $$$A_{i,j}$$$ is replaced with $$$A_{i,j} \text{ | } x$$$.

The value of $$$x$$$ may be chosen differently for different operations.

Determine whether it is possible to transform matrix $$$A$$$ into matrix $$$B$$$ using the given operations any number of times (including zero).

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Then, $$$t$$$ test cases follow.

Each test case is given as follows:

- the first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^3$$$; $$$n \cdot m \le 10^3$$$) — the dimensions of the matrices $$$A$$$ and $$$B$$$;
- the following $$$n$$$ lines describe the matrix $$$A$$$, where the $$$i$$$-th line contains $$$m$$$ integers $$$A_{i,1}, A_{i,2}, \dots, A_{i,m}$$$ ($$$0 \le A_{i,j} \le 10^9$$$);
- the following $$$n$$$ lines describe the matrix $$$B$$$, where the $$$i$$$-th line contains $$$m$$$ integers $$$B_{i,1}, B_{i,2}, \dots, B_{i,m}$$$ ($$$0 \le B_{i,j} \le 10^9$$$).

Output format:
For each test case, output Yes if it is possible to transform the matrix $$$A$$$ into the matrix $$$B$$$; otherwise, output No. Each letter can be output in any case, upper or lower.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Let's consider the second set of input data and show a sequence of operations that transforms matrix $$$A$$$ into matrix $$$B$$$:

Initially, the matrix looks like this:

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

Apply an operation of the first type with parameters $$$i = 1$$$ and $$$x = 0$$$. As a result, we get the matrix:

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

Apply an operation of the first type with parameters $$$i = 2$$$ and $$$x = 0$$$. As a result, we get the matrix:

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

Apply an operation of the second type with parameters $$$j = 1$$$ and $$$x = 21$$$. As a result, we get the matrix:

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

Apply an operation of the second type with parameters $$$j = 2$$$ and $$$x = 21$$$. As a result, we get the matrix:

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

Thus, we have transformed matrix $$$A$$$ into matrix $$$B$$$.

Example input:
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

Example output:
Yes
Yes
No
Yes

Editorial:
Every operation which affects multiple bits can be split into several operations which only affect one bit. For example, if you make an  |= operation with $$$x=11$$$, it is the same as making three  |= operations with $$$x=1$$$, $$$x=2$$$ and $$$x=8$$$. So, let's solve the problem for each bit separately.
If we consider only one bit, the problem becomes the following one:
You are given a binary matrix $$$A$$$, and you have to check if it is possible to transform it into another binary matrix $$$B$$$. The operations you can make are "set all elements in some row to $$$0$$$" and "set all elements in some column to $$$1$$$".
Let's find all cells where $$$A_{i,j} \ne B_{i,j}$$$. If $$$A_{i,j} = 0$$$ and $$$B_{i,j} = 1$$$, then it means that we definitely have to apply an operation to the $$$j$$$-th column. Otherwise, if $$$A_{i,j} = 1$$$ and $$$B_{i,j} = 0$$$, then we definitely have to apply an operation to the $$$i$$$-th row. That way, we can find the operations we definitely need to apply. It's pretty obvious that we don't need to do the same operation twice — if we do the same operation to the same row/column twice, we can discard the first operation, since it will be overwritten by the last operation.
But these are not all operations we need to apply. Suppose $$$B_{i,j} = 0$$$, and we change everything in the $$$j$$$-th column to $$$1$$$. Then, we have to make an operation with the $$$i$$$-th row to set $$$B_{i,j}$$$ back to $$$0$$$. This means that after you apply an operation to the $$$j$$$-th column, you have to do an operation with the $$$i$$$-th row. Same when $$$B_{i,j} = 1$$$: after you apply an operation to the $$$i$$$-th row, you have to do an operation with the $$$j$$$-th column.
Let's build a graph where every operation will be represented by a vertex, and a directed edge $$$x \rightarrow y$$$ means that, if you apply the operation $$$x$$$, the operation $$$y$$$ must be applied after that. Some vertices of this graph represent operations which we definitely need to apply. If there is a cycle reachable from one of these vertices, the transformation is impossible, since we will apply operations forever and never get the matrix we need. But if there is no cycle reachable from any operation we need to apply, then we can "mark" all operations reachable from the operations we need, and apply them in the order of topological sorting, and we will get exactly the matrix $$$B$$$ (for every cell that was changed, the last operation applied to it will make it correct; and we enforced that we need to apply operations to all cells that must change).
Searching for a cycle in a directed graph can be done with "three-colored DFS" — a modification of DFS which, for each vertex, maintains one of three states — either this vertex wasn't reached by DFS at all, or it was already reached and is on the DFS stack, or this vertex was already fully processed (both reached by DFS and deleted from the DFS stack). This way, we can find a back-edge that creates the cycle as follows: if we try to go from a vertex to another vertex which is on the DFS stack, it means that we have found a cycle. There are other methods of cycle detection, but this one is the most common.
If for every bit, we can make the transformations we need, the answer is Yes. Otherwise, the answer is No. The solution works in $$$O(n m \log A)$$$.