Cho số nguyên \(n\). Hãy biểu diễn số \(n\) sang hệ cơ số -2. Ở đây, \(s\) là biểu diễn của hệ cơ sô -2 từ số \(n\) khi các điều kiện sau đây được thỏa mãn:

• \(s\) là một xâu chứa các kí tự 0 và 1.
• Trừ khi \(s\) = 0, kí tự đầu tiên của \(s\) là 1.
• Đặt \(s=s_ks_{k-1}...s_0\) thì \(s_0.(-2)^0+s_1.(-2)^1+...+s_k.(-2)^k = n\).

INPUT FORMAT

Một dòng duy nhất gồm số nguyên dương \(n\) \((-10^9 \leq n \leq 10^9)\).

OUTPUT FORMAT

In ra biểu diễn hệ cơ số -2 của \(n\).

Ví dụ 1:

Input

-9

Output

1011

Ví dụ 2:

Input

123456789

Output

11000101011001101110100010101

Giải thích ví dụ mẫu

Ví dụ 1:

• Input: -9
• Giải thích: Biểu diễn số -9 trong hệ cơ số -2 là 1011, thể hiện rằng -9 có thể được tạo thành từ các lũy thừa của -2.

Ví dụ 2:

• Input: 123456789
• Giải thích: Biểu diễn số 123456789 trong hệ cơ số -2 là 11000101011001101110100010101, cho thấy cách số này được cấu thành từ các lũy thừa của -2.
  

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House