Little D, who has never been to Shaoxing, had the good fortune to attend Winter Camp 2008. Captivated by the beautiful scenery of this historic city, he strongly requested to visit all the tourist attractions in and around Shaoxing.
The organizers have divided Shaoxing into an $N \times M$ grid of blocks.
Attractions are contained within blocks, and each block contains at most one attraction. Blocks without attractions are considered roads.
To ensure safety and convenience, the organizers have arranged different numbers of volunteers in some non-attraction blocks based on road conditions and security, while hiring tour guides for the attractions (tour guides are not volunteers). When choosing a tour plan, it must be guaranteed that there exists a path between any two attractions such that every block passed along this path either has volunteers or is an attraction. The goal is to satisfy the needs of the participants while minimizing the total number of volunteers.
Input
The input contains two integers $N$ and $M$ on the first line, describing the dimensions of the grid.
The following $N$ lines each contain $M$ non-negative integers. If an integer is $0$, the block is an attraction; otherwise, it represents the minimum number of volunteers required to control that block. Adjacent integers are separated by (one or more) spaces, and there may be extra spaces at the beginning or end of lines.
Output
The output consists of $N + 1$ lines. The first line contains an integer representing the total number of volunteers in your proposed plan.
The following $N$ lines each contain $M$ characters, describing the status of the corresponding blocks in the plan:
_ (underscore) indicates that no volunteers are arranged in this block;
o (lowercase English letter o) indicates that volunteers are arranged in this block;
* x (lowercase English letter x) indicates that this block is an attraction.
Note: Please pay attention to the output format requirements. If a line is missing or the number of characters in a line does not match the requirements (no extra spaces are allowed in any line), it may result in no points for that test case.
Examples
Input 1
4 4 0 1 1 0 2 5 5 1 1 5 5 1 0 1 1 0
Output 1
6 xoox ___o ___o xoox
Note
The shaded blocks in the figure below have volunteers arranged:
Subtasks
There are 10 test cases in total, each worth 10% of the total score.
For each test case: If only the correct total number of volunteers is output, 50% of the points for that test case are awarded. If both the correct total number of volunteers and the correct plan are output, full points for that test case are awarded. * Otherwise, 0 points are awarded.
Constraints
The ranges for $N$, $M$, and the number of attractions $K$ for all 10 test cases are as follows:
| Test Case | $N$ | $M$ | $K$ |
|---|---|---|---|
| 1 | $\le 2$ | $\le 2$ | $\le 2$ |
| 2 | $\le 4$ | $\le 5$ | $\le 4$ |
| 3 | $\le 2$ | $\le 10$ | $\le 3$ |
| 4 | $\le 6$ | $\le 7$ | $\le 5$ |
| 5 | $\le 8$ | $\le 9$ | $\le 7$ |
| 6 | $\le 10$ | $\le 9$ | $\le 10$ |
| 7 | $\le 9$ | $\le 10$ | $\le 10$ |
| 8 | $\le 10$ | $\le 10$ | $\le 3$ |
| 9 | $\le 10$ | $\le 10$ | $\le 10$ |
| 10 | $\le 10$ | $\le 10$ | $\le 10$ |
All integers in the input file are $\ge 0$ and $\le 2^{16}$.