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

\[ (1, 0, 0, -1, -1) = 2^4 - 2^1 - 2^0. \]

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.


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


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
Sample Input 2 Sample Output 2
Sample Input 3 Sample Output 3