Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2140
Ball

Time Limit: 2 Seconds      Memory Limit: 32768 KB      Special Judge

N persons are going to attend a ball, in order to make acquaintance with other people. But they don't like to make friends with too many persons. As the organizer, you have asked each of them about the number of friends he wants to make acquaintance with. Assume that the ith person needs EXACTLY a[i] friends, how could you arrange their meets to satisfy all the needs of them?

Perhaps you need a computer to help you. You are given the number of attendants and the exact number of friends each person wants to have, you must give out a configuration of acquaintances after your ball.


Input

The first line of each test case stands a integer N (1<=N<=100), which means the number of attendants to the ball. The second line contains N integers, which are the number of friends each person needs, the ith number a[i] means the ith person needs a[i] friends. The input ends up with N = 0, which should not be proceeded.


Output

If it is impossible to satisfy all the needs, print a single line "~><~".

Otherwise, print out the configuration matrix of acquaintances after your arrangement. The matrix contains n lines and each line contains n integers (1 or 0). A '1' in the ith row and the jth column means the ith person have made friends with the jth person (of course that the jth person also made friends with the ith person), A '0' means they are not friends. Use exactly one space between two adjacent integers. Don't print any other character in the matrix.

If there are multiple solutions for the needs, any one is acceptable.

Print a blank line between two cases.


Sample Input

2
2 2
2
1 1
0


Sample Output

~><~

0 1
1 0



Author: JIANG, Hao
Source: ZOJ Monthly, October 2004
Submit    Status