Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Garden

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputVasya 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.

Input

The first input line contains three integers *n*, *m* and *k* (1 ≤ *n*, *m* ≤ 100, *n*·*m* ≤ 200, 1 ≤ *k* ≤ *min*(*n*·*m*, 7)) — the garden's sizes and the number of the important squares. Each of the next *n* lines contains *m* numbers *a*_{i}_{j} (1 ≤ *a*_{i}_{j} ≤ 1000) — the numbers of flowers in the squares. Next *k* lines contain coordinates of important squares written as "*x* *y*" (without quotes) (1 ≤ *x* ≤ *n*, 1 ≤ *y* ≤ *m*). The numbers written on one line are separated by spaces. It is guaranteed that all *k* important squares have different coordinates.

Output

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.

Examples

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.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/24/2020 06:07:19 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|