Partitions into summands

List all partitions of a positive integer $n$ into positive integer summands. The partitions should satisfy the following properties:

• The summands in each partition are arranged in non-increasing order.

• The partitions are listed in lexicographic order.

Input

One single integer $n(1\le n\le 40)$.

Output

Print each partition on a separate line.

Examples