표적 연습 II

참고: 이 문제에 나오는 정수는 매우 커서 64비트 정수 자료형(C/C++의 long long 등)을 써야 할 수 있습니다.

파리 무올림픽이 다가오고 있어 파머 존은 소 팀에게 양궁 훈련을 시키고 있습니다. 그는 2차원 좌표 평면에서 다음 연습을 준비했습니다.

축에 평행한 직사각형 표적이 $N$개($1 \leq N \leq 4 \cdot 10^4$) 있고, 소는 $4N$마리 있습니다. 모든 소는 서로 다른 표적의 꼭짓점에 하나씩 배정되어야 합니다. $1 \leq i \leq N$인 각 시점 $i$에서 다음 순서로 진행됩니다.

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)} \leq 10^9$, $1 \leq y_1^{(i)} < y_2^{(i)} \leq 10^9$을 만족합니다. $X_1$은 모든 표적에서 같습니다.

또한 각 소에는 집중하는 "조준 각도"가 있어서, 쏠 때 특정 각도로 방향을 틉니다. 화살은 소의 위치에서 배정된 꼭짓점까지 직선으로 날아갑니다. 소 $i$의 궤적은 기울기 $s_i$($0 < |s_i| < 10^9$)로 주어집니다.

파머 존은 소들의 기술을 자세히 살펴보고 싶어 합니다. 그래서 가장 멀리 떨어진 두 소 사이의 거리를 최소로 만들려 합니다. 각 소를 꼭짓점에 최적으로 배정하고 $y$축 위에 배치한다면, 가장 멀리 떨어진 소들 사이 거리의 최솟값은 얼마입니까? 소들이 항상 실패한다면 -1을 출력하세요.

첫 줄에 테스트 케이스의 개수 $T$ ($1 \leq T \leq 10$)가 주어집니다. 각 테스트 케이스는 다음과 같습니다.

각 테스트 케이스의 첫 줄에는 표적의 개수 $N$과 표적들의 가장 왼쪽 $x$ 좌표 $X_1$이 주어집니다. 이어서 $N$줄이 주어지며, $i$번째 줄에는 표적 $i$의 아래쪽 $y$ 좌표 $y_1^{(i)}$, 위쪽 $y$ 좌표 $y_2^{(i)}$, 오른쪽 $x$ 좌표 $x_2^{(i)}$가 주어집니다.

마지막 줄에는 $4N$개의 정수 $s_1, s_2, \dots, s_{4N}$이 주어집니다. $s_i$는 소 $i$가 쏘는 화살 궤적의 기울기입니다. 모든 테스트 케이스의 $N$ 합은 $4 \cdot 10^4$을 넘지 않습니다.

가장 멀리 떨어진 소들 사이 거리의 최솟값을 출력합니다. 소들이 항상 실패하면 $-1$을 출력합니다.