CF1970B3 Exact Neighbours (Hard)

在最近食死徒对霍格华兹城堡发动了一些袭击之后，凤凰社决定将 $n$ 个成员安置在霍格迈德村。这些房子将坐落在一片风景如画的正方形场地上。每个巫师都有自己的房子，每个房子都属于某个巫师。每栋房子将占据一个正方形的空间。 然而，正如你可能知道的，巫师是非常迷信的。在周末，每个巫师 $i$ 都想参观距离自己房子$a_i$（$0 \leq a_i \leq n$）的房子。 村里的道路是水平和垂直修建的，因此点（$x_i，y_i$）和（$x_j，y_j$）之间的距离在 $n \times n$ 域上是$ |x_{i} - x_{j}| + |y_{i} - y_{j}| $ 。巫师们相互了解和信任，所以当第二个巫师不在时，一个巫师可以去另一个巫师的家。建造的房子将会足够大，所有 $n$ 个巫师都可以同时参观任何房子。 除此之外，每个巫师都必须能看到北边的霍格沃茨城堡和南边的禁林，所以其他巫师的房子不应该挡住视线。就村庄而言，这意味着在 $n \times n$ 域的每一列中，最多可以有一个房子，所以如果第 $i$ 个房子有坐标$（x_i，y_i）$，那么对于所有 $i$ 不等于 $j$ ，都有 $x_i \neq x_j$。 凤凰社还不知道是否有可能以这样的方式放置 $n$ 栋房子，以满足所有 $n$ 位巫师的参观和景观要求，所以他们请求您帮助设计这样的计划。 如果可以有一个正确的位置，其中第 $i$ 个向导的房子离它有 $a_i$ 的距离，而第 $i$ 个巫师的房子是他们列中唯一的房子，输出 $YES$，每个巫师的房子的位置，以及每个巫师周末应该去哪个向导的房子。 如果无法正确放置，则输出 $NO$。

第一行包含 $n$ （$2 \leq n \leq 2 \times 10^5$），即要建造的房屋数量。 第二行包含从 $a_1$ 到 $a_n$ 的n个整数。（$0 \leq a_i \leq n$）

如果存在这样的放置，则在第一行输出 $YES$ ；否则，输出 $NO$ 。 如果答案是 $YES$，则输出 $n+1$ 行描述放置的内容。 接下来的 $n$ 行应该包含每个巫师的房屋 $1 \leq x_i，y_i \leq n$ 的位置。 最后一行的第 $i$ 个元素应该包含巫师的索引，其房屋与第 $i$ 个巫师的房屋正好相距 $a_i$。如果有多个这样的巫师，你可以输出任何一个。 如果有多个房屋放置方式，你可以输出任意一个。

For the sample, the house of the 1st wizard is located at $ (4, 4) $ , of the 2nd at $ (1, 3) $ , of the 3rd at $ (2, 4) $ , of the 4th at $ (3, 1) $ . The distance from the house of the 1st wizard to the house of the 1st wizard is $ |4 - 4| + |4 - 4| = 0 $ . The distance from the house of the 2nd wizard to the house of the 1st wizard is $ |1 - 4| + |3 - 4| = 4 $ . The distance from the house of the 3rd wizard to the house of the 1st wizard is $ |2 - 4| + |4 - 4| = 2 $ . The distance from the house of the 4th wizard to the house of the 3rd wizard is $ |3 - 2| + |1 - 4| = 4 $ . The view and the distance conditions are satisfied for all houses, so the placement is correct.