Given ~n~ squares of the same size ~(n \le 30)~, arrange them on a 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, as is shown below:

■
■  ■
■  ■   ■   ■
■  ■   ■■  ■    ■■   ■
■  ■■  ■■  ■■■  ■■■  ■■■■  ■■■■■

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 $$\displaystyle (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, \dots, a_s)~ precedes ~(b_1, b_2, \dots, b_t)~, if either ~a_1 > b_1~ or there is an integer ~i > 1~ such that ~a_1 = b_1, \dots, 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, \dots, a_s)~ should be output as a sequence of integers ~a_1, \dots, 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