Description

Little D, who has never been to Shaoxing, was lucky to attend Winter Camp 2008. He was captivated by the beautiful scenery of this historic city and strongly requested to visit all scenic spots in and around Shaoxing.

The organizers divide Shaoxing into $N$ rows and $M$ columns, i.e., an $(N \times M)$ grid, as in the figure ($8 \times 8$):

Each scenic spot lies within a cell, and each cell contains at most one scenic spot. A cell without a scenic spot is considered a road.

For safety and convenience, based on road and security conditions, the organizers place different numbers of volunteers in some non-scenic cells; in scenic cells they hire tour guides (guides are not volunteers). When choosing a touring plan, we must ensure that between any two scenic spots there exists a path such that every cell on this path either has volunteers or is itself a scenic spot. The plan should meet contestants’ touring needs while minimizing the total number of volunteers.

For example, in the example above, each non-scenic cell is assigned a number indicating the minimum number of volunteers needed to control that cell:

The dark-shaded region shows one feasible volunteer arrangement, requiring a total of $20$ volunteers. As can be seen, two adjacent scenic spots are directly connected (via roads inside the scenic spots), e.g., 沈园 and 八字桥.

Now, please help the organizers find the best arrangement.

Input Format

The first line contains two integers, $N$ and $M$, describing the number of cells.

The next $N$ lines each contain $M$ nonnegative integers. If an integer is $0$, then the corresponding cell is a scenic spot; otherwise, it is the minimum number of volunteers required to control that cell. Adjacent integers are separated by one or more spaces; there may also be extra spaces at the beginning or end of a line.

Output Format

Output $N+1$ lines. The first line is a single integer, the total number of volunteers in your plan.

Then output $N$ lines, each containing $M$ characters, describing the status of each cell in your plan:

• _ (underscore) means no volunteers are placed in that cell.
• o (lowercase letter o) means volunteers are placed in that cell.
• x (lowercase letter x) means that cell is a scenic spot.

Note: Please strictly follow the output format. If any line is missing, or if any line contains an incorrect number of characters (and no extra spaces are allowed on any line), that test point may receive no score.

4 4
0 1 1 0
2 5 5 1
1 5 5 1
0 1 1 0

6
xoox
___o
___o
xoox

Hint

Constraints (across all $10$ groups of testdata) on $N$, $M$, and the number of scenic spots $K$ are as follows:

All integers in the input file are between $0$ and $2^{16}$, inclusive.

Translated by ChatGPT 5