当前没有测试数据。

一、题目名称

射击练习 II（Target Practice II）

二、题目描述

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

有$N$（$1\leq N\leq4\cdot10^4$）个与坐标轴平行的矩形目标和$4N$头奶牛。每头奶牛必须被分配到一个不同的目标顶点。在时刻$i$（$1\leq i\leq N$）：

1. 目标$i$出现。
2. 分配到其顶点的$4$头奶牛向它们射击。
3. 如果一头奶牛的射击在击中指定顶点之前穿过目标内部或未击中，奶牛们此次练习失败。
4. 目标消失以为下一个目标腾出空间。

每头奶牛位于$y$轴（$x = 0$）上，每个目标是一个矩形，目标$i$的左下角坐标为$(X_1,y_1^{(i)})$，右上角坐标为$(x_2^{(i)},y_2^{(i)})$。坐标还满足$1\leq X_1<x_2^{(i)}\leq10^9$且$1\leq y_1^{(i)}<y_2^{(i)}\leq10^9$（注意：每个目标的$X_1$相同）。

此外，每头奶牛都有一个正在练习的“聚焦”角度。因此，它们射击时会以特定角度转身。假设它们的射击从其位置沿直线射向指定顶点，奶牛$i$的箭的轨迹可以用$s_i$（$0<\vert s_i\vert<10^9$）表示，即轨迹的斜率。

为了仔细检查奶牛们的技术，农夫约翰想最小化最远奶牛之间的距离。如果农夫约翰要最优地将每头奶牛分配到一个目标顶点并将它们放置在$y$轴上，你能帮助他确定最远奶牛之间的最小距离是多少，或者奶牛们是否总是会在练习中失败吗？

每个输入包含$T$（$1\leq T\leq10$）个独立的测试用例。所有测试用例中$N$的总和保证不超过$4\cdot10^4$。

三、输入格式（从终端/标准输入读取）

1. 第一行包含$T$（$1\leq T\leq10$），即独立测试用例的数量。每个测试用例描述如下：
   • 每个测试用例的第一行包含两个整数，$N$和$X_1$，分别是目标的数量和目标最左边的$x$坐标。
   • 接下来是$N$行，第$i$行包含三个整数，$y_1^{(i)}$，$y_2^{(i)}$和$x_2^{(i)}$，分别是第$i$个目标的下$y$坐标、上$y$坐标和右$x$坐标。
   • 最后一行包含$4N$个整数，$s_1,s_2,\cdots,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 的右上角顶点）。

六、评分规则

1. 输入 2：对于所有$1\leq i\leq4N$，$\vert s_i\vert$相同。
2. 输入 3 - 9：所有测试用例中$N$的总和最多为$1000$。
3. 输入 10 - 15：无其他额外约束。

题目来源：Suhas Nagar。