Pizza#8363
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 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 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.
Write a program that, given the costs of all pizza combinations, will help restore the prices of the individual ingredients.
The first line of the input file pizza.in contains a single integer (1 \leq N \leq 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.
The single line of the file pizza.out should contain exactly positive integers in ascending order — the costs of each of the 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 .
Exemple 1
Exemple 2
Exemple 3
Subtask | Points | Additional Constraints | Required Subtasks |
Tests from the condition | - | ||
The ingredient costs are pairwise distinct powers of two, the answer always exists | - | ||
1 \leq N \leq 4, numbers in the input file | |||
1 \leq N \leq 4 | |||
1 \leq N \leq 10 | |||
No additional constraints | 0, 2, 3, 4 |