题目背景

注意：本题的时间限制为 2.5 秒，通常限制的 1.25 倍。

注意：这个问题涉及到的整数可能需要使用 64 位整数型（例如，C/C++ 中的 long long）。

题目描述

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

有 $N$（$1\le N\le 4\cdot 10^4$）个四边与坐标轴平行的矩形箭靶和 $4N$ 头奶牛。每头牛都必须被分配一个不同的箭靶顶点。对于 $1\le i\le N$，在时刻 $i$：

1. 箭靶 $i$ 出现。
2. 分配其顶点的 $4$ 头奶牛向它们射箭。
3. 如果奶牛的箭在击中所分配的顶点之前穿过箭靶内部，或未命中，则奶牛们的练习失败。
4. 箭靶消失，为下一个箭靶腾出空间。

每头牛都位于 $y$ 轴（$x=0$）上，每个箭靶都是一个矩形，其中箭靶 $i$ 的左下顶点坐标为 $(X_1,y^{(i)}_1)$，右上顶点坐标为 $(x^{(i)}_2,y^{(i)}_2)$。所有坐标满足 $1\le X_1<x^{(i)}_2\le 10^9$ 以及 $1\le y^{(i)}_1<y^{(i)}_2\le 10^9$（注意：$X_1$ 对于每个箭靶都是相同的）。

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

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

每个测试点包含 $T$（$1\le T\le 10$）个独立的测试用例。输入保证所有测试用例的 $N$ 之和不超过 $4\cdot 10^4$。

输入格式

输入的第一行包含 $T$（$1\le T\le 10$），为测试用例的数量。每个测试用例的描述如下：

每个测试用例的第一行包含两个整数 $N$ 和 $X_1$，分别为箭靶的数量以及所有箭靶的左端的 $x$ 坐标。

以下 $N$ 行，第 $i$ 行包含三个整数 $y^{(i)}_1$，$y^{(i)}_2$ 和 $x^{(i)}_2$，分别为第 $i$ 个箭靶的下端 $y$ 坐标，上端 $y$ 坐标和右端 $x$ 坐标。

最后一行包含 $4N$ 个整数 $s_1,s_2,\ldots,s_{4N}$，其中 $s_i$ 表示奶牛 $i$ 的射箭轨迹的斜率。

输出格式

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

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

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\le i\le 4N$，$|S_i|$ 均相同。
• 测试点 $3-9$：所有测试用例的 $N$ 之和不超过 $1000$。
• 测试点 $10-15$：没有额外限制。