P16114 [USTCPC 2026] Blank or Mine

Kruskal-chan recently came up with a new idea again. “What if you can only see half of the information? Can you still deduce the other half?” She muttered to herself while drawing small squares on scratch paper. A junior club member leaned over to take a look. “Huh? Isn’t this Minesweeper? Why is there only the top row?” “This is called ‘half-information Minesweeper’!” Kruskal-chan proudly waved her pen. “Real reasoning is not about guessing, but about inevitability!” She pushed the board that shows only the first row of information in front of you and gently tapped the table. “Give it a try. Can you determine which cells in the second row must be mines, which must be empty, and which cannot be determined at all?”

You are playing a special Minesweeper game. The game is played on a grid with $2$ rows and $n$ columns ($1 \le n \le 3 \times 10^5$). Each cell is either a mine or empty. You already know whether each cell in the first row is a mine or empty. If a cell is empty, you also see a number indicating the total number of mines among the cells adjacent to it in the eight directions. Now, based on this information, you need to infer for each cell in the second row whether it must be a mine, must be empty, or cannot be determined. The testdata guarantees that there is at least one layout of the second row that satisfies all conditions of the first row.

**This problem contains multiple test cases.** The first line contains a positive integer $T$, the number of test cases. Each of the following lines describes one test case and contains a string of length $n$. The $i$-th character represents the state of the $i$-th cell in the first row: - If the cell is a mine, it is represented by the character `*`. - If the cell is empty, it is represented by a digit character `0` to `8`, indicating the total number of mines among the cells adjacent to it in the eight directions.

For each test case, output a string of length $n$. The $i$-th character represents the inferred result for the $i$-th cell in the second row: - If it must be a mine, output `*`. - If it must be empty, output `.`. - If it cannot be determined, output `?`.

The sum of $n$ over all testdata is $\le 3\times 10^5$. The testdata guarantees that there is at least one layout of the second row that satisfies all conditions of the first row. Translated by ChatGPT 5