负二进制表示

题目描述

给定整数 $N$，请计算 $N$ 的 $-2$ 进制表示。

这里，$S$ 是 $N$ 的 $-2$ 进制表示，当且仅当满足以下全部条件：

• $S$ 是仅由 0 和 1 组成的字符串
• 若 $S =$ 0 不成立，则 $S$ 的首字符为 1
• 设 $S = S_k S_{k-1} ... S_0$，则 $S_0 \times (-2)^0 + S_1 \times (-2)^1 + ... + S_k \times (-2)^k = N$ 成立

另外，可以证明任意整数 $M$ 的 $-2$ 进制表示都是唯一确定的。

输入格式

输入从标准输入按以下格式给出。

$N$

输出格式

输出 $N$ 的 $-2$ 进制表示。

样例

-9

1011

因为 $(-2)^0 + (-2)^1 + (-2)^3 = 1 + (-2) + (-8) = -9$，所以 1011 是 $-9$ 的 $-2$ 进制表示。

123456789

11000101011001101110100010101

0

0

数据范围

• 输入全部为整数

• $-10^9 \leq N \leq 10^9$