| The Absent Minded Professor |
Professor Xian is working on Balance for quite a few days. The newly invented balance by him can accurately specify the difference between two weights. As a result it is possible to weight anything using only one standard weight.
Professor wants to test the new Balance. So he collected few metallic sphere of different weight. Now he keeps one sphere on one side of the balance and then one by one from other spheres on another side to take the difference of weight between two spheres. When the difference becomes negative he ignores that otherwise he writes the difference on a paper. He performs this process with each sphere individually. Now using the data professor wants to test the correctness of the new Balance. His idea is simple. If a,b,c (a < b < c) are three weights then (c-a)-(b-a) = c-b. But Oh!! professor Xian has forgot the proper order of his weighting scheme. He is seeking your help.
Your task is to find a weight for each sphere such that the all possible weight difference match with professor's reading.
The input will start with an integer, N (3<=N<=50). Then in several lines there will be (N*(N-1))/2 positive integer(less than 10000) indicating the readings of the balance. Input will be terminated by EOF.
If you get a solution then in each case you have to print N integers on a single line which indicates the weight of each sphere in ascending order of weight. There can be infinite solutions of the problem because an offset,d if added with each weight then the difference of weight will not change. So the first weight should be zero. Another important thing is each solution has an image which is also a solution. Such as in sample output 1 image of (0 2 3) is (0 1 3) which is also a solution. You have to show the first one.
If no solution is found then just print "Incorrect Balance."
3 1 2 3 3 1 2 2 6 1 2 2 2 3 3 3 4 5 5 5 6 7 8 10
0 2 3 Incorrect Balance. 0 3 5 6 8 10
Md. Kamruzzaman