Пешо е отличник по математика в СМГ и много обича бира. Един ден отишъл с приятелите си в селската кръчма и както си пиели бира му хрумнала страшна идея. Макар че вече бил почти в нетрезво състояние, все пак успял с грозния си почерк да разпише на една салфетка нова революционна бройна система. След това, за да я изпробва, представил няколко числа в неговата фибоначиева бройна система.
Вече Пешо се е напил брутално и ви моли да му помогнете като напишете програмата FibPrez, която по зададено число N определя кои числа на Фибоначи го съставят.
Цялата философия е следната:
- Всяко число бива представено като сбор от числа на Фибоначи
- Всички числа, които го съставят са различни и са със възможно най-малък брой.
Ето как биха изглеждали няколко числа във фибоначиевата бройна система:
| N | Представяне |
|---|---|
| 110 | 89 + 21 |
| 54 | 34 + 13 + 5 + 2 |
| 26 | 21 + 5 |
- На първия ред от конзолата се въвежда N - цяло число в интервала [1...1000].
- На конзолата се принтират всички събираеми, участващи във фибоначиевото представяне на N. Поредицата е подредена в низходящ ред и всяко число от нея е на отделен ред.
- 1 <= N <= 1000
- Входът винаги е коректен и в оказания формат.
| Вход | Изход |
|---|---|
| 110 | 89 21 |
| 54 | 34 13 5 2 |
| 26 | 21 5 |