曹文信息在线OJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5815: 称重

Memory Limit：256 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：72 Solved：1
SubmitSubmit RecordStatisticsWeb BoardShowOff!

Description

忙碌了一整天，小 X 伸了伸懒腰，准备上床休息，每天睡觉前小 X 都要称一下体重，小 X 称重的工具是一架神奇的天平，它的神奇之处在于：首先这是一架纳米天平，非常稀有，是因小 X 研制出了量子计算机后外星首领赠送给他的；其次该天平的精度极其之高，它能够称出的最小单位是纳克，纳克的英文表示为 ng,众所周知 1 克(g)=1,000,000,000 纳克；第三该天平使用的砝码十分奇特，它有一组砝码，每个砝码的质量依次为 1ng、 3ng、 9ng、 27ng、81ng……， 每个砝码的质量都是 3 的幂次(如 3 的 6 次幂表示为 3^6=729)， 且各不相同。 小 X将某些砝码放在天平的左边托盘中，另一些放在右边托盘中，然后他自己站在天平右边的托盘上，天平平衡之后左边的砝码重量减去右边的砝码重量就得到小 X 的重量。 现在小 X 想出个题目来考考你，看你聪明不聪明！
小 X 的问题是给定一个物体的重量，请你设计一个方案把这个物体和一些砝码放在天平上使得天平两端平衡，规定物体必须放在天平的右端。

Input

输入数据仅有一行包含一个正整数 W，表示物体的重量， 重量单位是纳克(ng) 。

Output

输出数据共有两行，分别输出左右两端各个砝码及物体的重量，同一行砝码重量必须从小到大排序后按次序输出，第二行的第一个数必须先输出物体的重量，然后才是各个砝码的重量。相邻两个数之间必须严格用一个空格隔开。
输入数据保证一定有解！如有多组解，输出任意一组即可！

Sample Input Copy 

样例1
67

样例2
22806

样例3
1999

Sample Output Copy 

样例1
1 3 9 81
67 27

样例2
243 729 2187 19683
22806 9 27

样例3
1 81 2187
1999 27 243

HINT

给你一个 67ng 的物体，你可以在天平的左边放上 4 个砝码，重量依次为 1,3,9,81 总重量 94ng， 而右边放一个砝码质量为 27ng，加上物体的重量 67ng，恰好也是 94ng，满足题目要求，此时天平的左右两端平衡。

20%的数据， W<=100。
另外 20%的数据， W<=10000，最多只用到 5 个砝码。
另外 20%的数据， W<=1000000，所有砝码都放在左边。
另外 20%的数据， W<=1000000。
100%的数据， W<=10^15，要用 long long！