Vasya has a very beautiful country garden, which is a rectangular field n × m in size, divided into n · m square cells. One day, Vasya remembered that he needed to pave pathd between k cells with important buildings - for that he can fill some of the cells in his garden with concrete.

For each cell of the garden, the number a_ij is known, 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 die.

Vasya wants to fill some cells with concrete so that the conditions:

• all k important cells must be filled with concrete.
• from each important cell to any other important cell, there was a path through the cells filled with concrete, provided that cells with a common side are considered neighboring.
• the total number of dead plants should be minimal.

Since Vasya has a rather large garden, he asks you to help him.

Input

The first line of the input contains 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. The following n lines with m numbers each contain numbers a_ij (1 ≤ a_ij ≤ 1000) — the number of flowers in the cells. Next k lines contain the coordinates of important cells in the format "x y" (without quotes) (1 ≤ x ≤ n, 1 ≤ y ≤ m). Numbers on the same line are separated by spaces. It is guaranteed that all k important cells have different coordinates.

Output

In the first line print a single integer — the minimum number of plants killed during the construction. Then output n lines of m characters each — the plan of the garden, where the character "X" (capital Latin letter X) denotes a cell filled with concrete, and the character "." (dot) - not filled. If there are several solutions, print any

Sample

Input
3 3 2
1 2 3
1 2 3
1 2 3
1 2
3 3

Output
9
.X.
.X.
.XX

Input
4 5 4
1 4 5 1 2
2 2 2 2 7
2 4 1 4 5
3 2 1 7 1
1 1
1 5
4 1
4 4

Output
26
X..XX
XXXX.
X.X..
X.XX.