eolymp
Задачи

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

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

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

Вхідні дані

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

Вихідні дані

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

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
11
Выходные данные #1
1 3 9 
Источник ACM-ICPC Ukraine 2016, Перший етап Україна, 16 квітня 2016 року