题目描述

将n分成若干个大于0的数的和，按照字典序输出所有方案。

输入格式

一个数 n（1 <= n <= 20 ）。

输出格式

按照字典序，输出所有方案。数字之间，用空格划分。

样例数据

input

4

output

1 1 1 1 

1 1 2 

1 2 1 

1 3 

2 1 1 

2 2 

3 1 

4

数据规模与约定

对于100%的数据，1 <= n <= 20。

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$