Pizza
All participants of the olympiad know that having a good meal before the round is essential. With this in mind, Stepan decided to order a vegetarian pizza. The pizzeria he chose allows customers to select their own ingredients for the pizza. There are N ingredients available, each with a specific cost. Stepan cannot add the same ingredient more than once. The total cost of the pizza is the sum of the costs of all the ingredients included.
There are 2^N - 1 different combinations to assemble a pizza (excluding the option of a pizza without ingredients, which Stepan finds uninteresting). Stepan was overwhelmed by the choices and decided to write down the costs of all possible pizzas on a piece of paper.
After enjoying his meal, Stepan performed excellently in the olympiad. As he was about to rest, he realized he forgot the cost of each of the N ingredients. Fortunately, he still had the piece of paper with the costs of all pizza combinations, which could help him determine the cost of each ingredient.
Task
Write a program that, given the costs of all pizza combinations, will help restore the prices of the individual ingredients.
Input
The first line of the input file pizza.in contains a single integer N (1 ≤ N ≤ 17) – the number of ingredients. The second line contains exactly 2^N−1 positive integers, each not exceeding 10^6 – the costs for all pizza combinations.
Output
The single line of the file pizza.out should contain exactly N positive integers in ascending order – the costs of each of the N ingredients. If there are multiple solutions, output any one of them. If Stepan made a mistake and it's impossible to determine the costs for each ingredient, output the single number -1.
Scoring
Subtask Points Additional Constraints Required Subtasks
0 0 Tests from the condition - 1 18 The ingredient costs are pairwise distinct powers of two, the answer always exists 2 22 1 ⩽ N ⩽ 4, 1 ⩽ numbers in the input file ⩽ 10 0 3 22 1 ⩽ N ⩽ 4 0, 2 4 17 1 ⩽ N ⩽ 10 0, 2, 3 5 21 No additional constraints 0, 2, 3, 4