Dr Who's Banquet

Dr Who is holding a banquet and invites several guests. Guest $i$ is happy when he chats with exactly $a_i$ of the other guests. A guest never chats with himself, and any two guests either chat with each other or they do not. Pair the guests so that every guest is happy, or report that no such arrangement exists.

The input holds several data sets, one data set per line. A line holds the integers $a_1, a_2, \dots, a_n$ separated by single spaces, where $a_i$ is the number of chat partners guest $i$ wants. The guests on a line are numbered $1$ to $n$ in the order they appear. $1 \le n \le 10000$ and $1 \le a_i \le 1000$. The input ends at the end of the file.

Print one block for each data set. If every guest can be made happy, print the $n \times n$ matrix $m$, where $m[i][j] = m[j][i] = 1$ when guests $i$ and $j$ chat and $0$ otherwise. Print each row on its own line and separate the values of a row by single spaces. If no arrangement makes every guest happy, print fail. Print one empty line after each block.

Several matrices can satisfy the same wish list, so only the matrix produced by the construction below counts as correct.

Give each guest a counter $r_i$ set to $a_i$ and put every guest in the pool. While some guest in the pool has $r_i > 0$, repeat this. Take the guest $v$ of the pool with the largest $r_v$, and among ties the one with the smaller number. Order the remaining guests of the pool by $r$ from large to small, breaking ties by the smaller number, and pair $v$ with the first $r_v$ of them. Subtract $1$ from the counter of each new partner, set $r_v$ to $0$, and remove $v$ from the pool. The matrix is complete once every guest left in the pool has $r_i = 0$. This construction pairs everybody whenever a valid arrangement exists.