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

n ≤ 50

n numbers each ≤ 10⁵.

Output

The 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.