这是一个星光璀璨的夜晚，DreamGrid 正在数星星。不幸的是，天空中出现了云朵，许多星星被遮挡了。DreamGrid 想走出阴影，找到一个至少能看到一颗星星的地方。他首先想知道阴影的总面积（长度）。

天空中共有 $n$ 颗星星和 $m$ 朵云。形式化地，每颗星星由二维平面上的一个点 $(x_i, y_i)$ ($1 \le i \le n$) 表示。第 $i$ 朵云 ($1 \le i \le m$) 由一条线段 $(u_{i1}, v_{i1}) - (u_{i2}, v_{i2})$ 表示，其中 $(u_{i1}, v_{i1})$ 和 $(u_{i2}, v_{i2})$ 是该线段的两个端点。

对于 $x$ 轴上的一个观察点 $(x, 0)$，如果在此处看不到任何星星，DreamGrid 就认为该点处于阴影中。如果在观察点与星星之间的连线不与任何云朵相交（包括云朵的端点），则称该星星在观察点可见。注意，如果一朵云（包括其端点）穿过了某颗星星，那么这颗星星在任何地方都不可见。

遍历整个 $x$ 轴并计算总阴影面积是一件很累人的事。你能告诉 DreamGrid $x$ 轴上被阴影覆盖的总面积（长度）吗？

输入格式

输入包含多组测试数据。输入的第一行包含一个整数 $T$ ($1 \le T \le 500$)，表示测试数据的组数。

对于每组数据，第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 500$)，分别表示星星和云朵的数量。接下来的 $n$ 行描述星星的位置。第 $i$ 行 ($1 \le i \le n$) 包含两个整数 $x_i$ 和 $y_i$ ($-10^4 \le x_i \le 10^4, 1 \le y_i \le 10^4$)，表示第 $i$ 颗星星的位置。接下来的 $m$ 行描述云朵的位置。第 $i$ 行 ($1 \le i \le m$) 包含四个整数 $u_{i1}, v_{i1}, u_{i2}, v_{i2}$ ($-10^4 \le u_{i1}, u_{i2} \le 10^4, 1 \le v_{i1}, v_{i2} \le 10^4, (u_{i1}, v_{i1}) \neq (u_{i2}, v_{i2})$)，表示第 $i$ 朵云的两个端点坐标。

保证 $\max(n, m) \ge 100$ 的测试数据组数不超过 5 组。请注意，多颗星星可能位于同一位置，云朵之间也可能相交或重叠。

输出格式

对于每组数据，输出一行，包含一个实数，表示 $x$ 轴上阴影的总面积（长度）。如果答案大于 $10^9$，则输出 $-1$。

当且仅当你的答案与标准答案的绝对误差或相对误差不超过 $10^{-4}$ 时，你的答案才会被接受。

样例

输入 1

8
1 2
0 3
-2 1 -1 1
2 1 1 1
1 2
0 3
-2 1 -1 1
1 2 2 1
2 2
10000 100
-10000 100
-10000 50 -3000 50
10000 50 3000 50
2 2
0 3
-1 10
3 2 0 1
0 1 -1 10
1 1
0 2
1 1 3 2
1 1
0 10000
-10000 9999 10000 9999
1 1
0 10000
-9999 9999 9999 9999
1 1
0 10000
-10000 1 9999 2

输出 1

3.0000000000
1.5000000000
8000.0000000000
-1
-1
200000000.0000000000
199980000.0000000000
20002.0003000500

说明

对于第一个样例，阴影的范围是 $[-3, -1.5] \cup [1.5, 3]$。

对于第四个样例，第二颗星星被第二朵云遮挡，因此它在任何地方都不可见。