Калькулятор Ильи выполняет два действия: умножает текущее число на 3 и прибавляет к нему 1. На калькуляторе сейчас число 1. Помогите Илье определить наименьшую последовательность действий, после которой он получит число n.
Одно число n (1 ≤ n ≤ 10^9
).
Выведите в одной строке искомую последовательность действий как показано в примере. Выводите 1, если добавляете единицу. Выводите 3, если умножаете на три.
В первом примере числа на экране калькулятора могут меняться соедуюшим образом:
1 → 2 → 6 → 7 → 8 → 24 → 25 → 26
Можно убедиться, что это самый короткий путь получить число 26.