C. Nanami and the House Protecting Problem
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Nanami is playing Minecraft, where the map can be thought of as a $$$n\times m$$$ grid. Monsters are constantly appearing from outside this grid, so Nanami needs to build a wall of obstacles to protect her house. When monsters move, they can move to any empty grid that has an adjacent edge to the current grid.

The grid contains the following three types: '.' for empty grids, '#' for grids with obstacles, and 'H' for Nanami's house; Nanami can place a new obstacle at any grid point that does not have an obstacle or a house.

At the same time, Minecraft has a setting where the cost of placing an obstacle on different grid points is different. In other words, there is a two-dimensional matrix $$$a$$$, and the price of placing an obstacle at grid point $$$(i,j)$$$ is $$$a_{i,j}$$$.

Nanami wants to ask you what is the smallest price she would have to pay if she wanted to protect all her houses.

Input

In the first line, an integer $$$t(1\le t \le 333)$$$, representing the number of data sets.

For each group of data:

The first line, two integers $$$n,m(3\le n,m \le 1000)$$$, represents the size of the Minecraft map.

The next consecutive $$$n$$$ rows, each consisting of '.' , '#' or 'H', representing the map of Minecraft.

The next consecutive $$$n$$$ lines, each with $$$m$$$ integers $$$a_{i,j},\dots,a_{i,m}(0\le a_{i,j}\le 10^5)$$$, represent the price of placing an obstacle $$$a_{i,j}$$$ at grid point $$$(i,j)$$$.

It is guaranteed that a house (i.e. 'H') will not appear on the map boundary and that there is at least one 'H' on the map.

It is guaranteed that all corresponding positions of matrix $$$a$$$ that do not have '.' are $$$0$$$, and that the prices of the locations corresponding to '.' are greater than $$$0$$$. The price of the corresponding location is greater than $$$0$$$.

Ensure that the sum of $$$n\times m$$$ within the same test point does not exceed $$$3000$$$.

Output

For each set of data, first output a line of integers $$$c$$$, representing the minimum price Nanami will pay. Next, output $$$n$$$ lines of string of length $$$m$$$, with each character being '.', '#' or 'H', representing Nanami's solution for placing the obstacle. , '#' or 'H', representing Nanami's solution for placing obstacles. Note that Nanami can only place obstacles in spaces, and cannot move existing obstacles or her house.

Any obstacle solution that meets the requirements of the question will be considered correct.

Example
Input
5
3 3
.#.
#H.
.#.
1 0 1
0 0 2
1 0 1
3 3
###
#H#
###
0 0 0
0 0 0
0 0 0
5 6
#...#.
...H..
##..##
...#.#
###...
0 1 2 2 0 9
1 1 9 0 3 1
0 0 1 1 0 0
9 9 9 0 9 0
0 0 0 8 8 8
4 4
.##.
.H.#
..H.
.#..
23 0 0 75
13 0 42 0
1 25 0 1
17 0 13 96
6 5
.....
.H...
.....
.....
.H...
...#.
2 1 2 1 1
2 0 3 2 1
2 2 1 2 1
3 2 3 1 1
1 0 2 2 2
2 2 1 0 1
Output
2
.#.
#H#
.#.
0
###
#H#
###
7
#.###.
.#.H.#
###.##
...#.#
###...
28
.##.
#H.#
#.H#
.##.
15
.#...
#H#..
.#...
.#...
#H#..
.#.#.