Description

N年M月O日CX和ZJS同学在刚学玩整数加减后，就在那里比试谁厉害。比试内容是：将一个正整数N拆成若干个正整数的和。看谁拆的多谁就赢。为了赢得比赛，CX就向你求助一个整数的所有拆分方法。

Input

输入N（ 1 <= N <= 50 ）。

Output

对于N的拆分方法，请以字典序排列（数字越大越排前面）。每一种拆分之间以一个空格分开。

Sample Input

7

Sample Output

7
6 1
5 2
5 1 1
4 3
4 2 1
4 1 1 1
3 3 1
3 2 2
3 2 1 1
3 1 1 1 1
2 2 2 1
2 2 1 1 1
2 1 1 1 1 1
1 1 1 1 1 1 1

HINT

请使用scanf & printf

Source

NBU OJ