Cities of the Nile

The first line contains a single integer N, representing the number of settlements, where 3 ≤ N ≤ 25.

Following this, there are N*(N-1)/2 lines, each containing a positive integer that represents the distance between two settlements. These distances are listed in ascending order, and no distance exceeds 100,000.

Output

Output the distances from the mouth of the Nile to each of the N settlements, one per line, in ascending order. The distance to the first settlement is always 0.

Examples