Description
Nonogram is a puzzle solving game.
The rule of solving Nonogram is simple:
you are given an empty 2D matrix, and your goal is to color some grid to fit given conditions.
There is a list of numbers beside each row and column,
which tells you the length of each consecutive colored grid of that row/column.
If the list on each row and column is fit, then the Nonogram is solved.
Your sister just tells you that she finished her summer homework,
and her homework is to solve Nonogram!
She asks you to verify wherther the Nonogram she colored is correct or not.
As an engineer, we should make everything automatically. So just build a Nonogram Validator!
ouo.
For the first Nonogram in the sample input, the input is as follows:
notice that the order of the input is blue arrows from up to down, then green arrows from left to right.
For the first row, there are exactly 2 consecutive colored grids both of length 1,
for the second row, there are exactly 3 consecutive colored grids all of length 1,
...
for the first column, there is 1 consecutive colored grid of length 2,
for the second column, there are exactly 2 consecutive colored grids both of length 1,
...
So the answer is "Yes".
For the second Nonogram in the sample input, the input is as follows:
the grid at the third row and the third column should be a 'o' so that the Nonogram can be correct,
so the output should be a "No".
Input
The first line contains an integer T,
representing that your sister has just finished T Nonograms.
Then for each Nonogram, the first line contains 2 integers N, M, representing the numbers of rows and columns of the Nonogram, respectively.
Then for each of the following N lines,
there is an integer Row_Li representing the length of the list beside the ith row,
followed by Row_Li integers, separated by spaces, representing the numbers of the list beside the ith row,
where the numbers in the list are given from left to right.
Then for each of the following M lines,
there is an integer Col_Li representing the length of the list beside the ith column,
followed by Col_Li integers, separeted by spaces, representing the numbers of the list beside the ith column,
where the numbers in the list are given from up to down.
Lastly, each of the following N lines has M characters,
representing the Nonogram your sister has finished, where
the character 'o' represents that the grid is colored, while
the character 'x' represents that the grid is not colored and empty.
It is guaranteed that:
1 <= T <= 10,
1 <= N, M <= 45
and the given lists of numbers are always valid.
Output
Output should contain T lines:
for each Nonogram,
output "Yes" (without quotes) if the Nonogram is solved correctly;
otherwise, output "No" (without quotes).