CF949E.Binary Cards

It is never too late to play the fancy "Binary Cards" game!

There is an infinite amount of cards of positive and negative ranks that are used in the game. The absolute value of any card rank is a power of two, i.e. each card has a rank of either 2_k_ or  - 2_k_ for some integer k ≥ 0. There is an infinite amount of cards of any valid rank.

At the beginning of the game player forms his deck that is some multiset (possibly empty) of cards. It is allowed to pick any number of cards of any rank but the small deck is considered to be a skill indicator. Game consists of n rounds. In the i-th round jury tells the player an integer a__i. After that the player is obligated to draw such a subset of his deck that the sum of ranks of the chosen cards is equal to a__i (it is allowed to not draw any cards, in which case the sum is considered to be equal to zero). If player fails to do so, he loses and the game is over. Otherwise, player takes back all of his cards into his deck and the game proceeds to the next round. Player is considered a winner if he is able to draw the suitable set of cards in each of the rounds.

Somebody told you which numbers a__i the jury is going to tell you in each round. Now you want to pick a deck consisting of the minimum number of cards that allows you to win the "Binary Cards" game.

玩时尚的“二进制卡片”游戏，永远都不晚！

游戏中使用了无限张正负等级的卡片。任意卡片的等级的绝对值均为 2 的幂次，即每张卡片的等级为 $2^k$ 或 $-2^k$（其中 $k$ 为满足 $k \geq 0$ 的整数）。对于任意合法的等级，均有无限张对应卡片。

游戏开始时，玩家需构建自己的牌组——即某个（可能为空的）多重集合。允许选取任意数量、任意等级的卡片，但较小的牌组被视为技巧的体现。游戏共进行 $n$ 轮。在第 $i$ 轮中，裁判会告知玩家一个整数 $a_i$。此后，玩家必须从自己的牌组中选出一个子集，使得所选卡片等级之和恰好等于 $a_i$（允许不选任何卡片，此时和视为 0）。若玩家无法做到，则判负，游戏结束；否则，玩家将所有已出卡片收回牌组，游戏进入下一轮。若玩家能在每一轮中均成功选出满足条件的卡片子集，则视为获胜。

已知裁判将在每轮中告知的数字 $a_i$。现在，你希望构造一个包含最少张卡片的牌组，使得你能赢得这场“二进制卡片”游戏。

The first line of input contains an integer n (1 ≤ n ≤ 100 000), the number of rounds in the game.

The second line of input contains n integers _a_1, _a_2, ..., a__n ( - 100 000 ≤ a__i ≤ 100 000), the numbers that jury is going to tell in each round.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 100\,000$），表示游戏的轮数。

输入的第二行包含 $n$ 个整数 $a_1,\,a_2,\,\ldots,\,a_n$（$-100\,000 \leq a_i \leq 100\,000$），表示裁判在每一轮中将说出的数字。

In the first line print the integer k (0 ≤ k ≤ 100 000), the minimum number of cards you have to pick in your deck in ordered to win the "Binary Cards".

In the second line print k integers _b_1, _b_2, ..., b__k ( - 220 ≤ b__i ≤ 220, |b__i| is a power of two), the ranks of the cards in your deck. You may output ranks in any order. If there are several optimum decks, you are allowed to print any of them.

It is guaranteed that there exists a deck of minimum size satisfying all the requirements above.

第一行输出整数 $k$（$0 \le k \le 100\,000$），即为赢得“二进制卡片”（Binary Cards）游戏所需选取的最少卡片数量。

第二行输出 $k$ 个整数 $b_1,\,b_2,\,\dots,\,b_k$（$-2^{20} \le b_i \le 2^{20}$，且 $|b_i|$ 是 2 的幂），表示你牌组中各卡片的点数。这些点数可以以任意顺序输出。若存在多个满足最小尺寸的最优牌组，输出其中任意一个即可。

题目保证存在一个满足上述所有要求的、尺寸最小的牌组。

In the first sample there is the only round in the game, in which you may simply draw both your cards. Note that this sample test is the only one satisfying the first test group constraints.

In the second sample you may draw the only card  - 1 in the first round, cards 4 and  - 1 in the second round, nothing in the third round, the only card 4 in the fourth round and the whole deck in the fifth round.

在第一个样例中，游戏中仅有 1 轮，在该轮中你可以直接抽走你手中的全部两张牌。注意，该样例测试是唯一满足第一组测试约束条件的测试用例。

在第二个样例中，你可以在第一轮抽到唯一的一张牌 $-1$，第二轮抽到两张牌 $4$ 和 $-1$，第三轮不抽牌，第四轮抽到唯一的一张牌 $4$，第五轮抽走整副牌。