Target Practice II

Note: The large size of integers involved in this problem may require 64-bit integer data types (e.g., "long long" in C/C++).

The Paris Moolympics are coming up, and Farmer John is training his cows in archery. He has set up the following exercise on the 2D coordinate plane.

There are $N$ ($1 \leq N \leq 4 \cdot 10^4$) axis-aligned rectangular targets and $4N$ cows. Every cow must be assigned to a different target vertex. At moment $i$, for $1 \leq i \leq N$:

1. Target $i$ appears.
2. The 4 cows assigned to its vertices shoot at them.
3. If a cow's shot passes through the interior of the target before it hits the assigned vertex or misses, the cows fail the exercise.
4. The target disappears to make space for the next one.

Each cow is located on the $y$-axis ($x = 0$). Target $i$ is a rectangle with lower left corner $(X_1, y_1^{(i)})$ and upper right corner $(x_2^{(i)}, y_2^{(i)})$. The coordinates satisfy $1 \leq X_1 < x_2^{(i)} \leq 10^9$ and $1 \leq y_1^{(i)} < y_2^{(i)} \leq 10^9$. Note that $X_1$ is the same for every target.

Each cow also has a "focus" angle, so it turns to a specific angle when it shoots. A shot travels in a straight line from the cow's position to its assigned vertex. The trajectory of cow $i$ has slope $s_i$ ($0 < |s_i| < 10^9$).

Farmer John wants to examine the cows' technique closely, so he wants to minimize the distance between the two cows that are furthest apart. If he assigns each cow to a target vertex optimally and places the cows on the $y$-axis, what is the minimum possible distance between the furthest cows? If the cows will always fail the exercise, output -1 instead.

The first line contains $T$ ($1 \leq T \leq 10$), the number of test cases. Each test case is described as follows.

The first line of each test case contains two integers $N$ and $X_1$, the number of targets and the leftmost $x$-coordinate of the targets. Then $N$ lines follow. The $i$-th line contains three integers $y_1^{(i)}$, $y_2^{(i)}$, and $x_2^{(i)}$, the lower $y$-coordinate, the upper $y$-coordinate, and the right $x$-coordinate of target $i$.

The last line contains $4N$ integers $s_1, s_2, \dots, s_{4N}$, where $s_i$ is the slope of cow $i$'s shot. The sum of $N$ across all test cases does not exceed $4 \cdot 10^4$.

Print the minimum possible distance between the furthest cows, or $-1$ if the cows will always fail the exercise.