MAKESUM - MAKESUM

no tags 

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 ≤ 105.

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.


hide comments
Prof_Utonium_ಉಮೆಶ್: 2013-02-05 18:58:48

I think one of the test cases has a newline in first line. If writing in Java, use Scanner to read input.

priyamehtanit : 2012-06-26 23:50:45

Thanks a lot.. for your comments :)

যোবায়ের: 2012-06-24 22:48:03

nice one :)

Massand Sagar Sunil: 2012-06-21 18:30:55

Can nc2 be equal to 5 or 4?

:D: 2012-06-01 18:28:28

Fun problem. I could have used a bigger constrains version. My algo was pretty clunky. It would be nice to see how it fairs against other ones with harder test data.


Added by:priyamehtanit
Date:2012-06-01
Time limit:0.201s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own