说明

按字典序从小到大输出$1\sim n$的所有排列$p_1, p_2, \dots, p_n$，并且要求任意两个相邻元素$p_i, p_{i+1}$，满足$p_{i+1} \neq p_i+1$

输入格式

一行一个整数，表示$n$

输出格式

若干行，每行$n$个整数，表示满足条件的排列

样例

3

1 3 2
2 1 3
3 2 1

数据范围

$n<10$