题目描述

Given an integer $N$, find the base $-2$ representation of $N$.

Here, $S$ is the base $-2$ representation of $N$ when the following are all satisfied:

• $S$ is a string consisting of 0 and 1.
• Unless $S =$ 0, the initial character of $S$ is 1.
• Let $S = S_k S_{k-1} ... S_0$, then $S_0 \times (-2)^0 + S_1 \times (-2)^1 + ... + S_k \times (-2)^k = N$.

It can be proved that, for any integer $M$, the base $-2$ representation of $M$ is uniquely determined.

给定整数 $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$ , $M$ 的基数 $-2$ 表示是唯一确定的。

输入格式

输入内容按以下格式标准输入：

$N$

输出格式

打印 $N$ 的基数 $-2$ 表示。

样例 #1

样例输入 #1

-9

样例输出 #1

1011

样例 #2

样例输入 #2

123456789

样例输出 #2

11000101011001101110100010101

样例 #3

样例输入 #3

0

样例输出 #3

0

说明

数据规模与约定

• 输入的每个值都是整数
• $-10^9 \leq N \leq 10^9$

样例 $1$ 解释

与 $(-2)^0 + (-2)^1 + (-2)^3 = 1 + (-2) + (-8) = -9$ 一样，"1011 "是 $-9$ 的基 $-2$ 表示。