同学们在军训的时候被强制要求走方阵。军训中的方阵训练，就像是在学校里学团队合作和纪律的大游戏。它的几个关键点是：

1.学会听话：在方阵里，大家要听从指挥，统一动作，这能培养你的纪律性和执行力。

2.身体锻炼：走方阵时，你要保持队形，做整齐的动作，这能增强身体素质，让你更健康。

3.团队精神：每个人都是方阵的一部分，你和小伙伴要一起努力，保持步伐一致，这能增强团队合作和集体荣誉感。

4.心理磨炼：长时间的训练会有点累，但坚持下来，你的意志力和耐力都会变强。

5.成果展示：最后的方阵表演，是你们团队努力的展示，也是军训成果的展现，非常有成就感。

题目描述

输入一个n，一共会有n！个同学组成方阵。每个同学都有一个编号(1~n)，每一行都有n名同学，一行内同学的编号不会重复，就像(1,2,3……n)这样排列。并且方阵中的每一行与每一行都不一样。每行n个同学，所有行的排列方式依次作为一行组成了这个方阵。请你写一个程序，输出这个方阵。

输入

一个整数 n。1≤n≤9。

输出

按照从小到大的顺序输出所有的，每行 1个。

首先，同一行相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

样例

3

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

关于字典序：

1.从最高位开始比较：首先比较两个数字的最高位，较大的数字在字典序中排名靠前。

2.相同高位继续比较低位：如果最高位相同，则继续比较下一位，直到找到不同的数字或者到达数字的末位。

3.数字长度不一致时的处理：如果两个数字长度不一致，较短的数字在字典序中排名靠前。

数据范围

每个测试用例时间限制1s，内存限制256MB。