Description

巴黎牛奥会即将到来，农夫约翰正在训练他的奶牛队伍进行射箭训练！他在二维坐标平面上设置了以下练习。 有$N(1 \leq N \leq 4 \cdot 10^4)$个轴对齐的矩形靶子和$4N$头奶牛。每头奶牛必须被分配到一个不同的靶子顶点。在时刻$i$，对于$1 \leq i \leq N$：

1. 第$i$个靶子出现。
2. 被分配到其顶点的4头奶牛向它们射击。
3. 如果奶牛的射击丢靶或者射中了其他的靶子（包括穿过去了），奶牛们就会失败练习。
4. 靶子消失，为下一个腾出空间。

每头奶牛位于$y$轴上$(x=0)$，每个靶子是一个矩形，其中靶子的左下坐标在$(X_1,y_1^{(i)})$，右上坐标在$(x_2^{(i)},y_2^{(i)})$。坐标还满足$1 \leq X_1<x_2^{(i)} \leq 10^9$和$1 \leq y_1^{(i)}<y_2^{(i)} \leq 10^9$（注意：$X_1$对于每个靶子是相同的）。 此外，每头奶牛都有它们正在练习的“专注”角度。因此，它们在射击时会转动一个特定的角度。鉴于它们的射击沿直线从它们的位置向它们分配的顶点行进，奶牛的箭的轨迹可以通过$s_i\left(0<\left|s_i\right|<10^9\right)$，即轨迹的斜率来描述。 为了仔细检查奶牛的技术，农夫约翰希望最小化最远的奶牛之间的距离。如果农夫约翰能够最优地将每头奶牛分配给一个靶子顶点并将它们放置在$y$轴上，你能帮他确定最远的奶牛之间的最小距离是多少，或者奶牛们是否总会失败练习吗？ 每个输入包含$T(1 \leq T \leq 10)$个独立的测试案例。所有测试案例中$N$的总和保证不超过$4 \cdot 10^4$。

Format

Input

首行包含$T(1 \leq T \leq 10)$，即独立测试案例的数量。每个测试案例描述如下： 每个测试案例的第一行包含两个整数，$N$和$X_1$，分别代表目标的数量和目标的最左侧$x$-坐标。 接下来是$N$行，第$i$行包含三个整数，$y_1^{(i)}$、$y_2^{(i)}$和$x_2^{(i)}$，分别代表第$i$个目标的下$y$-坐标、上$y$-坐标和右$x$-坐标。

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

Output

最远的奶牛之间可能的最小距离，或者如果奶牛们总是会失败这个练习。

Samples

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$：

这给出了奶牛$1-8$相应的$y$位置：

这给出了最小距离$12-(-5)=17$。 第二个测试案例不可能的一个原因是因为不可能在不让射击穿过目标1内部的情况下射中$(6,3)$（目标1的右上顶点）。

评分：

• 输入2：$\left|S_i\right|$对所有$1 \leq i \leq 4N$相同。
• 输入3-9：所有测试案例中$N$的总和最多为1000。
• 输入10-15：没有额外的限制。