codeforces#P1475F. Unusual Matrix
Unusual Matrix
Description
You are given two binary square matrices and of size . A matrix is called binary if each of its elements is equal to or . You can do the following operations on the matrix arbitrary number of times (0 or more):
- vertical xor. You choose the number () and for all () do the following: ( — is the operation xor (exclusive or)).
- horizontal xor. You choose the number () and for all () do the following: .
Note that the elements of the matrix change after each operation.
For example, if and the matrix is: Then the following sequence of operations shows an example of transformations:
- vertical xor, .
- horizontal xor, .
- vertical xor, .
Check if there is a sequence of operations such that the matrix becomes equal to the matrix .
The first line contains one integer () — the number of test cases. Then test cases follow.
The first line of each test case contains one integer () — the size of the matrices.
The following lines contain strings of length , consisting of the characters '0' and '1' — the description of the matrix .
An empty line follows.
The following lines contain strings of length , consisting of the characters '0' and '1' — the description of the matrix .
It is guaranteed that the sum of over all test cases does not exceed .
For each test case, output on a separate line:
- "YES", there is such a sequence of operations that the matrix becomes equal to the matrix ;
- "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 () — the number of test cases. Then test cases follow.
The first line of each test case contains one integer () — the size of the matrices.
The following lines contain strings of length , consisting of the characters '0' and '1' — the description of the matrix .
An empty line follows.
The following lines contain strings of length , consisting of the characters '0' and '1' — the description of the matrix .
It is guaranteed that the sum of over all test cases does not exceed .
Output
For each test case, output on a separate line:
- "YES", there is such a sequence of operations that the matrix becomes equal to the matrix ;
- "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
Note
The first test case is explained in the statements.
In the second test case, the following sequence of operations is suitable:
- horizontal xor, ;
- horizontal xor, ;
- horizontal xor, ;
It can be proved that there is no sequence of operations in the third test case so that the matrix becomes equal to the matrix .