# Problem C

Constellation Creation

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.

Sample Input 1 | Sample Output 1 |
---|---|

3 3 2 *.* .*. *.* |
*-* |*| *-* |

Sample Input 2 | Sample Output 2 |
---|---|

6 6 3 ...*.. ..*... .*..*. *....* ..*.*. ...*.. |
* *| *++* *-+++* *+* * |

Sample Input 3 | Sample Output 3 |
---|---|

11 15 8 *.*.*.*.*.*.*.* ............... ........*.*.... ............... *.*.*.*.*...*.* ............... *.*.*.*.*.*.*.* ............... *.*.....*.*.*.* ............... *.*.*.*.*.*.*.* |
*-* *-* *-* *-* | | | | | | | *-* | | | | | *-* *-* * *-* *-* *-* *-* *-* | | | | | *-* | | *-* *-* | | | | | *-* *-* *-* *-* |