Vasja is a very beautiful country garden, which is a rectangular box the size of n × m, divided by n · m square cells. One day, Bob remembered that he needed to pave the path between k cells with important buildings - for that he can fill in some of the concrete cells of the garden.

About every cell of the garden known number of aij, which means the number of flowers growing in the cell with coordinates (i, j). When pouring concrete all the flowers that grow in the cell dies.

Bob wants to pour concrete, some cells so that the following conditions:

    * K all the important cells have to be filled with concrete
    * Each of the major cell to any other cells there was an important way of concrete poured, the cells under the condition that neighboring cells are considered as having a common side
    * Total number of dead plants should be minimal

Since Wasi quite a large garden, it asks you to help him.

Input

The first line of input data are given three integers n, m and k (1 ≤ n, m ≤ 100, n · m ≤ 200, 1 ≤ k ≤ min (n · m, 7) - the size of the garden and the number of important cells. Next the n rows of m numbers are given in each of aij (1 ≤ aij ≤ 1000) - the number of colors in the cells. Then the k rows are the coordinates of the critical cells in the form «xy» (without quotation marks) (1 ≤ x ≤ n, 1 ≤ y ≤ m). numbers are located on the same line, separated by spaces. It is guaranteed that all k important cells have different coordinates.

Output

In the first line of the output single integer - the minimum number of deaths in the construction of plants. Then output n lines of m characters each - the plan of the garden, where the symbol «X» (a capital letter X) is flooded with concrete cell, and the symbol "." (Point) - is not flooded. If several solutions, any output.

Input

3 3 2
1 2 3
1 2 3
1 2 3
1 2
3 3
Output
9
.X.
.X.
.XX