Problem1130--奇偶交错排列

1130: 奇偶交错排列

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 263  Solved: 198
[Submit] [Status] [Web Board] [Creator:]

Description

如果一个1~N的排列P = [A1, A2, ... AN] 满足任意两个相邻整数都是一个奇数另一个偶数,我们就称P是奇偶交错排列。  

给定一个N,请你按字典序输出所有1~N的奇偶交错排列。

Input

多组数据

一个整数N。  1 <= N <= 11

Output

输出若干行,每行一个排列,每个数字后面一个空格。

Sample Input

4

Sample Output

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

Source/Category