Ilya's calculator does two things: multiply the current number by 3 and add 1 to it. The calculator now has the number 1. Help Ilya to find the smallest sequence of operations to get the number n.
One integer n (1 ≤ n ≤ 10^9
).
Print in one line the required sequence of operations as shown in the example. Print 1 if you add one. Print 3 if you multiply by three.
In the first example, the numbers on the calculator screen can change in the following way:
1 → 2 → 6 → 7 → 8 → 24 → 25 → 26
You can see that this is the shortest way to get the number 26.