Partition a Natural Number

For any natural number \(n > 1\), it can be partitioned into a sum of natural numbers, each of which is less than \(n\). Given a natural number \(n\), your task is to find all possible partitions of \(n\) into some natural numbers (each less than \(n\)). In every partition the numbers must be arranged in ascending order. Finally, output these partitions, making sure that the sequences are printed in lexicographical order.

inputFormat

The input consists of one line containing a single natural number \(n\) where \(2 \le n \le 40\).

outputFormat

Print each valid partition on a separate line. In each partition, the numbers are separated by a space. Only partitions with at least two numbers (i.e. each addend is less than \(n\)) should be output, and the partitions must be listed in lexicographical order.

sample

2

1 1