时间限制：1秒　　内存限制：256M

---

【问题描述】

　　巴黎哞运会即将来临，Farmer John 正在对他的奶牛队进行射箭训练！他在二维坐标平面上设置了以下练习。

　　有 \(N（1≤N≤4⋅10^4）\)个四边与坐标轴平行的矩形箭靶和 \(4N\) 头奶牛。每头牛都必须被分配一个不同的箭靶顶点。对于 \(1≤i≤N\)，在时刻 \(i\)：箭靶 \(i\) 出现。分配其顶点的 4 头奶牛向它们射箭。如果奶牛的箭在击中所分配的顶点之前穿过箭靶内部，或未命中，则奶牛们的练习失败。箭靶消失，为下一个箭靶腾出空间。

　　每头牛都位于 \(y\) 轴上，每个箭靶都是一个矩形，其中箭靶 \(i\) 的左下顶点坐标为 \((X,y_{i1})\)，右上顶点坐标为 \((x_{i2} ,y_{i2})\)。所有坐标满足 \(1≤X<x_{i2}≤10^9\) 以及 \(1≤y_{i1}<y_{i2}≤10^9\) （注意：对于每个箭靶\(x_i\) 都是相同的）。

　　此外，每头奶牛都有一个正在钻研的「瞄准」角度。因此她们在射箭时会转向特定的角度。考虑到她们的箭从她们的位置沿直线射向指定的顶点，奶牛 \(i\) 的箭的轨迹可以用轨迹的斜率 \(s_i（0<|s_i∣<10^9）\)来表示。

　　为了能够仔细检查奶牛们的技术，Farmer John 希望尽量缩短最远的奶牛之间的距离。如果 Farmer John 以最佳方式给每头奶牛分配箭靶顶点并将她们放置在 \(y\) 轴上，你能否帮助他求出最远奶牛之间的最小距离是多少，或者奶牛是否总是会练习失败？

【输入格式】

　　每个测试点包含 \(T（1≤T≤10）\)个独立的测试用例。输入保证所有测试用例的 \(N\) 之和不超过 \(4⋅10^4\)。
　　输入的第一行包含 \(T（1≤T≤10）\)，为测试用例的数量。每个测试用例的描述如下：
　　每个测试用例的第一行包含两个整数 \(N\) 和 \(X_1\) ，分别为箭靶的数量以及所有箭靶的左端的 \(x\) 坐标。
　　以下 \(N\) 行，第 \(i\) 行包含三个整数 \(y1(i) ，y2(i)\) 和 \(x2(i)\) ，分别为第 \(i\) 个箭靶的下端 \(y\) 坐标，上端 \(y\) 坐标和右端 \(x\) 坐标。
　　最后一行包含 \(4N\) 个整数 \(s_1,s_2,…,s_{4N}\) ，其中 \(s_i\) 表示奶牛 \(i\) 的射箭轨迹的斜率。

【输出格式】

　　输出最远奶牛之间的最小可能距离，或如果奶牛总是练习失败时输出 −1。　　

【输入输出样例】

　Input

3
2 1
1 3 6
4 6 3
1 -1 2 -2 3 -3 4 -4
2 1
1 3 6
4 6 3
1 1 2 2 3 3 4 4
2 1
1 3 3
4 6 3
1 -1 2 -2 3 -3 4 -4

　Output

17
-1
11

【样例解释】

　　对于测试用例 1，一个最佳分配方案是分别为奶牛 1−8 分配以下目标顶点：(6,1),(6,3),(3,4),(3,6),(1,4),(1,3),(1,6),(1,1)。这得出了奶牛 1−8 的 y 坐标如下：−5,9,−2,12,1,6,2,5，这给出了最小距离 12−(−5)=17。

　　第二个测试用例的答案是不可能的原因之一是，如果箭不穿过箭靶 1 的内部，不可能射中 (6,3) 处的顶点（箭靶 1 的右上顶点）。

【测试点性质】

　　测试点 \(2：\)对于所有的 \(1≤i≤4N\)，\(∣Si ∣\) 均相同。
　　测试点 \(3−9：\)所有测试用例的 \(N\) 之和不超过 1000。
　　测试点 \(10−15：\)没有额外限制。

【来源】

　　Mr.he