CF152E Garden

Vasya has a very beautiful country garden that can be represented as an $ n×m $ rectangular field divided into $ n·m $ squares. One beautiful day Vasya remembered that he needs to pave roads between $ k $ important squares that contain buildings. To pave a road, he can cover some squares of his garden with concrete. For each garden square we know number $ a_{i}_{j} $ that represents the number of flowers that grow in the square with coordinates $ (i,j) $ . When a square is covered with concrete, all flowers that grow in the square die. Vasya wants to cover some squares with concrete so that the following conditions were fulfilled: - all $ k $ important squares should necessarily be covered with concrete - from each important square there should be a way to any other important square. The way should go be paved with concrete-covered squares considering that neighboring squares are squares that have a common side - the total number of dead plants should be minimum As Vasya has a rather large garden, he asks you to help him.

The first input line contains three integers $ n $ , $ m $ and $ k $ ( $ 1

In the first line print the single integer — the minimum number of plants that die during the road construction. Then print $ n $ lines each containing $ m $ characters — the garden's plan. In this plan use character "X" (uppercase Latin letter X) to represent a concrete-covered square and use character "." (dot) for a square that isn't covered with concrete. If there are multiple solutions, print any of them.