Pairwise sums of n numbers  (i.e. NC2 sums)are given in sorted order.

You need to identify the numbers and print then. If there are several solutions print the lexographically smallest one.

The Output should have natural numbers only.

Input

NC2 <=50

NC2 numbers each <=10^5

Output

lexographically smallest set of numbers

Example

Input:

1
2 
Output:
1 1

Input:
3
2 2 2 

Output:
1 1 1
Input:
6
2 2 2 3 3 3

Output:
1 1 1 2

Input:
1
4 
Output:
1 3
</p>
(here 2 2 and 3 1 are also possible solutions but we have to print the lexographically smallest one)