该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

曹操得了一头大象，想知道它有多重。满朝文武束手无策，年幼的曹冲却想出了妙计：用一条船把大象装上去，在船舷划好吃水线，再往船上推入砝码让吃水线重合，这些砝码总重就等于大象重量。

问题在于，军营里没有任意重量的砝码，只有一套特殊的砝码：重量分别为 1、3、9、27、81、…（3 的幂次方），而每种砝码最多只有一个。大象放在天平的左盘，需要在天平两盘放砝码使天平平衡。请你帮助曹冲找出：哪些砝码应放在左盘、哪些放在右盘。

题目描述

有一架天平和若干砝码，重量分别为 1、3、9、27、…、3^i（每种恰好一个，数量不限但每种至多用一个）。物体放在左盘，重量为 n。求一种放砝码的方案，使天平平衡，即左盘重量 + 左盘砝码总重 = 右盘砝码总重。

• 输入：一行一个整数 n（1 ≤ n ≤ 10^9）
• 输出：两行——第一行为放在左盘的砝码（升序，用空格隔开；没有则输出 0）；第二行为放在右盘的砝码（升序，用空格隔开；没有则输出 0）
• 样例1：2 → 左盘 1，右盘 3（2+1=3）
• 样例2：7 → 左盘 3，右盘 1 9（7+3=1+9）

输入样例

7

输出样例

3
1 9