eolymp
bolt
Try our new interface for solving problems
Problems

Піца

Піца

Time limit 1 second
Memory limit 64 MiB

Усім учасникам олімпіади відомо, що перед туром слід добре поживитися. З цією метою Степан вирішив замовити вегетаріанську піцу. Піцерія, яку обрав Степан, надає клієнтам можливість обрати інгредієнти для піци самостійно. У наявності піцерії N інгредієнтів, кожен з яких має свою вартість. Степан не може додати до піци один і той самий інгредієнт більше одного разу. Вартість піци рахується як сумма вартостей усіх інгредієнтів, що до неї входять.

Неважко підрахувати, що різних варіантів зібрати піцу (окрім нецікавого Степану варіанту піци без інгредієнтів) аж цілих 2^N - 1. Степан розгубився і вирішив для зручності записати на листочку вартості усіх можливих піц.

Смачно поївши, Степан чудово написав тур олімпіади. Задоволений, він вже збирався йти відпочивати, але зрозумів, що забув вартість кожного з N інгредієнтів. На щастя, Степан зберіг листочок з вартостями усіх варіантів піци, а тому може дізнатися, скільки коштував кожен інгредієнт.

####Завдання

Напишіть програму, яка за інформацією про вартості усіх варіантів піци дозволить відновити інформацію про ціни окремих інгредієнтів.

Input data

В першому рядку вхідного файлу pizza.in мiститься єдине цiле число N(1 ≤ N ≤ 17) – кiлькiсть iнгредiєнтiв. Другий рядок мiстить рiвно 2^N−1 цiлих додатнiх чисел, кожне з яких не перевищує 10^6 – вартостi для усiх варiантiв пiци.

Output data

В єдиному рядку файлу pizza.out має міститися рiвно N додатнiх цілих чисел у зростаючому порядку – вартостi кожного з N iнгредiєнтiв. Якщо існує декілька відповідей, виведіть будь-яку. Якщо Степан щось наплутав і неможливо неможливо відновити вартості для кожного інгредієнту, виведіть єдине число -1.

####Оцінювання

Пiдзадача Бали Додатковi обмеження Необхідні підзадачі

0	0	Тести з умови	-

1	18	вартостi iнгредiєнтiв – попарно рiзнi степенi	- двійки, вiдповiдь завжди iснує	

2	22	1 ⩽ N ⩽ 4, 1 ⩽ числа у вхідному файлі ⩽ 10	0

3	22	1 ⩽ N ⩽ 4	0, 2

4	17	1 ⩽ N ⩽ 10	0, 2, 3

5	21	Без додаткових обмежень	0, 2, 3, 4

Examples

Input example #1
3
1 2 3 4 5 6 7
Output example #1
1 2 4
Input example #2
3
1 2 3 3 4 5 6
Output example #2
1 2 3
Input example #3
2
3 2 2
Output example #3
-1