Filip are o balanta dotată cu N=4000 etaloane, numerotate de la 1 la N, ale căror mase exprimate în kilograme G1, G2, ..., GN sunt în ordine valorile termenilor şirului lui Fibonacci.
Astfel G1=1, G2=1, G3=2, ...,Gi=Gi-1+Gi-2, pentru orice 2<i<=N.
Tatăl lui îi pune pe talerul din stânga o nouă jucarie care cântareşte G kg. El îi promite că îi dăruieşte jucăria lui Filip dacă acesta reuşeste să echilibreze balanţa respectând condiţiile următoare:
-primul etalon îl va pune pe talerul din dreapta;
-etalonul următor va fi pus pe talerul din stânga;
-la pasul i etalonul va fi plasat pe talerul diferit celui plasat la pasul i-1;
-la fiecare pas etalonul folosit va cântări mai puţin decât cel folosit la pasul anterior, excepţie făcând etalonul pus la primul pas care poate fi oricare dintre cele 4000.
Cerinţă
Scrieţi un program care determină o modalitate de echilibrare a balanţei după regulile impuse de tatăl său.
Date de intrare
Fişierul de intrare taler.in conţine pe prima linie numărul natural G reprezentând masa jucăriei plasate de tatăl lui Filip pe talerul din stânga.
Date de ieşire
Fişierul de ieşire taler.out va conţine atâtea linii câte greutăţi-etalon au fost folosite pentru echilibrarea balanţei. Pe fiecare linie i este scris un număr natural reprezentând numărul de ordine al etalonului folosit de Filip la pasul i. Dacă există mai multe soluţii se va afişa oricare dintre acestea.
Restricţii
N=4000
1 <=G <= 10800
Exemplu
taler.in
taler.out
Explicaţie
79
11
8
7
4
2
Numerele din fişierul de iesire corespund etaloanelor de mase 89, 21, 13, 3, 2.
Balanţa s-a echilibrat deoarece pe talerul stâng s-au aşezat masele:
79, 21 şi 3.
Pe talerul din dreapta:
89, 13 şi 1