Description

Hey, can I say somthing amazing?  Bacteria touched the air for some reason and begin to widespread in the classroom. The bacteria turned out to be Firmicutes (some kind of bacteria). The classroom can be viewed as a 2D grid map with size R x C. Walls in classroom are denoted as #, clean areas not polluted by Firmicutes are denoted as C, and places where there exist Firmicutes are denoted as F. The classroom is guaranteed to be surrounded by walls. For example a classroom of size 7 x 8 with some area polluted may look like this :

 ########
 #CCC#CC#
 #CFC####
 #CCCCCC#
 #CC#####
 #FCCCCC#
 ########

Firmicutes reproduces rapidly. Initially, some areas in the classroom are polluted by Firmicutes. For every second, if an area is polluted by Firmicutes, the Firmicutes on this area will reproduce themselves and spread to neighboring clean areas. Here, we define neighboring areas of area (r, c) are (r+1, c), (r-1, c), (r, c+1), and (r, c-1). Note that Firmicutes cannot spread onto walls, which means that even if a wall is neighbor to some polluted area, the wall will not be polluted. The following example is a classroom from t = 0 ~ 2 seconds.

Initially, t=0. Some areas are polluted.

 ########
 #CCC#CC#
 #CFC####
 #CCCCCC#
 #CC#####
 #FCCCCC#
 ########

When t=1,

 ########
 #CFC#CC#
 #FFF####
 #CFCCCC#
 #FC#####
 #FFCCCC#
 ########

When t=2,

 ########
 #FFF#CC#
 #FFF####
 #FFFCCC#
 #FF#####
 #FFFCCC#
 ########

Given how the class looks like initially (when t=0) and a time T, please output how the classroom looks like when t=T.

Input

The first line consist of three integers R, C, T, meaning the size of the classroom and a time.

For the following R lines, each line has C characters, being how the classroom looks like initially. Each character will be one of {#, C, F} and the classroom is surrounded by walls (#).

Technical Restrictions

• 3 ≦ R, C ≦ 100

• 0 ≦ T ≦ 100

• The first test case is same as sample IO. It is suggest to use it to check whether your output format is valid.

Output

Please output how the classroom looks like in the T-th second (when t=T).

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Nonogram is a puzzle solving game.

The rule of solving Nonogram is simple,
you are given a empty 2D grid, and your goal is to color some grid to fit given conditions.

There are a list of numbers beside each row and column,
the list of numbers tells you the length of each consecutive colored grid of that row/column.

For example, if see '1 2 3' in row 1, then there will be 1 colored grid, followed by one or more empty grid, then exactly 2 consecutive colored grids, followed by one or more empty grid, then exactly 3 consecutive colored grids, from left to right.

Also, if see '2 2' in colum 2, then there will be exactly 2 consecutive colored grids, followed by one or more empty grid, then exactly 2 consecutive colored grids, from up to down.

If all lists on each row and column are 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 asked 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 follow:
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 colored grids that is length 1,
for the second row, there are exactly 3 colored grids that is length 1,
...
for the first column, there are exactly 2 colored grids and they are consecutive, so the length is 2,
for the second column, there are exactly 2 colored grids that is length 1,
...

So the answer is "Yes".

---

For the second Nonogram in the sample input, the input is as follow:

the grid at the third row and the third column should be a 'o' so the Nonogram is correct,
so the output should be a "No".

---

Testcases have changed and rejudge since some code are not allow to pass but pass.
Sorry for the inconvience.
Rejudge finished @2020/10/29 22:50.

Input

The first line contains of an integer T,
represent that your sister has just finished T Nonograms.

Then for each Nonogram,

The first line contains 2 integers N, M,
represent the rows and the colomns of the Nonogram respectively.

Then the following N lines,
there are an integer Row_L_i represent the length of the list beside the i_th row,
then follows by Row_L_i integers, separated by spaces, represent numbers of the list beside the _ith row,
the numbers in the list is given from left to right.

Then the following M lines,
there are an integer Col_L_i represent the length of the list beside the ith column,
then follows by Col_L_i integers, separeted by spaces, represent numbers of the list beside the i_th column,
the numbers in the list is given from up to down.

The the following N lines, each line has M characters,
represent the Nonogram your sister has finished,
the character 'o' represent that the grid is colored,
the character 'x' represent that the grid is not colored and empty.

It is a guarantee that:

1 <= T <= 10,
1 <= N, M <= 45

the given list of numbers is always valid.

Output

Output should contains T lines,

for each Nonogram,

output "Yes" (without quotes) if the Nonogram is solved correctly,

otherwise, output "No" (without quotes).

Sample Input  Download

Sample Output  Download

Tags

Discuss