Пицца

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

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

После вкусного обеда Степан успешно написал тур олимпиады. Довольный, он уже собирался отдыхать, но понял, что забыл стоимость каждого из N ингредиентов. К счастью, у него остался листочек со стоимостями всех вариантов пиццы, и он может восстановить стоимость каждого ингредиента.

Задание

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

Входные данные

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

Выходные данные

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

Примеры

Оценивание