{"raw_statement":[{"iden":"statement","content":"It is never too late to play the fancy \"Binary Cards\" game!\n\nThere 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.\n\nAt 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.\n\nSomebody 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."},{"iden":"input","content":"The first line of input contains an integer _n_ (1 ≤ _n_ ≤ 100 000), the number of rounds in the game.\n\nThe 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."},{"iden":"output","content":"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\".\n\nIn 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.\n\nIt is guaranteed that there exists a deck of minimum size satisfying all the requirements above."},{"iden":"examples","content":"Input\n\n1\n9\n\nOutput\n\n2\n1 8\n\nInput\n\n5\n-1 3 0 4 7\n\nOutput\n\n3\n4 -1 4\n\nInput\n\n4\n2 -2 14 18\n\nOutput\n\n3\n-2 2 16"},{"iden":"note","content":"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.\n\nIn 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."}],"translated_statement":[{"iden":"statement","content":"玩精致的“二进制卡”游戏，永远都不晚！\n\n游戏中使用无限多张正负权值的卡牌。任意一张卡牌的权值绝对值均为 2 的幂，即每张卡牌的权值为 #cf_span[2k] 或 #cf_span[ - 2k]（其中某个整数 #cf_span[k ≥ 0]）。对于任意合法权值，都存在无限多张该权值的卡牌。\n\n游戏开始时，玩家构建自己的牌组，即一个多重集（可能为空）。允许选择任意数量的任意权值卡牌，但牌组越小，越能体现玩家的技术水平。游戏共进行 #cf_span[n] 轮。在第 #cf_span[i] 轮，裁判会告诉玩家一个整数 #cf_span[ai]。随后，玩家必须从自己的牌组中选出一个子集，使得所选卡牌的权值之和恰好等于 #cf_span[ai]（允许不选任何卡牌，此时和视为零）。如果玩家无法做到这一点，则失败，游戏结束；否则，玩家将所有卡牌收回牌组，进入下一轮。如果玩家在每一轮都能选出合适的卡牌子集，则视为获胜。\n\n有人告诉你裁判在每一轮会给出的数字 #cf_span[ai]。现在你希望选择一个包含最少数量卡牌的牌组，以确保赢得“二进制卡”游戏。\n\n输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100 000]），表示游戏的轮数。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[ - 100 000 ≤ ai ≤ 100 000]），表示裁判在每一轮给出的数字。\n\n第一行输出一个整数 #cf_span[k]（#cf_span[0 ≤ k ≤ 100 000]），表示为了赢得“二进制卡”游戏，你必须在牌组中选择的最少卡牌数量。\n\n第二行输出 #cf_span[k] 个整数 #cf_span[b1, b2, ..., bk]（#cf_span[ - 220 ≤ bi ≤ 220]，且 #cf_span[|bi|] 是 2 的幂），表示你牌组中每张卡牌的权值。你可以按任意顺序输出权值。如果有多个最优牌组，允许输出其中任意一个。\n\n保证存在满足上述所有要求的最小规模牌组。\n\n在第一个样例中，游戏中只有一轮，你只需抽出两张牌即可。注意，该样例是唯一满足第一测试组约束的测试用例。\n\n在第二个样例中，第一轮可抽出唯一一张卡牌 #cf_span[ - 1]，第二轮抽出卡牌 #cf_span[4] 和 #cf_span[ - 1]，第三轮不抽牌，第四轮抽出唯一一张卡牌 #cf_span[4]，第五轮抽出整个牌组。"},{"iden":"input","content":"输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100 000]），表示游戏的轮数。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[ - 100 000 ≤ ai ≤ 100 000]），表示裁判在每一轮给出的数字。"},{"iden":"output","content":"第一行输出一个整数 #cf_span[k]（#cf_span[0 ≤ k ≤ 100 000]），表示为了赢得“二进制卡”游戏，你必须在牌组中选择的最少卡牌数量。第二行输出 #cf_span[k] 个整数 #cf_span[b1, b2, ..., bk]（#cf_span[ - 220 ≤ bi ≤ 220]，且 #cf_span[|bi|] 是 2 的幂），表示你牌组中每张卡牌的权值。你可以按任意顺序输出权值。如果有多个最优牌组，允许输出其中任意一个。保证存在满足上述所有要求的最小规模牌组。"},{"iden":"examples","content":"输入19输出21 8输入5-1 3 0 4 7输出34 -1 4输入42 -2 14 18输出3-2 2 16"},{"iden":"note","content":"在第一个样例中，游戏中只有一轮，你只需抽出两张牌即可。注意，该样例是唯一满足第一测试组约束的测试用例。在第二个样例中，第一轮可抽出唯一一张卡牌 #cf_span[ - 1]，第二轮抽出卡牌 #cf_span[4] 和 #cf_span[ - 1]，第三轮不抽牌，第四轮抽出唯一一张卡牌 #cf_span[4]，第五轮抽出整个牌组。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of rounds.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the sequence of integers presented in each round, where $ a_i \\in \\mathbb{Z} $ and $ -100000 \\leq a_i \\leq 100000 $.  \n\nLet $ D \\subseteq \\{ \\pm 2^k \\mid k \\in \\mathbb{Z}_{\\geq 0} \\} $ be a multiset (deck) of cards, where each card has rank equal to $ \\pm 2^k $ for some $ k \\geq 0 $.  \n\n**Constraints**  \nFor each $ i \\in \\{1, \\dots, n\\} $, there exists a subset $ D_i \\subseteq D $ such that:  \n$$\n\\sum_{d \\in D_i} d = a_i\n$$  \nThe deck $ D $ must be chosen to minimize $ |D| $, the total number of cards (counting multiplicities).  \n\n**Objective**  \nFind a multiset $ D $ of minimum cardinality such that every $ a_i $ is representable as a subset sum of $ D $, where each element of $ D $ is of the form $ \\pm 2^k $ for $ k \\geq 0 $.  \n\nOutput:  \n- The size $ k = |D| $  \n- The list of card ranks in $ D $, each satisfying $ |\\text{rank}| = 2^k $ for some $ k \\geq 0 $, and $ |\\text{rank}| \\leq 2^{20} $","simple_statement":null,"has_page_source":false}