E. Двоичные карты
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Никогда не поздно научиться играть в увлекательную игру под названием «Двоичные карты»!

В игре участвует неограниченное число игральных карт разных положительных и отрицательных достоинств. Абсолютная величина, написанная на любой карте, является степенью двойки, то есть на карте может быть написано либо 2k, либо  - 2k для некоторого целого k ≥ 0. Карты любого достоинства имеются в неограниченном количестве.

В начале игрок выбирает себе колоду — некоторое множество (возможно пустое) игральных карт. При этом в колоду разрешается включить произвольное количество карт каждого из достоинств, но уровень игрока оценивают по тому, насколько мало карт он включает в свою колоду. Игра состоит из n конов. На i-м кону жюри называет игроку целое число ai. После этого игрок обязан выложить на стол такое подмножество карт из своей колоды, что сумма достоинств этих карт в точности равна ai (можно не выкладывать никакие карты вообще, тогда сумма считается равной нулю). Если игрок не может выложить нужный набор карт, он считается проигравшим, а игра заканчивается. В противном случае игрок возвращает выложенные карты назад в свою колоду и переходит к следующему кону. Игрок считается победителем, если он на каждом кону смог выложить необходимые карты.

До вас дошли слухи, какие числа ai жюри собирается назвать на каждом кону. Теперь вы хотите выбрать колоду с минимальным количеством карт, которая позволит вам выиграть в «Двоичные карты».

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

В первой строке находится целое число n (1 ≤ n ≤ 100 000) — количество названных чисел в игре.

Во второй строке находятся n целых чисел a1, a2, ..., an ( - 100 000 ≤ ai ≤ 100 000) — числа, называемые на каждом кону.

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

В первой строке выведите число k (0 ≤ k ≤ 100 000) — минимальное количество карт, которые нужно выбрать в колоду, чтобы выиграть в «Двоичные карты».

Во второй строке выведите k целых чисел b1, b2, ..., bk ( - 220 ≤ bi ≤ 220, |bi| является степенью двойки) — достоинства карт, составляющих колоду. Достоинства можно выводить в любом порядке. Если существует несколько колод оптимального размера, разрешается вывести любую из них.

Гарантируется, что существует колода карт минимального размера, удовлетворяющая требованиям на величины чисел выше.

Примеры
Входные данные
1
9
Выходные данные
2
1 8
Входные данные
5
-1 3 0 4 7
Выходные данные
3
4 -1 4
Входные данные
4
2 -2 14 18
Выходные данные
3
-2 2 16
Примечание

В первом тесте из условия на единственном кону можно положить обе карты из колоды. Обратите внимание, этот тест из условия — единственный из подходящих под ограничения первой группы тестов.

Во втором тесте из условия в первый кон можно выложить единственную карту  - 1, во второй кон — карты 4 и  - 1, в третий кон можно не выкладывать ничего, в четвёртый кон — только карту 4, а в пятый кон — всю колоду.