题目描述

将n分成若干个大于0的数的和，1 2同 2 1 视作相同的划分。

按照字典序输出所有方案。

输入格式

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

输出格式

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

样例数据

input

4

output

1 1 1 1

1 1 2

1 3

2 2

4

数据规模与约定

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

样例解释

将4划分为4个数， 1 1 1 1

将4划分为3个数， 1 1 2

将4划分为2个数， 1 3，2 2

将4划分为1个数， 4

按照字典序输出。

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

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