“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.

-----Input-----
The input consists of a single line containing a positive integer $n < 2^{100000}$ 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}‘$).

-----Examples-----
Sample Input 1:
10000
Sample Output 1:
+0000

Sample Input 2:
1111
Sample Output 2:
+000-

Source: kattis | Difficulty: HARD


Solutions: