partition-manager

Problem Statement
You are writing the source code for an open source partition manager. A disk partition of size N KB needs to be divided into one or more partitions. (Size of each partition must be an integer multiple of Just as you finished writing the source code, you found an interesting problem: In how many different ways can the disk be partitioned? Refer wikipedia for more details on integer partitions.

In this question, an integer partition has the following properties:
Let P = <p1, p2, p3, ..., pk> be a partition of N. (1 ≤ k ≤ N)
Then, p1 + p2 + ... + pk = N and p1 ≥ p2 ≥ p3 ≥ ... ≥ pk.
Let P = <p1, p2, p3, ..., pj> and Q = <q1, q2, q3, ..., qk> be two different partitions of N. Then, we say that P > Q, if and only if, p1 = q1, p1 = q1, ..., pi - 1 = qi - 1 and pi > qi for some i ≤ min(j, k).

Now, given the value of N, generate all the partitions of N, in non-increasing order.

You can easily see that the first partition will <N>. and the last partition will be <1, 1, 1, ..., 1> (1 is repeated N times).
Input Format
The only line of the input file contains a positive integer N.

Output Format
The output must contain all the partitions of N in non-increasing order. Output each different partition of N on a separate line. Separate each part of a partition by a space.

Constraints
1 ≤ N ≤ 27

SAMPLE INPUT
8

SAMPLE OUTPUT
8
7 1
6 2
6 1 1
5 3
5 2 1
5 1 1 1
4 4
4 3 1
4 2 2
4 2 1 1
4 1 1 1 1
3 3 2
3 3 1 1
3 2 2 1
3 2 1 1 1
3 1 1 1 1 1
2 2 2 2
2 2 2 1 1
2 2 1 1 1 1
2 1 1 1 1 1 1
1 1 1 1 1 1 1 1

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: