这个和硬版本之间的唯一区别是所有 $$$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})$$$,则 $$$x_{i} \neq x_{j}$$$ 对于所有 $$$i \neq 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。
如果答案为“是”,则再输出 $$$n + 1$$$ 行来描述放置。
接下来的 $$$n$$$ 行应包含每个向导的房屋 $$$1 \leq x_{i}, y_{i} \leq n$$$ 的位置。
最后一行的第 $$$i$$$ 个元素应包含巫师的索引,其房屋与第 $$$i$$$ 个巫师的房屋正好 $$$a_{i}$$$ 相距。如果有多个这样的向导,您可以输出任何一个。
如果有多个房屋放置配置,则可以输出任何一个。
示例
输入 #1
4 0 4 2 4
输出 #1
YES 4 4 1 3 2 4 3 1 1 1 1 3
注意
对于示例,第一个向导的房子位于 $$$(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$$$。
所有房屋的视野和距离条件均满足,因此放置位置正确。