Given a natural number N. Consider its partition into natural terms. Two partitions that differ only in the order of the terms will be considered as one, so we can assume that the terms in the partition are ordered in non-increasing order.
Input
A single number N is given. (N ≤ 40)
Imprint
It is necessary to print all partitions of the number N into natural terms in lexicographic order.
Examples
| # |
Input |
Output |
| 1 |
5 |
1 1 1 1 1
2 1 1 1
2 2 1
3 1 1
3 2
4 1
5 |