Problem A - Extra Terrestrial Bacterium

Since humans mastered interstellar travel, a lot of new worlds have been visited. One of these worlds, imaginatively called BXP-167, has revealed a curious bacteria specie like no other seen on earth. These bacterium are in fact 4 different types of bacterium that scientists like to call cardinal, asterisk, null and cross because of their unusual shapes (see Figure 1).

Fig. 1 - The first shot taken of asterisk bacterium.

What's funny about these bacterium is that, besides always being organized in a grid like form, they seem to be able to change from one type to another following a set of rules:

Note: For a bacteria to be near another it has to be directly above it, below it or at its left or right.

These rules are automatically triggered every second. These are the rules that scientist found so far but they suspect more can exist.

The Problem

Your task is to write a program that will aid scientists to find if more rules exist. Your program should be capable of, knowing the initial bacterium configuration, anticipating its final configuration after a number of seconds.

Input

The first line of the input will contain three integers W, H and S (1≤W,H≤100, 0≤S≤100) representing the number of columns and lines of the bacteria population and also the number of seconds to be elapsed before the final configuration is found.

The next H lines will contain W characters, each one representing a single bacteria: # for cardinals, * for asterisks, 0 (zero) for nulls and X (capital x) for crosses.

Output

The output will have H lines each one of them containing W characters. These lines will represent the final configuration after S seconds.

Sample Input 1

10 5 1
####**####
##000000##
##00XX00##
##000000##
####**####

Sample Output 1

####00####
##XXXXXX##
##XXXXXX##
##XXXXXX##
####00####
 

Sample Input 2

10 5 10
####**####
##000000##
##00XX00##
##000000##
####**####

Sample Output 2

X#0X**X0#X
#*#0000#*#
*X*XXXX*X*
#*#0000#*#
X#0X**X0#X

TIUP & CPUP 2007
Universidade do Porto
(30 de Maio de 2007)