Maximum number in base three P51176

Here, we consider the base three representation of the natural numbers. For example, 59 is represented as 2012, because $2 \cdot 3^3 + 0 \cdot 3^2 + 1 \cdot 3^1 + 2 \cdot 3^0 = 59$. Note that all digits are between 0 and 2, and that we have no zeros on the left.

Write a program to print the result of rearranging the base three digits of each given number, so that the result is the maximum possible, with an additional condition: we cannot have two equal consecutive digits.

Input

Input consists of several $n$, all between 1 and $10^{18}$.

Output

For every given $n$, print its base three digit rearrangement without equal adjacent digits that produces the maximum possible result. If no reordering is possible, tell so.