题目描述

$Eva$ 有一个天平，配备了 $20$ 个砝码。这些砝码的重量分别为 $1, 3, 9, 27, ..., 3^{19}$。$Eva$ 断言，她有办法称量重量为 $1$ 到 $(3^{20}-1)/2$ 的任意整数的物体。假设 $Eva$ 已将一个在此范围内的物体放在天平的左托盘上，你的任务是将合适的砝码放置在正确的托盘上，以完成称量。

输入

第一行是整数 $T$（$1 \leq T \leq 20$），表示测试用例的数量。接下来的 $T$ 行每行包含一个整数 $W$（$1 \leq W \leq (3^{20}-1)/2$），表示物体的重量。

输出

对于每个测试用例，输出一行，显示左托盘和右托盘上的砝码重量。用空格分隔左托盘和右托盘。同一托盘上的砝码按升序排列，每两个砝码之间用逗号分隔。如果托盘上没有砝码，输出 "$empty$"。

输入数据 1

3
9
5
20

输出数据 1

empty 9
1,3 9
1,9 3,27

来源

POJ 月赛 -- 2004.07.18