Problem C
Constellation Creation

Illustration of Sample 2

As you journey further into space, the relative positions of the stars have shifted so much that you can no longer recognize the constellations that you’ve learned about growing up. This makes for a great opportunity – now you can come up with your own constellations!

You’ve taken a snapshot of the night sky and aligned it into a rectangular grid, and want to get to work creating some constellations. Since you’re working on such a nice grid, you’ll just use vertical and horizontal lines to connect stars together. Sometimes one constellation’s vertical line might cross another constellation’s horizontal line, but this doesn’t by itself make them the same constellation. Also, none of the stars are immediately adjacent horizontally or vertically on the grid.

After playing around like this for a while with different segments of the night sky, you start to get bored but your crew-mates want to see more constellations! Can you write a program to automate this task?

Input

The first line of input consists of three space-separated integers, $1 \leq r \leq 500$, $1 \leq c \leq 500$, and $1 \leq n \leq 20\, 000$, where $r$ is the number of rows, $c$ is the number of columns, and $n$ is the desired number of constellations. The next $r$ lines consist of $c$ characters each, where every character is either a “.”, representing empty space, or a “*”, representing a star.

Output

The output should consist of an $r \times c$ grid, with stars (“*”) placed in the same locations as the input, and with each “.” replaced with either a “|”, “-”, or “+” character, which connect stars by straight horizontal and/or vertical lines, or a space character “ ” for empty space. The output should form exactly $n$ constellations (groupings of one or more stars connected by straight lines). At least one valid solution will always exist.

3 3 2
*.*
.*.
*.*

*-*
|*|
*-*

6 6 3
...*..
..*...
.*..*.
*....*
..*.*.
...*..

   *  
  *|  
 *++* 
*-+++*
  *+* 
   *  

11 15 8
*.*.*.*.*.*.*.*
...............
........*.*....
...............
*.*.*.*.*...*.*
...............
*.*.*.*.*.*.*.*
...............
*.*.....*.*.*.*
...............
*.*.*.*.*.*.*.*

*-* *-* *-* *-*
|   |   | | |  
|   |   *-* |  
|   |   |   |  
*-* *-* *   *-*
               
*-* *-* *-* *-*
  | | |   |   |
*-* | | *-* *-*
|   | | |     |
*-* *-* *-* *-*