给定一个具有 $N$ 个顶点和 $M$ 条边的凸多面体。这个多面体形状不太美观，因此你想把它切割成另一种形状。

你在三维空间中选择了 $K$ 个平面。一个平面会将一个多面体切割成两个多面体。如果多面体完全位于平面的某一侧，我们定义其中一个多面体为空集（其体积为零）。因此，$K$ 个平面会将多面体切割成 $2^K$ 个多面体。

你需要计算切割后每个多面体的体积。由于原始多面体的顶点数量较多，你需要编写一个程序来计算答案。

输入格式

第一行包含三个正整数 $N, M, K$ ($N\leq M\leq 3\times 10^4, K\leq 3$)，分别表示多面体的顶点数、边数以及平面的数量。

接下来的 $N$ 行，每行包含三个整数 $x_i, y_i, z_i$ ($-10^4\leq x_i,y_i,z_i\leq 10^4$)，表示第 $i$ 个顶点的坐标。顶点编号从 $0$ 到 $N-1$。

接下来的 $M$ 行，每行包含两个整数 $u, v$ ($0\leq u,v < N$)，表示连接第 $u$ 个顶点和第 $v$ 个顶点的一条边。

接下来的 $K$ 行，每行包含四个整数 $a, b, c, d$ ($-10^9\leq a,b,c,d\leq 10^9$)，表示一个方程为 $ax+by+cz=d$ 的平面。

输出格式

输出 $2^K$ 个实数，每行一个，表示切割后每个多面体的体积。这些数字必须按非递减顺序排列。

如果你的答案与标准答案的相对误差或绝对误差不超过 $10^{-6}$，则视为正确。

样例

样例输入 1

8 12 1
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0 1
1 3
3 2
2 0
4 5
5 7
7 6
6 4
0 4
1 5
2 6
3 7
3 0 0 1

样例输出 1

0.333333333
0.666666667

样例输入 2

4 6 1
0 0 0
0 0 3
0 2 0
1 0 0
0 1
0 2
0 3
1 2
1 3
2 3
1 1 1 0

样例输出 2

0.000000000
1.000000000