Lưu ý: Giới hạn thời gian cho bài này là 2.5s, gấp 1.25 so với mặc định.
Lưu ý: Bài tập có thể sử dụng đến những số rất lớn, nên sử dụng kiểu số nguyên 64-bit (VD: "long long" trong C/C++).

Thế vận hội Moolympics đang đến gần và nông dân John đang gấp rút huấn luyện những con bò của mình bắn cung để đạt được huy chương vàng. Nông dân John đã thiết lập bài luyện tập có thể mô tả trên mặt phẳng toạ độ \(2D\)

• Có tất cả \(N\) (\(1 \leq N \leq 4 \times 10^4\)) mục tiêu hình chữ nhật và \(4\times N\) con bò. Mỗi con bò đều được chỉ định một đỉnh của mục tiêu. Tại thời điểm \(i\) \((1 \leq i \leq N)\) có các sự kiện:
  • Mục tiêu thứ \(i\) xuất hiện
  • \(4\) con bò ở các đỉnh được chỉ định bắn vào mục tiêu.
  • Nếu một con bò bắn vào mục tiêu trước khi bắn vào cạnh của nó hoặc bắn trượt, con bò đó sẽ không vượt qua bài tập.
  • Mục tiêu biến mất và mục tiêu tiếp theo xuất hiện
• Những con bò sẽ đứng bắn từ trục tung(\(x=0\)) của bản đồ nông trại.
• Mục tiêu thứ \(i\) có tọa độ của góc dưới bên trái là (\(X_1, y_1^{(i)}\)) và góc trên bên phải có tọa độ (\(x_2^{(i)},y_2^{(i)}\)). Tọa độ của các mục tiêu thỏa mãn \(1 \leq X_1 < x_2^{(i)} \leq 10^9\) và \(1 \leq y_1^{(i)}< y_2^{(i)}\le 10^9\)(Ghi chú: \(X_1\) giống nhau cho mọi mục tiêu)

Ngoài ra,mỗi con bò có một góc "tập trung" mà chúng đang luyện tập. Theo đó, chúng sẽ quay một góc cố định mỗi khi bắn. Biết rằng nếu cú bắn của chúng bay thẳng từ vị trí của chúng đến cạnh mà chúng được chỉ định, độ dốc đường bay của mũi tên của con bò thứ \(i\) có thể được mô tả bởi \(s_i\) (\(0 < |s_i| < 10^9\))

Để thẩm định kĩ năng của những con bò, nông dân John muốn những con bò đứng sát nhau nhất có thể. Nếu nông dân John chỉ định mục tiêu của những con bò một cách tối ưu và đặt chúng trên trục tung, khoảng cách nhỏ nhất giữa hai con bò cách xa nhau nhất sẽ là bao nhiêu hay chúng sẽ luôn trượt bài luyện tập.

Dữ liệu vào có tất cả \(T\) (\(1 \leq T \leq 10\)) test case riêng biệt. Dữ liệu đảm bảo tổng \(N\) của tất cả các test case không quá \(4 \times 10^4\).

Input:

• Dòng đầu tiên chứa \(T\) \((1 \leq T \leq 10)\)
• Dòng đầu tiên của mỗi test case chứa hai số nguyên \(N\) và \(X_1\) mô tả số lượng mục tiêu và vị trí của cạnh bên trái của những mục tiêu.
• \(N\) dòng tiếp theo chứa ba số nguyên \(y_1^{(i)}, y_2^{(i)}\) và \(x_2^{(i)}\) mô tả hình dạng của mục tiêu.
• Dòng cuối cùng chứa \(4N\) số nguyên \(s_{1}, s_{2}, \ldots, s_{4\times N}\), trong đó \(s_{i}\) là độ dốc đường bay của con bò thứ \(i\).

Output:

• Gồm \(T\) dòng trả lời cho từng test case, mỗi dòng là khoảng cách nhỏ nhất có thể giữa hai con bò ở xa nhau nhất hoặc "-1" nếu những con bò trượt bài tập.

Scoring:

• Subtask 1: \(|s_{i}|\) giống nhau với mọi \(1 \leq i \leq 4\times N\).
• Subtask 2: Tổng số \(N\) trong tất cả các test case không vượt quá \(1000\).
• Subtask 3: Không có ràng buộc gì thêm.

Example

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