Counting in Base Minus Two

In base -2 the digits are 0 and 1, and the place values from the right are the powers of -2: 1, -2, 4, -8, 16, -32 and so on. Every whole number, negative or not, can be written this way in exactly one way without leading zeros, and no minus sign is ever needed. For example, 110 is 4 - 2 + 0 = 2, and 11 is -2 + 1 = -1.

Write to_negabinary(n) that returns the base -2 digits of n as a string, with no leading zeros. Zero is written '0'.

Examples

to_negabinary(2)    # returns '110'
to_negabinary(-1)   # returns '11'
to_negabinary(6)    # returns '11010'
to_negabinary(0)    # returns '0'

11010 is 16 - 8 + 0 - 2 + 0 = 6.

Constraints

• -10**18 <= n <= 10**18