/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
H 行 W 列の非負整数からなる行列 A が与えられます。
あなたは以下の操作を任意の回数(0 回でもよい)行うことができます。
- 1 \le i \le H を満たす整数 i と非負整数 X を選んで、行列 A の i 行目の各要素 A_{i,j} を A_{i,j}\ \mathrm{XOR}\ X で置き換える。
- 1 \le j \le W を満たす整数 j と非負整数 X を選んで、行列 A の j 列目の各要素 A_{i,j} を A_{i,j}\ \mathrm{XOR}\ X で置き換える。
H 行 W 列の非負整数および -1 からなる行列 B が与えられます。
操作によって B_{i,j} \neq -1 となる整数の組 (i,j) 全てに対して A_{i,j}=B_{i,j} となるようにすることができるか判定してください。
\mathrm{XOR} とは
非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。
- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に k 個の整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots p_k の順番によらないことが証明できます。
制約
- 1 \le H,W \le 500
- 0 \le A_{i,j} < 2^{30}
- -1 \le B_{i,j} < 2^{30}
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
H W
A_{1,1} A_{1,2} \dots A_{1,W}
A_{2,1} A_{2,2} \dots A_{2,W}
\vdots
A_{H,1} A_{H,2} \dots A_{H,W}
B_{1,1} B_{1,2} \dots B_{1,W}
B_{2,1} B_{2,2} \dots B_{2,W}
\vdots
B_{H,1} B_{H,2} \dots B_{H,W}
出力
条件を満たすことができるならば Yes を、そうでないならば No を出力せよ。
入力例 1
2 2 1 2 3 4 -1 3 1 7
出力例 1
Yes
始め、A は以下のようになっています。
1 2 3 4
2 列目に対して X=1 として操作を行うと、以下のようになります。
1 3 3 5
2 行目に対して X=2 として操作を行うと、以下のようになります。
1 3 1 7
よって、条件を満たすことができるため Yes を出力します。
入力例 2
2 2 1 2 3 4 5 3 1 7
出力例 2
No
この場合、どのようにしても条件を満たすことができないため No を出力します。
Problem Statement
You are given an H-by-W matrix A consisting of non-negative integers.
You can perform the following operations any number of times (possibly zero):
- Choose an integer i satisfying 1 \le i \le H and a non-negative integer X, and replace each element A_{i,j} in the i-th row of the matrix A with A_{i,j}\ \mathrm{XOR}\ X.
- Choose an integer j satisfying 1 \le j \le W and a non-negative integer X, and replace each element A_{i,j} in the j-th column of the matrix A with A_{i,j}\ \mathrm{XOR}\ X.
You are also given an H-by-W matrix B consisting of non-negative integers and -1.
Determine if it is possible to make A_{i,j}=B_{i,j} for all pairs of integers (i,j) such that B_{i,j} \neq -1 by performing the operations.
What is \mathrm{XOR}?
The bitwise \mathrm{XOR} of non-negative integers A, B, denoted as A \oplus B, is defined as follows:
- The 2^k (k \geq 0) place of A \oplus B in binary notation is 1 if exactly one of the 2^k places of A and B in binary notation is 1, and 0 otherwise.
In general, the bitwise \mathrm{XOR} of k integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k), and it can be proven that this does not depend on the order of p_1, p_2, p_3, \dots p_k.
Constraints
- 1 \le H,W \le 500
- 0 \le A_{i,j} < 2^{30}
- -1 \le B_{i,j} < 2^{30}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
H W
A_{1,1} A_{1,2} \dots A_{1,W}
A_{2,1} A_{2,2} \dots A_{2,W}
\vdots
A_{H,1} A_{H,2} \dots A_{H,W}
B_{1,1} B_{1,2} \dots B_{1,W}
B_{2,1} B_{2,2} \dots B_{2,W}
\vdots
B_{H,1} B_{H,2} \dots B_{H,W}
Output
If it is possible to satisfy the condition, print Yes; otherwise, print No.
Sample Input 1
2 2 1 2 3 4 -1 3 1 7
Sample Output 1
Yes
Initially, A is as follows:
1 2 3 4
Performing the operation with X=1 on the second column, we get:
1 3 3 5
Performing the operation with X=2 on the second row, we get:
1 3 1 7
Thus, it is possible to satisfy the condition, so print Yes.
Sample Input 2
2 2 1 2 3 4 5 3 1 7
Sample Output 2
No
In this case, it is impossible to satisfy the condition no matter what, so print No.