# Problem A

Power Signs

“Increase my killing power, eh?”– Homer Simpson

You are probably familiar with the binary representation of
integers, i.e. writing a nonnegative integer $n$ as $\sum _{i=0}^ k a_ i \cdot 2^ i$,
where each $a_ i$ is
either $0$ or $1$. In this problem, we consider a so
called *signed binary representation*, in which we still
write $n$ as $\sum _{i=0}^{k} a_ i \cdot 2^ i$, but
allow $a_ i$ to take on
the values $-1$,
$0$ and $1$. For instance, $n=13$ can be represented
as

The binary representation of a number is unique, but obviously, the signed binary representation is not. In certain applications (e.g. in cryptography), one seeks to write a number $n$ in signed binary representation with as few non-zero digits as possible. For example, we consider the representation $(1, 0, 0, -1)$ to be a better representation of $n = 7$ than $(1, 1, 1)$. Your task is to write a program which will find such a minimal representation.

## Input

The input consists of a single line containing a positive integer $n < 2^{100\, 000}$ written in binary, without leading zeros.

## Output

For each line of input, output one line containing the
signed binary representation of $n$ that has the minimal number of
non-zero digits, using the characters ‘`-`’ for $-1$, ‘`0`’
for $0$ and ‘`+`’ for $+1$. The number should be written
without leading zeros. If there are several minimal
representations, output the one that is lexicographically
smallest (by the ASCII ordering, in which $‘\texttt{+}‘ < ‘\texttt{-}‘ <
‘\texttt{0}‘$).

Sample Input 1 | Sample Output 1 |
---|---|

10000 |
+0000 |

Sample Input 2 | Sample Output 2 |
---|---|

1111 |
+000- |

Sample Input 3 | Sample Output 3 |
---|---|

10111 |
++00- |