Піца#8363
Усім учасникам олімпіади відомо, що перед туром слід добре поїсти. З цією метою Степан вирішив замовити вегетаріанську піцу. Піцерія, яку обрав Степан, надає клієнтам можливість обрати інгредієнти для піци самостійно. У наявності піцерії інгредієнтів, кожен з яких має свою вартість. Степан не може додати до піци один і той самий інгредієнт більше одного разу. Вартість піци рахується як сума вартостей усіх інгредієнтів, що до неї входять.
Неважко підрахувати, що різних варіантів зібрати піцу (окрім нецікавого Степану варіанту піци без інгредієнтів) аж цілих 2^N - 1. Степан розгубився і вирішив для зручності записати на листочку вартості усіх можливих піц.
Смачно поївши, Степан чудово написав тур олімпіади. Задоволений, він вже збирався йти відпочивати, але зрозумів, що забув вартість кожного з інгредієнтів. На щастя, Степан зберіг листочок з вартостями усіх варіантів піци, а тому може дізнатися, скільки коштував кожен інгредієнт.
Напишіть програму, яка за інформацією про вартості усіх варіантів піци дозволить відновити інформацію про ціни окремих інгредієнтів.
В першому рядку вхідного файлу pizza.in міститься єдине ціле число (1 \leq N \leq 17) — кількість інгредієнтів. Другий рядок містить рівно 2^N - 1 цілих додатних чисел, кожне з яких не перевищує 10^6 — вартості для усіх варіантів піци.
В єдиному рядку файлу pizza.out має міститися рівно додатних цілих чисел у зростаючому порядку — вартості кожного з інгредієнтів. Якщо існує декілька відповідей, виведіть будь-яку. Якщо Степан щось наплутав і неможливо відновити вартості для кожного інгредієнта, виведіть єдине число .
Приклад 1
Приклад 2
Приклад 3
Підзадача | Бали | Додаткові обмеження | Необхідні підзадачі |
Тести з умови | - | ||
вартості інгредієнтів — попарно різні степені двійки, відповідь завжди існує | - | ||
1 \leq N \leq 4, числа у вхідному файлі | |||
1 \leq N \leq 4 | |||
1 \leq N \leq 10 | |||
Без додаткових обмежень | 0, 2, 3, 4 |