Submit  All submissions  Best solutions  Back to list 
WEIGHING  Weighing 
Wersja polska  English version 
You have a doublepan balance, some object and a collection of weights. Mass of the weight is always a power of 3 (so: 1, 3, 9, 27, 81...). For each integer k>=0 there is only one weight with mass 3^{k}. The object was put on the left balance pan. Your task is to put some weights on the left and right balance pans in order to make it balanced.
Input
The first line of the standard input contains one integer t (t<101) which is number of test cases.
In each of the next t lines there is one number n (n<=10^{9}) which is the weight of the object.
Output
For each test output consists of three lines. In the first line print number of weights (number x) and then print x numbers which you have to put on the left balance pan in ascending order. The second line should involve information about the right balance pan in the same format. Third line is a blank one.
Example
Input:
2
50
156
Output:
3 1 3 27
1 81
2 9 81
2 3 243
Added by:  Piotr Kąkol 
Date:  20100502 
Time limit:  2.197s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC SCM qobi VB.NET 
hide comments
20120417 23:18:32 Hallvard Norheim Bø
Looks like java is back on track now :) 

20120329 01:18:22 Piotr KÄ…kol
The right person has been informed. ; but for example ranking on polish SPOJ is off and won't be fixed in few weeks (sic!). So I wouldn't be optimistic. 

20120326 14:30:55 Hallvard Norheim Bø
Piotr: looks like spoj is broken after the upgrades. Can't get my java solution to even compile. On ideone.com it worked with "class Main{...", but even that won't work here :( 

20110826 12:09:07 HWK
@hallvabo: It's your turn. ;) 

20100504 22:02:39 Piotr KÄ…kol
Corrected. Thank You for Your remarks. :) 

20100504 00:50:40 Jargon
You should clarify that 1) n = weight of object, and 2) the first line of output is what you must put on the left pan, and the second line of output is what you must put on the right pan. Last edit: 20100504 00:51:28 