[ICPC2020 Shanghai R] Mine Sweeper II

一张扫雷地图 $X$ 可以被视为一个 $n \times m$ 的网格，每个格子要么是地雷格，要么不是地雷格。地雷格上没有数字，而每个非地雷格上都有一个数字，代表周围相邻 $8$ 个格子中地雷格的数目。下图是一个 $16\times 30$ 的扫雷地图，地雷格由小红旗表示，一个空白的格子代表一个数字为 $0$ 的非地雷格。  给出两张尺寸均为 $n\times m$ 的扫雷地图 $A,B$。每次修改可以将一个地雷格改为非地雷格，或者将一个非地雷格改为地雷格。你可以修改最多 $\lfloor \dfrac{nm}{2} \rfloor$ 个地图 $B$ 中的格子，请给出一种方案，使得 $A,B$ 中非地雷格上数字之和相同。若无解，输出 $-1$。

A mine-sweeper map $X$ can be expressed as an $n\times m$ grid. Each cell of the grid is either a mine cell or a non-mine cell. A mine cell has no number on it. Each non-mine cell has a number representing the number of mine cells around it. (A cell is around another cell if they share at least one common point. Thus, every cell that is not on the boundary has $8$ cells around it.) The following is a $16\times 30$ mine-sweeper map where a flagged cell denotes a mine cell and a blank cell denotes a non-mine cell with number 0.  Given two mine-sweeper maps $A, B$ of size $n\times m$, you should modify at most $\left\lfloor\frac{nm}{2}\right\rfloor$ (i.e. the largest nonnegative integer that is less than or equal to $\frac{nm}{2}$) cells in $B$ (from a non-mine cell to a mine cell or vice versa) such that the sum of numbers in the non-mine cells in $A$ and the sum of numbers in the non-mine cells in $B$ are the same. (If a map has no non-mine cell, the sum is considered as $0$.) If multiple solutions exist, print any of them. If no solution exists, print ``-1`` in one line.

The first line contains two integers $n, m\,(1\le n,m \le 1000)$, denoting the size of given mine-sweeper maps. The $i$-th line of the following $n$ lines contains a length-$m$ string consisting of ``.`` and ``X`` denoting the $i$-th row of the mine-sweeper map $A$. A ``.`` denotes for a non-mine cell and an ``X`` denotes for a mine cell. The $i$-th line of the following $n$ lines contains a length-$m$ string consisting of ``.`` and ``X`` denoting the $i$-th row of the mine-sweeper map $B$. A ``.`` denotes for a non-mine cell and an ``X`` denotes for a mine cell.

If no solution exists, print ``-1`` in one line. Otherwise, print $n$ lines denoting the modified mine-sweeper map $B$. The $i$-th line should contain a length-$m$ string consisting of ``.`` and ``X`` denoting the $i$-th row of the modified map $B$. A ``.`` denotes for a non-mine cell and an ``X`` denotes for a mine cell. Please notice that you need not print the numbers on non-mine cells since these numbers can be determined by the output mine-sweeper map.

2 4
X..X
X.X.
X.X.
.X..

X.XX
.X..

We modify one cell in $B$. Then the sums of the numbers on non-mine cells in $A$ and $B$ both equal $10$.