Inexperienced in the digital arts, the cows tried to build a calculating engine (yes, it's a cowmpouter) using binary numbers (base 2) but instead built one based on base negative 2! They were quite pleased since numbers expressed in base -2 do not have a sign bit.
The place values in base -2, from right to left, are 1, -2, 4, -8, 16, -32, and so on. Thus, counting from 1 goes like this: 1, 110, 111, 100, 101, 11010, 11011, 11000, 11001, and so on. Negative numbers are also represented using 1s and 0s without a sign. For example, counting down from -1 goes 11, 10, 1101, 1100, 1111, and so on.
Help the cows convert ordinary decimal integers to their base -2 representations.
Input
A single integer in the range -2,000,000,000..2,000,000,000.
Output
The input integer written in base -2, with no leading zeroes. Write 0 as exactly 0.
Examples
Input 1
-13Output 1
110111