时间限制：0.25 秒
内存限制：65536 KB
难度估计：CF 2700
判题提示：需要 SPJ / 几何 checker，因为合法划分方案不唯一且允许实数坐标。

题目描述

Quadroland（也可能叫 Triland……）的国王去世了。经过四天——或者三天——的哀悼后，人们公布了他的遗嘱：整个王国需要分成四份或三份，分别留给他的每一个儿子。

王国在平面上可以表示为一个四边形或三角形，并且它的每一条边都对应一个儿子。

完成划分之后，每个儿子得到的领地必须是一个三角形或四边形，并且其中一条边必须与分给他的那条原王国边完全重合。

同时，所有儿子所得到区域的面积必须满足给定比例。

请构造一种满足条件的划分方案。

输入格式

第一行包含整数 $N$，表示儿子数量，也等于王国多边形的边数：

$3\le N\le4$。

接下来 $N$ 行，每行包含两个整数，表示王国各顶点的坐标。

顶点按照顺时针或逆时针顺序给出。保证任意两条相邻边不在同一直线上。

每个坐标的绝对值均不超过 $100$。

最后一行给出要求的面积比例，格式为：

K1:K2:...:KN

其中：

• $K_1$ 对应第 $1$、第 $2$ 个顶点之间的边；
• $K_2$ 对应第 $2$、第 $3$ 个顶点之间的边；
• ……
• $K_N$ 对应第 $N$ 个顶点与第 $1$ 个顶点之间的边。

并且：

$1\le K_i\le100$。

输出格式

输出共 $N$ 行。

第 $1$ 行描述与第 $1$、第 $2$ 个顶点之间的原边对应的区域；第 $2$ 行描述与第 $2$、第 $3$ 个顶点之间的原边对应的区域；依此类推。

每个区域的描述格式为：

M x1 y1 x2 y2 ... xM yM

其中：

• $M$ 为该区域的顶点数，只能是 3 或 4；
• 随后给出该多边形所有顶点的坐标；
• 顶点可以按照顺时针或逆时针顺序输出；
• 与该儿子对应的原王国边的两个端点，必须是这个输出多边形中相邻的两个顶点。

输出坐标允许为实数。如果输出实数，应尽可能多地保留小数位，以保证精度。

如果无法完成满足要求的划分，则只输出一行：

-1

样例 1

3
0 0
10 0
0 10
4:2:4

3 0 0 10 0 4 4
3 10 0 0 10 4 4
3 0 10 0 0 4 4

样例 2

4
0 0
0 30
100 30
100 0
1:3:1:3

3 0 0 0 30 25.0 15.0
4 0 30 100 30 75.0 15.0 25.0 15.0
3 100 30 100 0 75.0 15.0
4 0 0 100 0 75.0 15.0 25.0 15.0

难度说明

当 $N=3$ 时，可以利用面积与重心坐标的线性关系直接构造内部点。

当 $N=4$ 时，还需要兼顾凸四边形与凹四边形，选择合适的内部对角线，并通过沿线段插值控制两侧区域面积，再继续拆分成满足各边面积比例的三角形/四边形。构造正确性和几何边界处理都具有较高难度。