玩精美的“二进制卡牌”游戏永远不会太晚!
游戏中使用的正数和负数卡牌的数量是无限的。任何卡牌等级的绝对值都是 2 的幂,即对于某个整数 k ≥ 0,每张卡的等级为 2k 或 - 2k。任何有效等级的卡牌数量都是无限的。
在游戏开始时,玩家形成他的牌组,该牌组是一些多组(可能是空的)牌。允许选择任何数量的任何级别的牌,但小牌组被认为是技能指标。游戏由n轮组成。在第 i 轮中,陪审团告诉玩家一个整数 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| 是 2 的幂),即你牌组中牌的排名。您可以按任何顺序输出排名。如果有多个最佳牌组,您可以打印其中任何一个。
保证存在满足上述所有要求的最小尺寸的牌组。
示例
输入 #1
1 9
输出 #1
2 1 8
输入 #2
5 -1 3 0 4 7
输出 #2
3 4 -1 4
输入 #3
4 2 -2 14 18
输出 #3
3 -2 2 16
注意
在第一个示例中,游戏中有唯一一轮,您可以简单地抽出两张牌。请注意,此示例测试是唯一满足第一个测试组约束的测试。
在第二个示例中,您可能在第一轮中抽出唯一的牌 - 1,在第二轮中抽出牌 4 和 - 1,在第三轮中什么都没有,在第四轮中抽出唯一的牌 4,在第五轮中抽出整副牌。