配点 : $300$ 点

問題文

整数 $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$ 進数表現が一意に定まることが証明できます。

制約

• 入力はすべて整数である
• $\-10^9 \\leq N \\leq 10^9$

入力

入力は以下の形式で標準入力から与えられる。

$N$

出力

$N$ の $\-2$ 進数表現を出力せよ。

入力例 1

-9

出力例 1

1011

$(-2)^0 + (-2)^1 + (-2)^3 = 1 + (-2) + (-8) = -9$ なので 1011 は $\-9$ の $\-2$ 進数表現です。

入力例 2

123456789

出力例 2

11000101011001101110100010101

入力例 3

0

出力例 3

0