Cash Change

You have an unlimited number of cash notes of the following denominations: 1, 5, 10, 50, 100, 500.

Given a number $N$, determine the minimum number of cash notes required to make the total $N$. For this problem, you will have to print out the values of each cash note in ascending order.

For example, when $N = 1535$, the minimum number of notes required is 7. And to make this total, you need the following cash notes:

5 10 10 10 500 500 500

Input

The input will contain a single integer $N$ ($1 \le N \le 10^4$).

Output

Print the cash note values that in total make $N$ while requiring the minimum number of cash notes.

Sample

1535

5 10 10 10 500 500 500