工匠大師Hill打造出一個精致的天平, 對他的徒弟Oren說：“你幫我做一些砝碼配套，為了方便攜帶，砝碼數(shù)目要盡量少”。

Oren：“好。我將按照2進制的規(guī)則打造，也就是1，2，4，8，16等等，這樣在稱量同等重量下使用的砝碼數(shù)量最少，只使用7個砝碼就可以稱量1－127的重量。”
Hill：“No, you are wrong”。
Oren：“難道還有更好的方法？2進制是最優(yōu)的，這一點是可以證明的”
Hill：“如果只允許砝碼放在天平的一端，那么你說的是對的，可是并沒有人限制我們可以在天平的兩端放置砝碼。所以可以有更好的方法。如可以設(shè)計砝碼重量為1，3，9，27，81，只用5個砝碼就可以稱量1－121”。
Oren：“原來是3進制，那怎么稱重呢? 如100克重量？”
Hill：“在天平的左端放上重物，再放上砝碼9，右端放砝碼1, 27, 81”。
Oren：“嗯，可這是怎么算出來的呢？”
Hill：“It’s your business”。
現(xiàn)在，作為Oren的朋友，請你設(shè)計一個程序來計算在這種砝碼下應(yīng)如何稱量。

Input:

輸入包括多個整數(shù)，每個數(shù)n占據(jù)一行，代表要稱重的重量。0 < n <= 1000000000。

Output:

對于每個輸入的整數(shù)，計算當此重量放置在天平左端時，應(yīng)如何安排3進制的砝碼，使天平平衡。每個結(jié)果輸出一行，輸出格式如例子所示，每個數(shù)字后面一個空格，如某一側(cè)沒有砝碼，則輸出0，多個砝碼按重量升序排列。

Sample Input:

100
30

Sample Output:

9 left, 1 27 81 right.
0 left, 3 27 right.

----------
題目很經(jīng)典
不要誤解題意，注意n的范圍，
不是搜索。 點下面的加號打開代碼