MOG
Spanish
|
English

Matcom Online Grader

Latin American Regional Contest - 2018

Ended

K - KryptoLocker Ate my Homework

Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)

Your friend’s computer was infected by KryptoLocker last night. KryptoLocker is a ransomware that encrypts user’s data making it unusable until a ransom is paid to the person behind the attack.

Luckily your friend noticed there was something weird happening and was able to stop the malicious process before all data was lost. Unfortunately it didn’t happen in time to save the homework he had just finished.

“The dog ate my homework” never really worked as an excuse for most teachers and probably things won’t be different with “KryptoLocker encrypted my homework”.

But not all hope is lost. For this homework each student was assigned an array of integer numbers $v_1 \leq v_2 \leq ... \leq v_N$ . Then, each student had to generate a list of $2^N$ numbers, containing the sums of the elements in each possible subsequence of the array. KryptoLocker only corrupted the first line of the file containing your friend’s answer and this was the line where the array was written. So, all sums are still known and that should be enough to recover the array.

Can you help your friend save his homework?

Input

The first line contains an integer $N$ $(1 \leq N \leq 18)$ indicating the number of elements in the array assigned to your friend. Each of the next $2^N$ lines contains an integer $S$ $(−10^9 \leq S \leq 10^9)$ representing the sum of the elements in a subsequence of the array. The sums of all possible subsequences appear in the input, in no particular order. There is at least one array whose sums are the values given.

Output

Output each different array that may have been assigned to your friend, one array per line, with the lines lexicographically sorted. Two arrays are considered different if, and only if, they contain different elements in at least one position.

Sample test(s)

Input
3 9 8 7 0 15 16 17 24
Output
7 8 9
Input
2 1 0 -1 0
Output
-1 1