Những đội quân "chính nghĩa" phiền phức lại đang chuẩn bị đến làm phiền vùng đất yên bình của lũ Goblin. Việc xây dựng một bức tường cao lớn đã không mang lại hiệu quả như mong đợi, vì vậy lũ Goblin quyết định chuyển sang một phương án phòng thủ cổ điển và đáng tin cậy hơn: một con hào chứa đầy nham thạch.

Chúng muốn đào con hào này như một ranh giới ngăn cách vùng đất của Goblin ở phía Bắc và vùng đất của những kẻ "thánh thiện" ở phía Nam, trải dài toàn bộ biên giới từ Tây sang Đông.

Thách thức

Khu vực biên giới này rất mấp mô, thậm chí có nhiều đồi núi. Trong khi đó, một con hào nham thạch phải nằm trên cùng một cao độ (cùng một độ cao \(z\)) — nếu không, nham thạch từ các phần cao hơn sẽ chảy xuống và tràn ra khỏi hào ở những phần thấp hơn. Do đó, lũ Goblin phải chọn một con đường có cao độ không đổi, nối liền biên giới phía Tây và biên giới phía Đông của vùng đất. Vì lý do kinh tế, chúng muốn con đường này phải ngắn nhất có thể.

Dữ liệu địa hình

Bạn được cung cấp một bản đồ cao độ của vùng biên giới. Nhiệm vụ của bạn là xác định độ dài ngắn nhất mà con hào có thể đạt được.

• Bản đồ có dạng một hình chữ nhật kích thước \(w \times \ell\) đã được chia lưới tam giác hoàn toàn (fully triangulated). Tất cả các tam giác đều có diện tích dương.
• Không có đỉnh nào của tam giác nằm bên trong cạnh của một tam giác khác.
• Góc Tây Nam của bản đồ có tọa độ \((0, 0)\), trục \(x\) hướng về phía Đông và trục \(y\) hướng về phía Bắc.
• Biên giới phía Tây (đoạn thẳng nối \((0, 0)\) và \((0, \ell)\)) là một cạnh duy nhất của lưới. Tương tự, biên giới phía Đông (nối \((w, 0)\) và \((w, \ell)\)) cũng là một cạnh duy nhất.

Đây là hình chiếu 2D của địa hình 3D thực tế: mỗi điểm \((x, y)\) đều có một cao độ \(z\). Cao độ tại các đỉnh của lưới tam giác được cung cấp trực tiếp và tất cả các cao độ này là phân biệt. Cao độ tại bất kỳ điểm nào khác có thể được tính bằng cách nội suy tuyến tính trên các mặt tam giác tương ứng. Nói cách khác, địa hình được tạo thành từ một tập hợp các mặt tam giác nối với nhau tại các cạnh chung.

Input

Dòng đầu tiên chứa số nguyên \(t\) (\(1 \le t \le 10\,000\)), là số lượng bộ dữ liệu (test cases). Các dòng tiếp theo mô tả chi tiết từng bộ dữ liệu.

Mỗi bộ dữ liệu bắt đầu bằng một dòng chứa bốn số nguyên \(w, \ell, n, m\):

• \(w\) (\(1 \le w \le 10^6\)): Chiều rộng của vùng biên giới từ Tây sang Đông.
• \(\ell\) (\(1 \le \ell \le 10^6\)): Chiều dài từ Nam sang Bắc.
• \(n\) (\(4 \le n \le 50\,000\)): Số lượng đỉnh.
• \(m\) (\(n - 2 \le m \le 2n - 6\)): Số lượng tam giác trong lưới tam giác được cung cấp.

Tiếp theo là \(n\) dòng, dòng thứ \(i\) chứa ba số nguyên \(x_i, y_i, z_i\) (\(0 \le x_i \le w; 0 \le y_i \le \ell; 0 \le z_i \le 10^6\)), biểu thị tọa độ và cao độ của đỉnh \(i\).

• Các đỉnh duy nhất có \(x_i = 0\) hoặc \(x_i = w\) là bốn góc của hình chữ nhật.
• Tất cả các cặp tọa độ \((x_i, y_i)\) là duy nhất.
• Tất cả các giá trị cao độ \(z_i\) là duy nhất.

Tiếp theo là \(m\) dòng, mỗi dòng chứa ba số nguyên phân biệt \(a, b, c\) (\(1 \le a, b, c \le n\)), biểu thị một tam giác được tạo bởi các đỉnh \(a, b\) và \(c\) theo thứ tự ngược chiều kim đồng hồ. Các tam giác này tạo thành một lưới tam giác hoàn chỉnh phủ kín hình chữ nhật \([0, w] \times [0, \ell]\). Mỗi đỉnh trong số \(n\) đỉnh được tham chiếu bởi ít nhất một tam giác.

Lưu ý: Tổng giá trị của \(n\) trên tất cả các bộ dữ liệu không vượt quá \(50\,000\).

Output

Với mỗi bộ dữ liệu:

• Nếu có thể xây dựng một con hào nham thạch ở một cao độ duy nhất nối từ biên phía Tây sang biên phía Đông, hãy in ra độ dài ngắn nhất của con hào đó. Kết quả được chấp nhận nếu có sai số tuyệt đối hoặc tương đối không vượt quá \(10^{-6}\).
• Nếu không thể xây dựng được, in ra impossible.

3
6 6 4 2
0 0 1
6 0 4
6 6 3
0 6 2
1 2 3
1 3 4
6 6 4 2
0 0 1
6 0 2
6 6 4
0 6 3
1 2 3
1 3 4
10 6 7 7
6 1 8
10 0 10
10 6 4
2 6 6
0 6 0
4 3 11
0 0 7
2 1 7
2 3 1
3 6 1
3 4 6
6 4 5
5 7 6
7 1 6

impossible
6.708203932
15.849260054