[Baltic2004]SCALES

给定一个重量为正整数 $M$ 的物体。对于每个非负整数 $i$，都有且仅有一个重量为 $3^i$ 的砝码，即砝码重量依次为 $1,3,9,27,\ldots$。

将物体放在天平左盘，并在天平两侧各放置有限个砝码，使天平达到平衡。

输入格式

输入一个十进制整数 $M$。

输出格式

输出两行。

第一行描述与物体一同放在左盘的砝码，第二行描述放在右盘的砝码。

每行先输出该盘中的砝码数量 $N$，随后按照重量严格递增的顺序输出 $N$ 个砝码的重量。若该盘不放置任何砝码，则该行只输出 $0$。

样例输入

42

样例输出

3 3 9 27
1 81

数据范围

• $1\le M\le 10^{100}$。

来源与许可

本题为 Baltic 2004 试题「SCALES」，题面与测试数据整理自 BZOJ。

样例 1

输入

42

输出

3 3 9 27
1 81