eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Старовинна задача

Старовинна задача

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Готуючись до чергової олімпіади з програмування, Степан натрапив на одну старовинну задачу, яка його зразу ж зацікавила. У задачі йшлося про те, що у країні, яка називалась Триманія, номінали усіх паперових грошей (триманських фунтів) дорівнювали ступеням трійки, тобто 1, 3, 9, 27 і так далі. Необхідно було визначити, яку мінімальну кількість купюр і яких саме потрібно мати покупцю та продавцю, щоб купити товар вартістю N триманських фунтів та отримати здачу, причому номінали купюр, якими розплачуються та отримують здачу, не повинні повторюватися.

Вхідні дані

Вхідний файл містить одне число – N (вартість товару у фунтах, 0 ≤ N ≤10^18).

Вихідні дані

Один рядок містить номінали купюр у зростаючому порядку через пробіл, які потрібні для купівлі товару покупцю та продавцю, або –1, якщо купити товар за означених умов неможливо.

Приклад

Вхідні дані #1
11
Вихідні дані #1
1 3 9 
Джерело ACM-ICPC Ukraine 2016, Перший етап Україна, 16 квітня 2016 року