Given squares of the same size
, arrange them on an horizontal line in several columns
such that the number of squares in any column should not be less than that of the column on
its immediate right.
For example, if
, then exactly seven arrangements are possible.
Any arrangement can be represented by a sequence of integers, the number of squares in the
columns from left to right. For example, in case ,
they are
Your task is to write a program which, given , outputs all possible arrangements in lexicographical order, where lexicographical order is defined as follows:
precedes
, if either
or there is an integer
such that
and
.
Input
The input consists of a single line containing .
Output
The output should contain all the possible arrangements in
lexicographical order, an arrangement a line. An arrangement
should be output as a sequence of integers
separated by a single space
character between them.
Sample Input
5
Sample Output
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1
Comments