CF1970B1.Exact Neighbours (Easy)

本题与难度更高的版本唯一的区别在于所有 $a_{i}$ 都是偶数。

在食死徒最近对霍格沃茨城堡的袭击之后，凤凰社决定在霍格莫德村驻扎 $n$ 名成员。房屋将建在一块风景如画的 $n\times n$ 正方形场地上。每位巫师将拥有属于自己的房屋，并且每间房屋都属于某位巫师。每间房屋占据一个格子。

然而，正如你所知，巫师们非常迷信。在周末，每位巫师 $i$ 都希望拜访距离自己房屋恰好 $a_{i}$ 的房屋（$0 \leq a_{i} \leq n$）。村庄的道路是水平和垂直修建的，因此在 $n\times n$ 场地上，点 $(x_{i}, y_{i})$ 与 $(x_{j}, y_{j})$ 之间的距离为 $|x_{i} - x_{j}| + |y_{i} - y_{j}|$。巫师们彼此信任，因此一位巫师可以在另一位巫师不在时拜访其房屋。房屋足够大，能够让所有 $n$ 位巫师同时拜访任意一间房屋。

除此之外，每位巫师都必须能够看到北方的霍格沃茨城堡和南方的禁林，因此不能有其他巫师的房屋阻挡视线。换句话说，在 $n\times n$ 场地的每一列中，最多只能有一间房屋。即如果第 $i$ 间房屋的坐标为 $(x_{i}, y_{i})$，那么对于所有 $i \neq j$，都有 $x_{i} \neq x_{j}$。

凤凰社尚不确定是否能够安排 $n$ 间房屋，使得所有 $n$ 位巫师的拜访和视线要求都能满足，因此他们请求你帮忙设计这样的方案。

如果存在一种合法的房屋安排方式，使得对于第 $i$ 位巫师，存在一间房屋距离其房屋恰好为 $a_{i}$，且第 $i$ 位巫师的房屋是其所在列唯一的房屋，则输出 YES，并输出每位巫师的房屋位置以及每位巫师周末应拜访哪位巫师的房屋。

如果不存在合法的安排方式，则输出 NO。

第一行包含一个整数 $n$（$2 \leq n \leq 2\cdot 10^{5}$），表示要建造的房屋数量。

第二行包含 $n$ 个整数 $a_{1}, \ldots, a_{n}$（$0 \leq a_{i} \leq n$）。所有 $a_{i}$ 都是偶数。

如果存在一种合法的安排方式，第一行输出 YES；否则输出 NO。

如果答案为 YES，接下来输出 $n+1$ 行描述房屋的安排。

接下来的 $n$ 行，每行包含两个整数，表示每位巫师的房屋坐标 $1 \leq x_{i}, y_{i} \leq n$。

最后一行包含 $n$ 个整数，第 $i$ 个数表示第 $i$ 位巫师在周末应拜访哪位巫师的房屋，要求该房屋与其房屋的距离恰好为 $a_{i}$。如果有多种选择，可以输出任意一种。

如果存在多种房屋安排方案，可以输出任意一种。

对于样例，第一位巫师的房屋位于 $(4, 4)$，第二位位于 $(1, 3)$，第三位位于 $(2, 4)$，第四位位于 $(3, 1)$。

第一位巫师的房屋到自己的房屋的距离为 $|4 - 4| + |4 - 4| = 0$。

第二位巫师的房屋到第一位巫师的房屋的距离为 $|1 - 4| + |3 - 4| = 4$。

第三位巫师的房屋到第一位巫师的房屋的距离为 $|2 - 4| + |4 - 4| = 2$。

第四位巫师的房屋到第三位巫师的房屋的距离为 $|3 - 2| + |1 - 4| = 4$。

所有房屋的视线和距离条件都满足，因此该安排是正确的。

由 ChatGPT 4.1 翻译