“Under The Sea”村庄坐落在一个山谷中。村庄唯一的入口前有一条大河。今年，他们遭遇了百年一遇的洪水。由于政府缺乏防范意识，疏散居民已为时已晚。洪水很快就会流入村庄。

幸运的是，这个村庄有可以阻挡洪水的墙壁和闸门。但我们不能将所有洪水都挡在外面。否则，会有过多的水流过河流，摧毁村庄附近的一座核电站，并给所有人带来不可估量的损失。我们需要以一种可控的方式让一些水流进来。

墙壁和闸门将村庄分隔成许多封闭的区域。如果我们打开所有的闸门，任意两个不同的区域都可以通过闸门恰好经过一条路径到达彼此。明确地说，样例 1 是一个由 1 个区域、2 面墙和 1 个闸门组成的村庄。在下图中，实线是墙壁，虚线是闸门。样例 2 是另一个由 5 个区域、5 面墙和 5 个闸门组成的村庄。给定估计的洪水体积，政府可以决定关闭一些闸门并保持其余闸门开启。让洪水摧毁一些区域，而让其他区域保持安全。图中阴影区域是样例输出中最佳方案里被摧毁的区域。

政府官员请你编写一个程序，帮助他们选择开启哪些闸门。他们给你一份名单，包含了所有居民的居住地以及他们拥有的财产。政府官员希望你找到一种方法来拯救拥有最多总财富的人。你觉得区别对待富人和穷人并不好。所以你想私下做点不同的事情。你将给出一个拯救人数最多的方案。如果存在多个拯救人数相同的方案，那么你选择其中拯救财富总额最多的方案。

样例 1

样例 2

样例 3

输入格式

第一行包含 1 个整数 $Area$ —— 洪水将摧毁的估计面积。

第二行包含 3 个整数 $G, W$ 和 $R$ —— 闸门、墙壁和居民的数量。

接下来 $G$ 行。每行包含 4 个整数 $x_{1_g}, y_{1_g}, x_{2_g}, y_{2_g}$，表示一个闸门的两个端点坐标。

接下来 $W$ 行。每行包含 4 个整数 $x_{1_w}, y_{1_w}, x_{2_w}, y_{2_w}$，表示一面墙的两个端点坐标。

最后有 $R$ 行。每行包含 3 个整数 $x_r, y_r$ 和 $money_r$，表示一位居民的坐标以及他们拥有的财产金额。

输出格式

你应该输出 2 行。

第一行包含 1 个实数和 3 个整数 $area, money, people$ 和 $gate\_n$，它们代表方案的结果。$area$ 是一个保留到小数点后一位的实数，表示被摧毁区域的总面积。$money$ 是受害者拥有的财产总额。$people$ 是受害者的人数。$gate\_n$ 是开启的闸门数量。

第二行包含 $gate\_n$ 个整数，它们是开启的闸门索引，顺序任意。注意闸门的索引从 1 到 $G$。

如果输入中的 $Area$ 大于村庄的总面积，你输出的 $area$ 应该是整个村庄的大小，$money$ 应该是村庄中所有人的财产总额，$people$ 应该是村庄中的所有人。并且你应该开启所有的闸门。

如果输入中的 $Area$ 不超过村庄的总面积，你输出的 $area$ 应该大于或等于 $Area$。

如果存在多个可以拯救相同人数的方案，选择损失财富较少的那个。如果仍然存在多个损失财富相同的方案，选择被摧毁面积较小的那个。如果仍然存在多个摧毁面积相同的方案，任意一个均可。

说明

• $0 < area, G, W, R < 5000$
• $-5000 < x, y < 5000$
• $0 \le money < 5000$
• 村庄边界上恰好有一个闸门。洪水将通过这个闸门流入村庄。在可行的方案中，这个闸门必须开启。
• 所有区域都是简单多边形。它们不自交且没有孔洞。
• 所有的墙壁或闸门互不相交。它们仅在端点处接触。
• 每个端点至少连接两面墙或闸门。不存在悬空的墙壁或闸门。
• 所有居民的位置都位于区域内部。他们不会在村庄之外。并且他们不会正好位于墙壁、闸门或连接点上。

样例

样例输入 1

20
1 2 1
0 0 20 20
20 20 0 20
0 20 0 0
10 15 100

样例输出 1

200.0 100 1 1
1

样例输入 2

100
5 5 5
0 10 10 0
0 0 0 10
0 0 10 0
0 0 -10 0
0 0 -5 5
0 -10 -10 0
-10 0 -5 5
0 10 -5 5
10 0 0 -10
0 0 0 -10
3 3 5
-5 3 1
-3 5 1
-3 -3 1
3 -3 10

样例输出 2

100.0 15 2 2
1 3

样例输入 3

33
3 17 3
-4 4 5 4
-4 3 -3 3
3 -3 4 -3
0 1 0 -1
-4 3 -4 -3
-3 -2 -3 3
-2 2 -2 -1
2 1 2 -2
3 2 3 -3
4 3 4 -3
-3 3 4 3
-2 2 3 2
-2 -1 0 -1
0 1 2 1
-3 -2 2 -2
-4 -3 3 -3
-4 -4 5 -4
-4 -4 -4 -3
-4 3 -4 4
5 -4 5 4
1 0 5
-1 0 1
-1 0 1

样例输出 3

48.0 5 1 2
1 3