1034: 能量项链

Memory Limit:128 MB Time Limit:4.000 S
Judge Style:Text Compare Creator:
Submit:167 Solved:35

Description

质数总是蕴含着无穷的能量。Lancer在使用了辅助配件改装的武器之后,轻松地取得了战斗的胜利。

他对于项链有着谜一般的执着,在感受到了质数特征值配件改装后的武器所产生的巨大能量之后,他决定请工匠为他打造一款由质数特征值组成的能量项链。

现在已知Lancer有N个魔法石,其能量值分别为1、2、3、…、N。众所周知,项链是一个环形(头尾相连)物品,Lancer想要用这N块魔法石打造一款项链,满足:对于项链上任意一块魔法石,它的能量值与它相邻的两块魔法石之和为一个质数。

现在Lancer想要知道如何设计魔法石在项链上的摆放次序,才能够满足他苛刻的条件呢?

(提示:由于项链是环形,因此我们规定输出的方案第一个数字必须是1,而且必须按照按照字典序从小到大输出,避免DFS全排列导致的输出方案重复。)

例如,当N=6时,下图是一个可行的方案:




即1 4 3 2 5 6

Input

输入文件名为 necklace.in
        输入共1行:第一行为1个正整数N,代表Lancer有N个魔法石

Output

输出文件名为 necklace.out
        输出有若干行,每一行有N个正整数,以空格分隔,表示方案

若无解,则输出"No"。

Sample Input Copy

4

Sample Output Copy

1 2 3 4
1 4 3 2

HINT



注意,若N=3,则你应该输出No.

【数据范围】

       对于100%的数据 2 N 18