题面

小 ∆ 把从 NOI2022 考场上移走的石子拿了一大堆带回了家。 他想在一个 n 行 n 列的二维网格上摆放这些石子，每行、每列都必须 恰好有一个石子，且每个石子距离其所在行对角线穿过的格子的距离互不相 同（其中距离定义为所在列编号之差）。 小 ∆ 摆了半天迟迟摆不出来，请告诉小 ∆ 一种摆法，或告诉他这不可 能。

输入格式

一行一个正整数 n

输出格式

若不可能，输出一行一个字符串 NO 否则第一行输出一个字符串 YES 可以证明满足要求的方案中，恰好使用石子 n 个。 接下来 n 行，每行两个正整数 x, y，代表一个在 x 行 y 列的石子。你 需要不重不漏的输出所有石子，但是输出顺序是任意的，若有多种方案，任 意输出一个即可。

答案检查器

我们提供了答案检查器 checker.cpp 以及编译它所需的头文件 testlib.h， 请将两个文件放在同一个目录下，然后在其中运行 g++ checker.cpp -o checker 来编译。 你可以使用 ./checker <.in> <.out> <.ans> 来运行检查器，其中 <.in> 是输入数据文件，<.out> 是你的程序的输出，<.ans> 是答案文件， 其中只包含一行 YES 或 NO，代表对应的输入数据是否有解。 这个答案检查器和最终评测使用的检查器除了使其兼容评测软件的必 要修改之外完全相同。 3

样例 1

输入 输出 4 YES 1 2 2 4 3 3 4 1

样例解释

摆放方式如下图。 1 2 3 4 4 3 2 1 如图中蓝线所示，这四行中每行石子和所在行对角线所在格子之间的距 离依次为 1, 2, 0, 3，互不相同。

样例 2

输入 输出 3 NO

数据范围与限制

对于所有数据 1 ≤ n ≤ 5 × 105 子任务如下： 1. (30 分) n ≤ 15 2. (35 分) n 是奇数 3. (35 分) n 是偶数