Using coin values \(1\), \(5\), \(10\), and \(25\), find the minimum number of coins whose total is exactly \(n\).

Input

One integer \(n\).

The input satisfies:

• \(0 <= n <= 10^9\)

Output

Print four counts for coins 25 10 5 1, followed by the total coin count, all separated by spaces.

Example

Input

6

Output

0 0 1 1 2