该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

你来到了森林里的糖果屋，女巫给你出了一道谜题：

她手里有 n 颗糖果，要把它们分成若干份，排成一排送给你。但她有一个古怪的规矩：

每一份的糖果数必须是正整数

相邻两份的糖果数不能一样，不然糖果会融化

女巫说，只有找出所有合法的分糖方案，你才能拿到糖果。请你帮她把所有方案列出来吧！

按字典序从小到大的顺序依次输出所有满足条件的数组。

Format

Input

第一行输入一个整数 $n(1 \leq n \leq 20)$.

Output

按顺序输出所有可能方案。

Samples

3

1 2
2 1
3

Limitation

1s, 1024KiB for each test case.