题目描述

输入 n，输出将 n 拆分成若干正整数和的所有方案，即 n=S 1 +S 2 +…+S k 的形式，且 S 1 ≤S 2 ≤…≤S k ，n≤20，请按照字典序输出。

输入格式

一行一个整数 N。

输出格式

所有拆分方案，具体格式参见输出样例。

样例数据

input

4

output

1 1 1 1
1 1 2
1 3
2 2
4

数据规模与约定

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

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