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 року