{"raw_statement":[{"iden":"background","content":"**注意：本题的时间限制为 2.5 秒，通常限制的 1.25 倍。**\n\n**注意：这个问题涉及到的整数可能需要使用 64 位整数型（例如，C/C++ 中的 `long long`）。**"},{"iden":"statement","content":"巴黎哞运会即将来临，Farmer John 正在对他的奶牛队进行射箭训练！他在二维坐标平面上设置了以下练习。\n\n有 $N$（$1\\le N\\le 4\\cdot 10^4$）个四边与坐标轴平行的矩形箭靶和 $4N$ 头奶牛。每头牛都必须被分配一个不同的箭靶顶点。对于 $1\\le i\\le N$，在时刻 $i$：\n\n1. 箭靶 $i$ 出现。\n2. 分配其顶点的 $4$ 头奶牛向它们射箭。\n3. 如果奶牛的箭在击中所分配的顶点之前穿过箭靶内部，或未命中，则奶牛们的练习失败。\n4. 箭靶消失，为下一个箭靶腾出空间。\n\n每头牛都位于 $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$ 对于每个箭靶都是相同的）。\n\n此外，每头奶牛都有一个正在钻研的「瞄准」角度。因此她们在射箭时会转向特定的角度。考虑到她们的箭从她们的位置沿直线射向指定的顶点，奶牛 $i$ 的箭的轨迹可以用轨迹的斜率 $s_i$（$0<|s_i|<10^9$）来表示。\n\n为了能够仔细检查奶牛们的技术，Farmer John 希望尽量缩短最远的奶牛之间的距离。如果 Farmer John 以最佳方式给每头奶牛分配箭靶顶点并将她们放置在 $y$ 轴上，你能否帮助他求出最远奶牛之间的最小距离是多少，或者奶牛是否总是会练习失败？\n\n每个测试点包含 $T$（$1\\le T\\le 10$）个独立的测试用例。输入保证所有测试用例的 $N$ 之和不超过 $4\\cdot 10^4$。 "},{"iden":"input","content":"输入的第一行包含 $T$（$1\\le T\\le 10$），为测试用例的数量。每个测试用例的描述如下：\n\n每个测试用例的第一行包含两个整数 $N$ 和 $X_1$，分别为箭靶的数量以及所有箭靶的左端的 $x$ 坐标。\n\n以下 $N$ 行，第 $i$ 行包含三个整数 $y^{(i)}_1$，$y^{(i)}_2$ 和 $x^{(i)}_2$，分别为第 $i$ 个箭靶的下端 $y$ 坐标，上端 $y$ 坐标和右端 $x$ 坐标。\n\n最后一行包含 $4N$ 个整数 $s_1,s_2,\\ldots,s_{4N}$，其中 $s_i$ 表示奶牛 $i$ 的射箭轨迹的斜率。"},{"iden":"output","content":"输出最远奶牛之间的最小可能距离，或如果奶牛总是练习失败时输出 $−1$。"},{"iden":"note","content":"### 样例解释\n\n对于测试用例 $1$，一个最佳分配方案是分别为奶牛 $1-8$ 分配以下目标顶点：\n\n$$(6,1),(6,3),(3,4),(3,6),(1,4),(1,3),(1,6),(1,1)$$\n\n这得出了奶牛 $1-8$ 的 $y$ 坐标如下：\n\n$$−5,9,−2,12,1,6,2,5$$\n\n这给出了最小距离 $12−(−5)=17$。\n\n第二个测试用例的答案是不可能的原因之一是，如果箭不穿过箭靶 $1$ 的内部，不可能射中 $(6,3)$ 处的顶点（箭靶 $1$ 的右上顶点）。\n\n### 测试点性质\n\n- 测试点 $2$：对于所有的 $1\\le i\\le 4N$，$|S_i|$ 均相同。\n- 测试点 $3-9$：所有测试用例的 $N$ 之和不超过 $1000$。\n- 测试点 $10-15$：没有额外限制。"}],"translated_statement":null,"sample_group":[["3\n2 1\n1 3 6\n4 6 3\n1 -1 2 -2 3 -3 4 -4\n2 1\n1 3 6\n4 6 3\n1 1 2 2 3 3 4 4\n2 1\n1 3 3\n4 6 3\n1 -1 2 -2 3 -3 4 -4","17\n-1\n11"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}