Equalizing Minesweeper Sums

You are given two minesweeper maps A and B, each of size \(n \times m\). A minesweeper map \(X\) is an \(n \times m\) grid where each cell is either a mine cell or a non-mine cell. In the input, a mine cell is denoted by the character * and a non-mine cell is denoted by ..

In any minesweeper map \(X\), every non-mine cell contains a number equal to the number of mine cells around it. Two cells are considered adjacent if they share at least one common point (thus, a cell typically has up to 8 neighbors, except at borders or corners). The sum of numbers in \(X\) is defined as the sum of the numbers in all non-mine cells (if there is no non-mine cell, the sum is considered to be \(0\)).

You are allowed to modify map B by flipping the state (from mine to non-mine or vice versa) of at most \(\left\lfloor \frac{nm}{2} \right\rfloor\) cells. Your task is to perform such modifications on B so that the sum of the numbers in the non-mine cells in B becomes equal to that of A. If multiple solutions exist, you may output any one of them. If no solution exists, output a single line with -1.

Note: When the final configuration of a map is considered, the number in each non-mine cell is computed based on the final distribution of mines in that map.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n, m \leq 1000)\) representing the number of rows and columns of the maps.

The next \(n\) lines describe map A, each line containing a string of length \(m\) consisting of the characters * (mine) and . (non-mine).

The following \(n\) lines describe map B in the same format.

outputFormat

If a solution exists, output the final configuration of map B after modifications, consisting of \(n\) lines, each line a string of length \(m\) composed of * and .. If more than one solution exists, output any of them. If no solution exists, output a single line with -1.

sample

3 3
...
.*.
...
...
.*.
...

...
.*.
...