19981번 - ЕГЭ 스페셜 저지다국어

Соня --- одиннадцатиклассница, и в этом году ей надо сдавать единый государственный экзамен по информатике. Она решила начать готовиться заранее и стала решать задачи из вариантов прошлых лет. 

В многих заданиях требуется перевести число из одной системы счисления в другую. Соня с легкостью справляется с такими заданиями, но недавно в одном из вариантов ей попалась задача, которая показалась довольно интересной: число $x$, заданное в десятичной системе счисления, требуется перевести в ($-2$)-ичную систему счисления. 

Формально, записью числа в ($-2$)-ичной системе счисления называется набор чисел $a_0, a_1, \ldots, a_{n-1}$, каждое из которых равно 0 или 1, причем $n = 1$ или $a_{n-1} \ne 0$ и выполнено равенство: $$x=\sum_{i=0}^{n-1} a_i (-2)^i.$$

Например, 3 в ($-2$)-ичной системе счисления представляется набором $(1, 1, 1)$: действительно, $1\cdot(-2)^0+1\cdot(-2)^1+1\cdot(-2)^2=1-2+4=3$.

В задаче предлагается перевести в ($-2$)-ичную систему счисления только одно число, но Соне стало интересно решение этой задачи в общем случае.

После долгих раздумий она обратилась к вам за помощью. Помогите ей перевести заданное число в ($-2$)-ичную систему счисления.

В единственной строке входного файла записано одно целое число $x$ --- число, которое Соня хочет представить в ($-2$)-ичной системе счисления ($-10^{18} \le x \le 10^{18}$).

В первой строке выходного файла выведите число $n$ ($n \ge 1$).

Во второй строке выходного файла через пробел выведите $n$ чисел $a_0, a_1, \ldots, a_{n-1}$ --- цифры числа $x$ в ($-2$)-ичной системе счисления ($0 \le a_i \le 1$).

Если существует несколько ответов, выведите любой из них.