“Method ringing”（方法鸣钟）常用于教堂钟楼的鸣钟活动，尤其是在英国。假设有 6 口音高不同的钟。我们将音高最高的钟编号为 1，次高的编号为 2，以此类推。当这 6 口钟按某种顺序鸣响一次（每口钟恰好鸣响一次）时，这被称为一个“行”（row）。例如，$1, 2, 3, 4, 5, 6$ 和 $6, 3, 2, 4, 1, 5$ 是两个不同的行。

一个“理想的表演”包含所有可能的行，且每一行恰好出现一次。遗憾的是，物理定律对任意两个连续的行施加了限制；当一口钟被鸣响时，它具有相当大的惯性，而敲钟人改变其周期节奏的能力有限。因此，在两个连续的行之间，每口钟的位置最多只能改变一步。

在图 B.1 中，你可以看到一个非理想表演的模式，其中钟的位置变化最多为一步。

图 B.1：一个遵循钟的惯性的非理想表演。钟 1 的轨迹用蓝线标记，钟 2 的轨迹用棕线标记。

给定钟的数量 $n$，输出一个理想的表演。所有可能的行必须恰好出现一次，且第一行应为 $1, 2, \dots, n$。

输入格式

输入的第一行也是唯一一行包含一个整数 $n$，满足 $1 \le n \le 8$。

输出格式

输出一个理想的行序列，每一行占一行。第一行应包含行 $1, 2, \dots, n$，且任意两个连续行之间的位置变化最多为一步。每一行在输出中应恰好出现一次。

样例

样例输入 1

2

样例输出 1

1 2
2 1