题目描述

题目译自 Open Olympiad in Informatics 2018 Day1 T4 「Двоичные карты / Binary Cards」。

学习玩一款名为《二进制卡牌》的有趣游戏永远都不晚！

这款游戏使用无限数量的卡牌，这些卡牌的面值可以是正数也可以是负数。任何卡牌上标注的绝对值都是 $2$ 的幂，即卡牌上的值可以是 $2^k$ 或 $-2^k$，其中 $k$ 为某个非负整数。任何面值的卡牌数量都是无限的。

游戏开始时，玩家需要选择一副牌组——即一组卡牌（可以为空）。玩家可以任意选择每种面值的卡牌数量加入牌组，但玩家的水平通过牌组中卡牌数量的多少来评估，卡牌数量越少越好。游戏包含 $n$ 个回合。在第 $i$ 个回合，评委向玩家宣布一个整数 $a_i$。随后，玩家必须从自己的牌组中选出一部分卡牌，使这些卡牌面值之和恰好等于 $a_i$（可以不选择任何卡牌，此时和视为 $0$）。如果玩家无法选出符合要求的卡牌组合，则被判输，游戏结束。否则，玩家将选出的卡牌放回牌组，进入下一个回合。如果玩家能在每个回合都成功选出所需卡牌，则被视为获胜。

你听到了评委在每个回合将要宣布的数字 $a_i$ 的传闻。现在，你希望选择一个卡牌数量最少的牌组，使你能在《二进制卡牌》中获胜。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 100000)$，表示游戏中评委宣布的数字数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(-100000 \leq a_i \leq 100000)$，表示每个回合评委宣布的数字。

输出格式

第一行输出一个整数 $k$ $(0 \leq k \leq 100000)$，表示为了在《二进制卡牌》中获胜，需要选择的最小卡牌数量。

第二行输出 $k$ 个整数 $b_1, b_2, \ldots, b_k$（$-2^{20} \leq b_i \leq 2^{20}$，且 $|b_i|$ 是 $2$ 的幂），表示构成牌组的卡牌面值。面值可以按任意顺序输出。如果存在多个最优大小的牌组，可以输出其中任意一个。

保证存在一个最小规模的牌组，满足上述数值限制的要求。

1
9

2
1 8

在第一个样例中，在唯一的回合中可以同时使用牌组中的两张卡牌。注意，此样例是唯一符合第一个子任务限制的样例。

5
-1 3 0 4 7

3
4 -1 4

在第二个样例中：

• 第一回合可以只使用卡牌 $-1$；
• 第二回合可以使用卡牌 $4$ 和 $-1$；
• 第三回合可以不使用任何卡牌；
• 第四回合只使用卡牌 $4$；
• 第五回合使用整个牌组。

4
2 -2 14 18

3
-2 2 16

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。