4365: 素数环

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:20 Solved:5

Description

一个大小为N(N<=17)的质数环是由1到N共N个正整数(不重复)组成的一个数环,数环上每两个相邻的数字之和为质数。为了方便描述,规定数环上的第一个数字总是1。如:1 4 3 2 5 6即为一个素数环。1+4、4+3、3+2、2+5、5+6、6+1都是质数。现在要求你求出所有不同的素数环。

Input

输入1行:一个正整数N,表示质数环的大小。

Output

输出多行:每一行描述一个数环,如果有多组解,按照字典序从小到大输出,如果无解则不输出。

Sample Input Copy

6

Sample Output Copy

1 4 3 2 5 6
1 6 5 2 3 4