Every change P29230

Write a program such that, for every given natural number $n$, prints all the different ways to obtain $n$ cents with the euro system of coins (1 cent, 2 cents, 5 cents, 10 cents, 20 cents, and 50 cents).

Input

Input consists of a sequence of natural numbers $1 \le n \le 50$.

Output

For every $n$, print all the ways to obtain $n$ cents, each one in a different line. The numbers of each line must appear in nonincreasing order. The solutions for every $n$ must appear in reverse lexicographical order. Print an empty line after the output for each case.

Observation

A simple backtracking program that computes the result for every given $n$ (even if repeated) is fast enough for this problem.