给你一个天平、一套砝码和一个物体。砝码的重量为 $1, 3, 9, 27, 81, \dots$，即每个砝码的重量都是 $3$ 的幂，且对于每个整数 $k \ge 0$，恰好有一个重量为 $3^k$ 的砝码。物体的重量为 $m$，其中 $m$ 是一个正整数。你的任务是将物体放在左侧秤盘上，并在一个或两个秤盘上放一些砝码，使天平保持平衡。

编写一个程序：

• 从输入中读取物体的重量 $m$；
• 计算应该在左侧和右侧秤盘上分别放置哪些砝码；
• 输出计算结果。

输入格式

输入包含一个整数 $m$（$1 \le m \le 10^{100}$），表示物体的重量。

输出格式

输出应包含两行。

第一行应包含关于放在左侧秤盘上的砝码的信息。第一个数必须是一个非负整数，表示放在左侧秤盘上的砝码数量，后面依次按升序排列输出这些砝码的重量。数字之间必须用单个空格分隔。

第二行应包含关于放在右侧秤盘上的砝码的信息，格式与第一行相同。

样例

输入样例 1

42

输出样例 1

3 3 9 27
1 81

输入样例 2

30

输出样例 2

0
2 3 27