codeforces#P1475F. Unusual Matrix

    ID: 31772 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>2-satbrute forceconstructive algorithms*1900

Unusual Matrix

Description

You are given two binary square matrices aa and bb of size n×nn \times n. A matrix is called binary if each of its elements is equal to 00 or 11. You can do the following operations on the matrix aa arbitrary number of times (0 or more):

  • vertical xor. You choose the number jj (1jn1 \le j \le n) and for all ii (1in1 \le i \le n) do the following: ai,j:=ai,j1a_{i, j} := a_{i, j} \oplus 1 (\oplus — is the operation xor (exclusive or)).
  • horizontal xor. You choose the number ii (1in1 \le i \le n) and for all jj (1jn1 \le j \le n) do the following: ai,j:=ai,j1a_{i, j} := a_{i, j} \oplus 1.

Note that the elements of the aa matrix change after each operation.

For example, if n=3n=3 and the matrix aa is: (110001110) \begin{pmatrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix} Then the following sequence of operations shows an example of transformations:

  • vertical xor, j=1j=1. a=(010101010) a= \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}
  • horizontal xor, i=2i=2. a=(010010010) a= \begin{pmatrix} 0 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \end{pmatrix}
  • vertical xor, j=2j=2. a=(000000000) a= \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}

Check if there is a sequence of operations such that the matrix aa becomes equal to the matrix bb.

The first line contains one integer tt (1t10001 \leq t \leq 1000) — the number of test cases. Then tt test cases follow.

The first line of each test case contains one integer nn (1n10001 \leq n \leq 1000) — the size of the matrices.

The following nn lines contain strings of length nn, consisting of the characters '0' and '1' — the description of the matrix aa.

An empty line follows.

The following nn lines contain strings of length nn, consisting of the characters '0' and '1' — the description of the matrix bb.

It is guaranteed that the sum of nn over all test cases does not exceed 10001000.

For each test case, output on a separate line:

  • "YES", there is such a sequence of operations that the matrix aa becomes equal to the matrix bb;
  • "NO" otherwise.

You can output "YES" and "NO" in any case (for example, the strings yEs, yes, Yes and YES will be recognized as positive).

Input

The first line contains one integer tt (1t10001 \leq t \leq 1000) — the number of test cases. Then tt test cases follow.

The first line of each test case contains one integer nn (1n10001 \leq n \leq 1000) — the size of the matrices.

The following nn lines contain strings of length nn, consisting of the characters '0' and '1' — the description of the matrix aa.

An empty line follows.

The following nn lines contain strings of length nn, consisting of the characters '0' and '1' — the description of the matrix bb.

It is guaranteed that the sum of nn over all test cases does not exceed 10001000.

Output

For each test case, output on a separate line:

  • "YES", there is such a sequence of operations that the matrix aa becomes equal to the matrix bb;
  • "NO" otherwise.

You can output "YES" and "NO" in any case (for example, the strings yEs, yes, Yes and YES will be recognized as positive).

Samples

输入数据 1

3
3
110
001
110

000
000
000
3
101
010
101

010
101
010
2
01
11

10
10

输出数据 1

YES
YES
NO

Note

The first test case is explained in the statements.

In the second test case, the following sequence of operations is suitable:

  • horizontal xor, i=1i=1;
  • horizontal xor, i=2i=2;
  • horizontal xor, i=3i=3;

It can be proved that there is no sequence of operations in the third test case so that the matrix aa becomes equal to the matrix bb.