Trong một trò chơi điện tử dựa trên vật lý 2D, hai nhân vật $P$ và $Q$ di chuyển khắp chiến trường. Mỗi nhân vật được biểu diễn bởi một đa giác lồi đóng vai trò là hộp va chạm (collision box) của nó. Khi hai hộp va chạm chồng lên nhau, trò chơi sẽ tính diện tích phần giao của chúng làm sát thương va chạm.

Tuy nhiên, do các luồng gió khó lường trong đấu trường, nhân vật $Q$ có thể bị dịch chuyển bởi một vectơ tịnh tiến tùy ý $\mathbf{t} = (t_x, t_y)$, nhưng không thể xoay hoặc lật. Bạn cần tính kỳ vọng của sát thương va chạm khi $Q$ được đặt ngẫu nhiên phân bố đều sao cho nó thực sự va chạm với $P$, tức là phần giao của chúng có diện tích dương.

Một cách hình thức hơn, định nghĩa $f(\mathbf{t})$ là diện tích phần giao giữa đa giác biểu diễn nhân vật $P$ và đa giác biểu diễn nhân vật $Q$ sau khi được tịnh tiến theo $\mathbf{t}$. Gọi $D \subseteq \mathbb{R}^2$ là tập hợp tất cả các vectơ tịnh tiến $\mathbf{t}$ sao cho $f(\mathbf{t}) > 0$. Có thể chứng minh rằng $D$ có diện tích dương, ký hiệu là $|D|$. Bạn cần tính $\frac{1}{|D|} \iint_D f(\mathbf{t})\,d\mathbf{t}$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên $T$ ($1 \le T \le 300$), biểu thị số lượng bộ dữ liệu. Đối với mỗi bộ dữ liệu:

• Dòng đầu tiên chứa hai số nguyên $n$ và $m$ ($3 \le n, m \le 1\,000$), lần lượt biểu thị số đỉnh của hai đa giác lồi.
• Tiếp theo là $n$ dòng, mỗi dòng chứa hai số nguyên $x$ và $y$ ($-10^4 \le x, y \le 10^4$), cho biết tọa độ đỉnh $(x, y)$ của đa giác biểu diễn nhân vật $P$.
• Tiếp theo là $m$ dòng, mỗi dòng chứa hai số nguyên $x$ và $y$ ($-10^4 \le x, y \le 10^4$), cho biết tọa độ đỉnh $(x, y)$ của đa giác biểu diễn nhân vật $Q$.
• Dữ liệu đảm bảo các đỉnh của mỗi đa giác lồi được cho theo thứ tự ngược chiều kim đồng hồ, và không có ba đỉnh nào thẳng hàng.

Dữ liệu đảm bảo cả tổng của $n$ và tổng của $m$ trong tất cả các bộ dữ liệu đều không vượt quá $1\,000$.

Kết quả

Đối với mỗi bộ dữ liệu, in ra một dòng chứa một số thực biểu thị sát thương va chạm kỳ vọng.

Câu trả lời của bạn được chấp nhận nếu sai số tuyệt đối hoặc tương đối của nó không vượt quá $10^{-6}$. Nói một cách hình thức, giả sử kết quả của bạn là $a$ và đáp án của ban giám khảo là $b$, kết quả của bạn được chấp nhận khi và chỉ khi $\frac{|a - b|}{\max(1, |b|)} \le 10^{-6}$.

Ví dụ

Dữ liệu vào 1

2
3 3
0 0
1 0
0 1
0 0
1 0
0 1
3 3
0 0
1 0
0 1
0 1
1 0
1 1

Kết quả 1

0.083333333333
0.125000000000