Uncool Grid

You are given an $N$ by $M$ grid $A$. Each cell contains either $0$ or $1$.

A shortest path from $(1,1)$ to $(N,M)$ moves one cell to the right or one cell downward at every step. Reading the characters on the visited cells from the start to the end produces a binary string of length $N+M-1$.

The grid is called cool if two distinct shortest paths can produce the same binary string. Otherwise, equivalently, if every shortest path produces a different binary string, the grid is not cool.

Choose exactly $K$ distinct cells and flip each chosen cell once. A $0$ becomes $1$, and a $1$ becomes $0$.

Construct one grid that is not cool after exactly $K$ flips. If this is impossible, report that it is impossible.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N\ M\ K$ $A_1$ $A_2$ $\vdots$ $A_N$

$A_i$ is a binary string of length $M$, and its $j$-th character is the value of cell $(i,j)$.

For each test case, print the answer.

If no valid grid can be constructed, print -1 on one line.

Otherwise, print $N$ binary strings of length $M$. The printed grid must differ from the original grid in exactly $K$ cells and must not be cool.

If there are multiple solutions, print any of them.

• $1 \leq T \leq 200\,000$.
• $1 \leq N,M \leq 3\,000$.
• $0 \leq K \leq NM$.
• $A_{i,j} \in \{0,1\}$ ($1 \leq i \leq N$, $1 \leq j \leq M$).
• The sum of $NM$ over all test cases does not exceed $9\,000\,000$.