Truy vấn diện tích

Cho một đa giác lồi $n$ đỉnh trên mặt phẳng tọa độ. Các đỉnh được đánh số từ $1$ đến $n$ theo chiều kim đồng hồ; đỉnh thứ $i$ có tọa độ $(x_i,y_i)$.

Ban đầu đa giác chưa có đường chéo nào.

Bạn cần xử lý $q$ truy vấn thuộc ba loại sau:

• A $i$ $j$: vẽ thêm một đường chéo nối đỉnh $i$ với đỉnh $j$. Dữ liệu đảm bảo đỉnh $i$ không kề đỉnh $j$, đường chéo nối hai đỉnh này chưa tồn tại ngay trước truy vấn, và nó không cắt bất kỳ đường chéo nào đang có, ngoại trừ tại các đầu mút.
• R $i$ $j$: xóa đường chéo nối đỉnh $i$ với đỉnh $j$. Dữ liệu đảm bảo đường chéo này tồn tại ngay trước truy vấn.
• ? $i$ $j$: các đường chéo đang có chia đa giác thành các mảnh nhỏ hơn. Hãy giải bài toán con sau: chọn bỏ đi một số mảnh (có thể không bỏ mảnh nào) sao cho:
  • Mảnh chứa cả đỉnh thứ $i$ và đỉnh thứ $(imodn+1)$ không bị bỏ.
  • Mảnh chứa cả đỉnh thứ $j$ và đỉnh thứ $(jmodn+1)$ không bị bỏ.
  • Hai mảnh nói trên vẫn liên thông với nhau.
  • Tổng diện tích các mảnh bị bỏ là lớn nhất có thể.

Hai mảnh $A$ và $B$ được coi là liên thông khi và chỉ khi cả hai đều không bị bỏ và thỏa mãn một trong hai điều kiện sau:

• $A$ và $B$ có chung một cạnh.
• Tồn tại một mảnh $C$ không bị bỏ sao cho $C$ liên thông với cả $A$ và $B$.

Lưu ý rằng trong các truy vấn loại thứ ba, không có mảnh nào thực sự bị bỏ đi. Bạn chỉ giải bài toán con và in ra tổng diện tích lớn nhất có thể của các mảnh bị bỏ. Các đỉnh và các cạnh của đa giác luôn giữ nguyên.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ dữ liệu. Mỗi bộ có dạng:

• Dòng đầu tiên chứa số nguyên $n$ ($3\le n\le 2·{10}^5$), số đỉnh của đa giác.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $x_i$ và $y_i$ ($0\le |x_i|,|y_i|\le {10}^9$), tọa độ đỉnh thứ $i$.
• Dòng tiếp theo chứa số nguyên $q$ ($1\le q\le 2·{10}^5$), số truy vấn.
• $q$ dòng tiếp theo, mỗi dòng chứa một truy vấn theo một trong các dạng trên.

Dữ liệu vào kết thúc bằng một dòng chứa số $0$, dòng này không phải là một bộ dữ liệu.

Dữ liệu đảm bảo:

• Tổng $n$ trên mọi bộ dữ liệu không vượt quá $2·{10}^5$.
• Tổng $q$ trên mọi bộ dữ liệu không vượt quá $2·{10}^5$.

Dữ liệu ra

Với mỗi truy vấn loại thứ ba, in ra một số thực trên một dòng: tổng diện tích lớn nhất có thể của các mảnh bị bỏ.

Đáp án được coi là đúng nếu sai số tương đối hoặc tuyệt đối không vượt quá ${10}^{-6}$. Cụ thể, gọi $C$ là đáp án của bạn và $J$ là đáp án của ban giám khảo, đáp án được chấp nhận nếu $\frac{|C-J|}{max(1,|J|)}\le {10}^{-6}$.

Ràng buộc

• $3\le n\le 2·{10}^5$, $1\le q\le 2·{10}^5$, $0\le |x_i|,|y_i|\le {10}^9$; đa giác lồi, các đỉnh theo chiều kim đồng hồ.
• Tổng $n$ và tổng $q$ trên mọi bộ dữ liệu đều không vượt quá $2·{10}^5$.

Ví dụ