Here, we consider the base three representation of the natural numbers.
For example, 59 is represented as 2012,
because 2 · 3^{3} + 0 · 3^{2} + 1 · 3^{1} + 2 · 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.

Public test cases

**Input**

59 1 4 12 9 1000000000 999999999999998378 1000000000000000000

**Output**

59 : 2120 1 : 1 4 : no 12 : 101 9 : no 1000000000 : no 999999999999998378 : no 1000000000000000000 : 21212121212120202020202020202010101010

Information

- Author
- Salvador Roura
- Language
- English
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++