Ujan 终于清理了他的房子,现在想要装饰室内。他决定铺一块漂亮的地毯,真正将客房联系在一起。
他对由多边形块组成的地毯感兴趣,这样块的每一侧要么是另一个(不同)块的一侧,要么是整个地毯的外侧。换句话说,地毯可以表示为平面图,其中每个面片对应于图的一个面,每个面是一个简单的多边形。地毯的周长是外侧的数量。
Ujan 认为,如果地毯由 $$$f$$$ 块组成,其中第 $$$i$$$ 块恰好具有 $$$a_i$$$ 边,且周长尽可能最小,则该地毯是美丽的。找到此类地毯的示例,以便 Ujan 可以订购!
输入
输入的第一行包含一个整数 $$$f$$$ ($$$1 \leq f \leq 10^5$$$),即地毯中的块数。
下一行包含 $$$f$$$ 整数 $$$a_1, \ldots, a_f$$$ ($$$3 \leq a_i \leq 3\cdot 10^5$$$),即面片的边数。面片 $$$a_1 + \ldots + a_f$$$ 的边总数不超过 $$$3\cdot10^5$$$。
输出
将地毯的描述输出为图表。
首先,输出一个整数 $$$n$$$ ($$$3 \leq n \leq 3 \cdot 10^5$$$),即图中的顶点总数(顶点的编号必须从 $$$1$$$ 到 $$$n$$$)。
然后输出包含面部描述的 $$$f$$$ 行。第 $$$i$$$ 行应描述第 $$$i$$$ 面并包含 $$$a_i$$$ 不同的整数 $$$v_{i,1}, \ldots, v_{i,a_i}$$$ ($$$1 \leq v_{i,j} \leq n$$$),这意味着顶点 $$$v_{i,j}$$$ 和$$$v_{i,(j \bmod{a_i})+1}$$$ 通过任何 $$$1 \leq j \leq a_i$$$ 的边连接。
该图应该是平面的并且满足问题陈述中描述的限制。它的周长应该是尽可能最小的。图中不应有双边或自环。该图应该是连接的。请注意,解决方案总是存在的;如果有多个解,输出任意一个。
示例
输入 #1
2 3 3
输出 #1
4 2 1 4 1 2 3
输入 #2
3 5 3 5
输出 #2
6 1 2 3 4 5 4 5 6 1 3 4 6 5
注意
在第一个示例中,两个三角形面通过一条边连接,从而得到最小周长 $$$4$$$。
该图显示了第二个示例的一种可能配置。本例中的最小周长为 $$$3$$$。