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).