配点 : $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$ 進数表現を出力せよ。

-9

1011

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

123456789

11000101011001101110100010101

0

0