Negative Binary

Time limit

Memory limit

128 MB

Problem

Ordinary binary notation uses powers of 2 as place values. Base -2 notation uses powers of -2 instead: (-2)^0 = 1, (-2)^1 = -2, (-2)^2 = 4, (-2)^3 = -8, alternating between positive and negative values. Each digit is either 0 or 1.

Given a decimal integer N, write a program that prints the representation of N in base -2.

Input

The first line contains a decimal integer N.

Output

Print the base -2 representation of N.

Constraints

-2,000,000,000 <= N <= 2,000,000,000