== include(page="template/taskheader" task_id="fibo") ==
Rareș este colecționar de cochilii de melci și de scoici. A făcut o cerecetare referitoare la forma acestora, și a descoperit că o cochilie de Nautilus respectă spirala construită pe baza șirului lui Fibonacci.
Termenii șirulului Fibonacci se obțin astfel: primul termen este 0, al doilea termen este 1, iar fiecare dintre următorii termeni se obține ca sumă a celorlalți doi termeni care-l preced. Șirul rezultat este: 0, 1, 0+1=1, 1+1=2, 2+1=3, 3+2=5, 5+3=8, 8+5=13 , etc.
Reprezentând geometric șirul, alegem două termeni (13 și 8) si formăm un dreptunghi. În interiorul acestui dreptunghi, fiecare termen din șirul Fibonacci mai mic ca 13 formează latura unui pătrat. Dacă trasăm un fel de diagonală curbă pornind de la 1 spre 8 obținem o spirală care poate continua, după aceeași regulă, cu un patrat de 13, rezultând valoarea 21 (8+13=21).
Termenii șirulului Fibonacci se obțin astfel: primul termen este [$0$], al doilea termen este [$1$], iar fiecare dintre următorii termeni se obține ca sumă a celorlalți doi termeni care-l preced. Șirul rezultat este: $0, 1, 0+1=1, 1+1=2, 2+1=3, 3+2=5, 5+3=8, 8+5=13,$ etc.
Reprezentând geometric șirul, alegem două termeni ( $13$ și [$8$]) si formăm un dreptunghi. În interiorul acestui dreptunghi, fiecare termen din șirul Fibonacci mai mic ca $13$ formează latura unui pătrat. Dacă trasăm un fel de diagonală curbă pornind de la $1$ spre $8$ obținem o spirală care poate continua, după aceeași regulă, cu un patrat de [$13$], rezultând valoarea $21 (8+13=21)$.
Această descoperire l-a facut curios pe Rareș, care a dorit să afle mai multe despre propietățile misterioase ale acestui șir. Astfel, a aflat că orice număr natural se poate descompune ca o sumă de cel puțin doi termeni nenuli distincți ai șirului Fibonacci; de exemplu, 12=8+3+1; 8=3+5.
Această descoperire l-a facut curios pe Rareș, care a dorit să afle mai multe despre propietățile misterioase ale acestui șir. Astfel, a aflat că orice număr natural se poate descompune ca o sumă de cel puțin doi termeni nenuli distincți ai șirului Fibonacci; de exemplu, $12=8+3+1; 8=3+5$.
h2. Cerinta
Scrieți un program care să citească un număr natural n și un șir x de n numere naturale x1,x2,...,xn, și care să determine descompunerea fiecărui număr din șirul citit ca o sumă de un număr minim (cel puțin doi) de termeni nenuli distincți ai șirului Fibonacci.
Scrieți un program care să citească un număr natural $n$ și un șir $x$ de $n$ numere naturale $x1, x2, ..., xn$, și care să determine descompunerea fiecărui număr din șirul citit ca o sumă de un număr minim (cel puțin doi) de termeni nenuli distincți ai șirului Fibonacci.
h2. Date de intrare
Fișierul $fibo.in$ conține pe prima linie numărul natural n, iar următoarea linie conține cele n numere naturale x1,x2,...,xn, separate prin câte un spațiu.
Fișierul $fibo.in$ conține pe prima linie numărul natural [$n$], iar următoarea linie conține cele n numere naturale $x1, x2, ..., xn$, separate prin câte un spațiu.
h2. Date de ieșire
Fișierul $fibo.out$ va conține n linii, câte una pentru fiecare număr din șirul x:
− prima linie va conține, în ordinea descrescătoare a valorilor, separate prin câte un spațiu, numerele naturale din descompunerea numărului x1 ca o sumă de un număr minim (cel puțin doi) de termeni nenuli distincți ai șirului Fibonacci;
− a doua linie va conține, în ordinea descrescătoare a valorilor, separate prin câte un spațiu, numerele naturale din descompunerea numărului x2 ca o sumă de un număr minim (cel puțin doi) de termeni nenuli distincți ai șirului Fibonacci.
Fișierul $fibo.out$ va conține n linii, câte una pentru fiecare număr din șirul [$x$]:
* prima linie va conține, în ordinea descrescătoare a valorilor, separate prin câte un spațiu, numerele naturale din descompunerea numărului $x1$ ca o sumă de un număr minim (cel puțin doi) de termeni nenuli distincți ai șirului Fibonacci;
* a doua linie va conține, în ordinea descrescătoare a valorilor, separate prin câte un spațiu, numerele naturale din descompunerea numărului $x2$ ca o sumă de un număr minim (cel puțin doi) de termeni nenuli distincți ai șirului Fibonacci.
...............
− a n-a linie va conține, în ordinea descrescătoare a valorilor, separate prin câte un spațiu, numerele naturale din descompunerea numărului xn ca o sumă de un număr minim (cel puțin doi) de termeni nenuli distincți ai șirului Fibonacci.
* a [$n$]-a linie va conține, în ordinea descrescătoare a valorilor, separate prin câte un spațiu, numerele naturale din descompunerea numărului $xn$ ca o sumă de un număr minim (cel puțin doi) de termeni nenuli distincți ai șirului Fibonacci.
h2. Restricții
* $1≤ n ≤ 100$; n număr natural
* $3≤ x1, x2,..., xn ≤ 2 000 000$; x1,x2,...,xn sunt numere naturale
* $1 ≤ n ≤ 100; n este număr natural$
* $3 ≤ x1, x2,..., xn ≤ 2 000 000; x1, x2, ..., xn sunt numere naturale$
h2. Exemplu
