Svarstyklės

Pradinių duomenų failas:

svarstykles.in  

Rezultatų failas:

svarstykles.out  

Laiko apribojimas:

2 s.  

Atminties apribojimas:

32 Mb.  

Užduotis

Duotos svirtinės svarstyklės, svarsčių rinkinys bei daiktas. Svarsčių svoriai lygūs 1, 3, 9, 27, 81 … t. y. kiekvieno svarsčio svoris lygus 3 laipsniui ir kiekvienam sveikajam skaičiui k >= 0 yra lygiai vienas svarstis, sveriantis \(3^{k}\). Daikto svoris lygus m, čia m – teigiamas sveikasis skaičius. Daiktas padedamas ant kairiosios svarstyklių lėkštės ir reikia taip sudėlioti svarsčius ant vienos ar abiejų lėkščių, kad svarstyklės būtų pusiausvyroje.

Parašykite programą, kuri, nustatytų, kurie svarsčiai turi būti padėti ant kairiosios ir kurie ant dešiniosios svarstyklių lėkštės.

Pradiniai duomenys

Pirmoje pradinių duomenų bylos eilutėje įrašytas vienas sveikasis skaičius m (1 <= m<= \(10^{100}\)).

Rezultatai

Rezultatų bylą turi sudaryti dvi eilutės.

Pirmoje eilutėje turi būti įrašyta informacija apie kairėje svarstyklių lėkštelėje padėtus svarsčius. Pirmasis eilutės skaičius turi būti lygus ant kairiosios svarstyklių lėkštelės padėtą svarsčių skaičiui (neneigiamas sveikasis skaičius). Toliau eilutėje didėjimo tvarka turi būti įrašyti svarsčių svoriai. Skaičiai atskiriami vienu tarpu.

Antroje eilutėje analogišku formatu turi būti įrašyta informacija apie dešinėje svarstyklių lėkštelėje padėtus svarsčius.

Pavyzdžiai

42

3 3 9 27
1 81

30

0
2 3 27