题目描述

大小为$\red 3$的棋盘游戏里有$\red 3$个白色棋子，$\red 3$个黑色棋子，和一个有$\red 7$个格子一线排开的木盒子。$\red 3$个白棋子被放在一头，$\red 3$个黑棋子被放在另一头，中间的格子空着。

初始状态: $\red{WWW\_BBB}$

目标状态: $\red{BBB\_WWW}$

在这个游戏里有两种移动方法是允许的：

你可以把一个棋子移到与它相邻的空格；

你可以把一个棋子跳过一个(仅一个)与它不同色的棋子到达空格。

大小为$\red N$的棋盘游戏包括$\red N$个白棋子，$\red N$个黑棋子，还有有$\red{2N+1}$个格子的木盒子。

这里是$\red{3-}$棋盘游戏的解，包括初始状态，中间状态和目标状态：

WWW BBB
WW WBBB
WWBW BB
WWBWB B
WWB BWB
W BWBWB
 WBWBWB
BW WBWB
BWBW WB
BWBWBW
BWBWB W
BWB BWW
B BWBWW
BB WBWW
BBBW WW
BBB WWW

请编一个程序解大小为$\red N$的棋盘游戏$\red{(1 <= N <= 12)}$。要求用最少的移动步数实现。

输入格式

一个整数$\red N$。

输出格式

输出用移动的棋子在棋盘的位置(位置从左到右依次为$\red 1$, $\red 2$, $\red{...}$, $\red{2N+1}$)表示的变换序列，每个数字之间以空格分隔，每行$\red{20}$个数(除了最后一行)。

输出的解还应当有最小的字典顺序(即如果有多组移动步数最小的解，输出第一个数最小的解；如果还有多组，输出第二个数最小的解；...)。

样例

输入样例

3

输出样例

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