Description

给定一个正整数\(n\)，请求出所有满足如下两个条件的正整数集合\(x[1],x[2]...x[n]\):
1. \(x[1]+x[2]+...+x[n]=2n\)
2. 不存在一个划分将集合划分成和相等的两部分，也就是说，集合的任意子集和均不为\(n\)。
请按照集合中元素升序排序后字典序从小到大的顺序输出答案，若不存在这样的集合请不要输出任何字符。

Format

Input

每个测试点仅包含一组测试数据。
第一行一个正整数\(n(1 \leq n \leq 1000)\)。

Output

多行，每行代表一个可能的答案序列。
同一个序列内所有数从小到大排序，相邻两个数之间用一个空格隔开，行首尾不要添加多余空格。

Sample 1

Input

3

Output

1 1 4
2 2 2

Limitation

1s, 256MB for each test case.

Source

lyh