ЕГЭ

소냐는 11학년이고, 올해 정보학 통합 국가 시험을 봐야 한다. 그녀는 미리 준비하기로 마음먹고 지난 몇 년간의 기출 문제를 풀기 시작했다.

많은 문제에서는 수를 한 진법에서 다른 진법으로 변환해야 한다. 소냐는 이런 문제를 쉽게 풀지만, 최근 한 기출 문제에서 꽤 흥미로워 보이는 문제를 만났다. 십진법으로 주어진 수 $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.$

예를 들어, ($-2$)진법에서 3은 나열 $(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}$을 공백으로 구분해 출력한다. 이는 ($-2$)진법에서 수 $x$의 자릿수이다 ($0 \le a_i \le 1$).

여러 답이 존재하면 그중 아무거나 출력한다.