描述

周幽王从诸侯那得到了一匹象，此时有一台可以称\(10^9\)的天平，可惜时间仓促，这台天平没有游标，只有几块\(1g、3g、9g、27g、…、6561g…\)的石头，每块石头只有一个，大象放在天平的左侧，而石头允许放在天平的左右两侧。已知一个大象的质量\(N\)，问如何称重？

格式

输入格式

一个整数\(N\)。

输出格式

输出有两行：
第一行为放在天平左侧的每块石头重量，当天平左侧不放石头时输出 \(0\)；
第二行为放在天平右侧的每块石头重量。
输出时每块石头重量按从小到大的顺序。

样例1

输入样例1

7

输出样例1

3
1 9

限制

\(100\)%的数据，\(N≤10^9\)。

来源

地址：\(vijos\)，芜湖\(OI\)团队
作者：黑暗路西法\(08\)
模拟赛\(T3\)