Given $n$ squares of the same size $(n\le 30)$, 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 $n=5$, 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 $n=5$, they are $(5),(4,1),(3,2),(3,1,1),(2,2,1),(2,1,1,1),(1,1,1,1,1).$

Your task is to write a program which, given $n$, outputs all possible arrangements in lexicographical order, where lexicographical order is defined as follows: $(a_1,a_2,\cdots ,a_s)$ precedes $(b_1,b_2,\cdots ,bt)$, if either $a_1>b_1$ or there is an integer $i>1$ such that $a_1=b_1,\cdots ,a_{i-1}=b_{i-1}$ and $a_i>b_i$.

Input

The input consists of a single line containing $n$.

Output

The output should contain all the possible arrangements in lexicographical order, an arrangement a line. An arrangement $(a_1,\cdots ,a_s)$ should be output as a sequence of integers $a_1,\cdots ,a_s$ 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