Description

Nowadays, Sudoku is a very popular game.

The Sudoku game is to fill in digits 1-9 into blank grids such that none repeated digits in any row, column and block in a Sudoku solution.

and you, are asked to make an sudoku validator,
such that it can check whether the sudoku is a question or a solution,
(if there is any blank box, it's a question; else, it's a solution)
you also need to check that the question/solution is valid or not,
it is guarantee that if the input sudoku is a question, it will have exactly 1 solution,
that is, you only need to check every row, column, block such there are none repeat digits (1-9) in each of them.

ouo.

For example, the input of the above sudoku will be like:
_____________
|xxx|39x|x1x|
|5x1|xxx|x4x|
|9xx|7xx|5xx|
-------------
|6x2|53x|x7x|
|xxx|x7x|xx8|
|7xx|8xx|9x3|
-------------
|8x3|x1x|x9x|
|x9x|2x6|xx7|
|4xx|xx3|x61|
_____________

and the output should be:
question, valid

 

Hints :You can use scanf("%s", char array) and loop to get input

Input

Input contains 13 lines,
and there are exactly 13 characters in each line,
the input character will only be one of "123456789x",
'x' represent the blank box.

The format of input is like:
_____________
|ooo|ooo|ooo|
|ooo|ooo|ooo|
|ooo|ooo|ooo|
-------------
|ooo|ooo|ooo|
|ooo|ooo|ooo|
|ooo|ooo|ooo|
-------------
|ooo|ooo|ooo|
|ooo|ooo|ooo|
|ooo|ooo|ooo|
_____________
where 'o' is one of the character in "123456789x"

See Sample Input for more details.

 

Output

Output contain only 1 line.

If the input is a question of sudoku, output "question" (without quotes),
if the input is a solution of sudoku, then output "solution" (without quotes).

Then if the question/solution is valid, then output "valid" (without quotes), with ", " between the previous output,
if the question/solution is invalid, then output "invalid" (without quotes), with ", " (without quotes) between the previous output.

Remember to add a newline character after your output.

See Sample Output for more details.

Sample Input  Download

Sample Output  Download

Tags

Discuss

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