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 · 3³ + 0 · 3² + 1 · 3¹ + 2 · 3⁰ = 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¹⁸.

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.