Time limit per test: 1.5
Memory limit: 65536
Scientist Shurik needs voltage that is N
times more that the standard voltage in the wall outlet for power supply for his time machine. The standard voltage is equal to one Bervolt. Shurik decided to use voltage amplifiers. In the nearby shop he found the amplifiers of two types, the first type creates voltage 2X-1 Bervolt from X
Bervolt, the second one creates voltage 2X+1 Bervolt from X
Bervolt. The number of amplifiers in the shop is unlimited. Shurik wants to build a sequence of amplifiers from the outlet to the time machine. Of course he wants to minimize the number of amplifiers. Help him.
A single integer 1 ≤ N
≤ 2· 109
If it is possible to make such scheme, output in the first line the minimal possible number of amplifiers. The second line in this case is to contain the sequence of amplifiers from the outlet to the time machine. Use number 1 for the first-type amplifiers and number 2 for second-type amplifiers.
If there is no solution, output "
" (without quotes).