Cerința

Se dă un număr natural n. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe n ca sumă de termeni strict crescători din șirul lui Fibonacci.
Șirul Fibonacci este definit astfel: f1=1 , f2=1 , fn=fn-1+fn-2 , dacă n>2.

Date de intrare

Fișierul de intrare descfib.in conține pe prima linie numărul n.

Date de ieșire

Fişierul de ieşire descfib.out va conţine pe pe fiecare linie câte un şir de numere din șirul lui Fibonacci, ordonate strict crescător, separate prin câte un spaţiu. Suma numerelor din fiecare şir este n. Şirurile vor fi afişate în ordine lexicografică.

Restricții și precizări

• 1 ≤ n ≤ 300000

Exemplu:

descfib.in

24

descfib.out

1 2 3 5 13 
1 2 8 13 
1 2 21 
3 8 13 
3 21