P15657 [ICPC 2025 Jakarta R] Binary Grid

You are given an array $A$ containing $N$ non-negative integers. You have to construct a binary grid of size $N \times M$ such that: - for any cell with value $1$, any of its adjacent cells, i.e. cells that share one of its four sides, must $\textbf{not}$ have the value $1$. - the number of cells with value $1$ in row $i$ is exactly $A_i$. Find any such binary grid or tell that it's impossible to construct.

The first line contains two integers $N$ and $M$ ($1 \leq N, M \leq 1000$). The next line contains $N$ integers containing $A_i$ ($0 \leq A_i \leq M$).

Output $N$ lines, each containing $M$ characters of either $\texttt{0}$ or $\texttt{1}$ representing the binary grid you constructed. If multiple construction exists, you may output any of them. If such a grid does not exist, output $-1$.