닥터 후의 연회

닥터 후가 연회를 열고 손님을 여러 명 초대한다. 손님 $i$는 자기를 뺀 다른 손님 정확히 $a_i$명과 대화하면 만족한다. 손님은 자기 자신과 대화하지 못하고, 두 손님은 서로 대화하거나 대화하지 않거나 둘 중 하나다. 모든 손님이 만족하도록 대화 짝을 정하고, 그런 배치가 없으면 없다고 답하라.

입력은 데이터 집합 여러 개로 이루어지고, 데이터 집합 하나가 한 줄을 차지한다. 한 줄에는 정수 $a_1, a_2, \dots, a_n$을 공백 하나로 구분해 적는다. $a_i$는 손님 $i$가 원하는 대화 상대의 수다. 손님 번호는 줄에 적힌 순서대로 $1$번부터 $n$번까지다. $1 \le n \le 10000$이고 $1 \le a_i \le 1000$이다. 입력은 파일의 끝에서 끝난다.

데이터 집합마다 결과를 한 덩어리씩 출력한다. 모든 손님을 만족시킬 수 있으면 $n \times n$ 행렬 $m$을 출력한다. 손님 $i$와 손님 $j$가 대화하면 $m[i][j] = m[j][i] = 1$이고, 그렇지 않으면 $0$이다. 각 행을 한 줄에 출력하고, 같은 행의 값은 공백 하나로 구분한다. 모든 손님을 만족시킬 수 없으면 fail을 출력한다. 덩어리를 하나 출력한 뒤에는 빈 줄을 한 줄 출력한다.

같은 희망 목록을 만족시키는 행렬이 여러 개일 수 있으므로, 다음 방법이 만드는 행렬만 정답으로 인정한다.

손님마다 남은 횟수 $r_i$를 $a_i$로 두고 모든 손님을 후보에 넣는다. 후보 중에 $r_i > 0$인 손님이 있는 동안 다음을 반복한다. 후보 중에서 $r_v$가 가장 큰 손님 $v$를 고르되, 값이 같으면 번호가 작은 쪽을 고른다. 나머지 후보를 $r$이 큰 순서로, 값이 같으면 번호가 작은 순서로 늘어놓고 앞에서 $r_v$명을 $v$의 대화 상대로 정한다. 새로 짝이 된 손님의 $r$을 $1$씩 줄이고, $r_v$를 $0$으로 바꾼 다음 $v$를 후보에서 뺀다. 후보에 남은 손님의 $r$이 모두 $0$이 되면 행렬이 완성된다. 가능한 배치가 하나라도 있으면 이 방법은 반드시 성공한다.