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

Вхідні дані

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

Вихідні дані

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