题目描述

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

小 X 的问题是给定一个物体的重量，请你设计一个方案把这个物体和一些砝码放在天平上使得天平两端平衡，规定物体必须放在天平的右端。

输入格式

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

输出格式

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

输入数据保证一定有解！如有多组解，输出任意一组即可！

67

1 3 9 81
67 27

22806

243 729 2187 19683
22806 9 27

1999

1 81 2187
1999 27 243

数据范围

$1 \le W \le 10^{15}$