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 lexicographically smallest one.

The Output should have natural numbers only.

Input

NC2 <= 50

NC2 numbers each <= 10^5

Output

lexicographically 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

Here 2 2 and 3 1 are also possible solutions but we have to print the lexicographically smallest one.