{"raw_statement":[{"iden":"statement","content":"Alex has two magic machines A and B. Machine A will give you 2x + 1 coins if you insert x coins in it, machine B will give you 2x + 2. Alex has no coins and wants to get exactly n coins in order to buy a new unicorn, but he can't figure out how to do it. Your task is to find a way to use the machines to get exactly n coins.\n\nThe input consists of a single line containing n (1 ≤ n ≤ 109).\n\nFor each one output a string of A's and B's giving the order in which the machines are used.\n\n"},{"iden":"input","content":"The input consists of a single line containing n (1 ≤ n ≤ 109)."},{"iden":"output","content":"For each one output a string of A's and B's giving the order in which the machines are used."},{"iden":"examples","content":"Input7OutputAAAInput10OutputABB"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 10^9 $.  \nDefine two operations:  \n- Operation $ A $: $ x \\mapsto 2x + 1 $  \n- Operation $ B $: $ x \\mapsto 2x + 2 $  \n\n**Constraints**  \nStart from $ x = 0 $. Apply a sequence of operations $ A $ and $ B $ to reach exactly $ n $.  \n\n**Objective**  \nFind a string $ s \\in \\{A, B\\}^* $ such that applying the operations in order from left to right to initial value $ 0 $ yields $ n $.","simple_statement":"Given n, find a sequence of A and B operations to get exactly n coins, starting from 0.  \nA: x → 2x + 1  \nB: x → 2x + 2  \nOutput the sequence of A's and B's.","has_page_source":false}