幻想の地下大線路網

题号：NC288099
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
Special Judge, 64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 某日，幻想乡著名大蜈蚣——姬虫百百世，盯着手中的《地下世界地图》陷入沉思。由于年代久远，地下世界城市之间的道路经历了多次改道，早已和地图不符，这严重影响了她挖掘龙珠的效率。“也许，是时候开辟一条新干线的也说不定呢”，不禁这样想到。作为一个行动派，百百世仅花了 $0.623532$ 秒就决定了新干线的名字——“幻想地下大轨道网”，并开始着手规划线路。
$\hspace{15pt}$ 但还没过多久，百百世就遇到了十分棘手的问题。一方面，她希望自己建立的道路两两之间完全不同；另一方面，作为噬龙者的她却不善于数学计算。于是，她拿着《地下世界地图》来找你帮忙。

$\hspace{15pt}$ 地下世界可以抽象为一个二维平面，分布着 $n$ 行 $n$ 列一共 $n^2$ 个城市，每一个城市坐落在互不相同的坐标 $(i,j)$ 上（其中 $1 ≤ i ≤ n$ ， $1 ≤ j ≤ n$ ，即布满一个 $n \times n$ 的方阵）。城市可以抽象成平面上的点。百百世希望用一条线路把所有城市串联起来，即你需要构造一条满足以下条件的折线：
$\hspace{23pt}\bullet\,$ 折线共由 $n \times n - 1$ 条线段首尾相连形成，并经过所有的 $n \times n$ 个点。
$\hspace{23pt}\bullet\,$ 每一条折线段仅将首尾的点联系起来。如果线段与除首尾之外的其他点重合，不会视为经过该点（不许中途下车！）。
$\hspace{23pt}\bullet\,$ 折线上，线段的斜率均两两不同。这里斜率定义如下：假设折线段连接了 $( x_1, y_1 )$ 和 $( x_2, y_2 )$ ，则斜率为 $\tfrac{y_2 - y_1}{x_2 - x_1}$ 。特别的，当 $x_2 = x_1$ 时，斜率为 $+\infty$ 。
$\hspace{15pt}$ 请你判断，这样的折线是否存在。如果存在请输出一种可行的方案。一个可行的方案由 $n^2$ 行组成，第 $i$ 行输出两个整数 $x_i, y_i$ ，表示第 $i$ 条折线段连接点 $(x_i, y_i)$ 和 $(x_{i+1}, y_{i+1})$ 。

输入描述:

在一行上输入一个正整数  表示地下世界的城市数量。

输出描述:

如果不存在这样的折线，直接输出 。否则，请参考下方的格式输出。
第一行输出 。
此后  行，第  行输出两个整数 ，代表折线经过第  个点的坐标。你应该首先输出起点，然后按顺序输出折线经过的点，最后输出终点。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

示例1

输入

复制

输出

复制

说明

在这个样例中，其中一个合法的构造方案如下图所示，在这个方案中，第一段线段的斜率为 ，第二段线段的斜率为 ，第三段线段的斜率为 。

示例2

输入

复制

输出

复制

说明

在这个样例中，其中一个合法的构造方案如下图所示。

备注:

请注意本题特别的时间限制。