Unified State Exam

Sonya is a high school senior, and this year she has to take the Unified State Exam in computer science. She decided to start preparing early and began solving problems from past years' exams.

Many tasks require converting a number from one numeral system to another. Sonya handles such tasks with ease, but recently she came across a problem in one of the exams that seemed quite interesting: the number $x$, given in decimal, has to be converted to the ($-2$)-base numeral system.

Formally, the representation of a number in the ($-2$)-base numeral system is a sequence of numbers $a_0, a_1, \ldots, a_{n-1}$, each of which is 0 or 1, where $n = 1$ or $a_{n-1} \ne 0$, and the following equality holds: $x=\sum_{i=0}^{n-1} a_i (-2)^i.$

For example, 3 in the ($-2$)-base numeral system is represented by the sequence $(1, 1, 1)$: indeed, $1\cdot(-2)^0+1\cdot(-2)^1+1\cdot(-2)^2=1-2+4=3$.

The problem asks to convert only one number to the ($-2$)-base numeral system, but Sonya became curious about the solution to this problem in the general case.

After long deliberation, she turned to you for help. Help her convert the given number to the ($-2$)-base numeral system.

The single line of the input file contains one integer $x$, the number Sonya wants to represent in the ($-2$)-base numeral system ($-10^{18} \le x \le 10^{18}$).

In the first line of the output file, print the number $n$ ($n \ge 1$).

In the second line of the output file, print $n$ numbers $a_0, a_1, \ldots, a_{n-1}$ separated by spaces, the digits of the number $x$ in the ($-2$)-base numeral system ($0 \le a_i \le 1$).

If several answers exist, print any of them.