Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Time limit: 0.5s | Memory limit: 64MB

Đây là một thời kỳ hỗn loạn, những lãnh chúa cắt đất xưng hùng và tranh chấp lẫn nhau hòng đoạt được toàn bộ đất đai trên hành tinh E.

Tuy không phải một lãnh chúa, nhưng với lợi thế vượt trội về công nghệ quân sự (cụ thể như chiếc tàu chiến Destruction), Ngọc Mai quyết tâm dẹp loạn và thống trị toàn bộ hành tinh E.

Tuy nhiên, đây là một cuộc loạn đả, nên cũng sẽ không có gì lạ nếu có một lãnh chúa bị tất cả những đối thủ của mình công kích, và “nạn nhân” đó cũng hoàn toàn có thể là Mai nếu cô tham chiến bất cẩn. Để tránh điều này, cô quyết tâm phân tích sức mạnh của các đối thủ trước.

Hành tinh E bao gồm n lãnh chúa cát cứ các khu vực. Mỗi lãnh chúa được đặc trưng bởi vùng đất mình chiếm cứ - với lãnh chúa thứ i, vùng đất của hắn là một đa giác lồi gồm m_i đỉnh.

Vì có quá nhiều công việc cần chuẩn bị, Mai giao việc phân tích dữ liệu đối thủ cho đội ngũ quân sư: khối công việc cần giao gồm q truy vấn, thuộc 2 loại sau:

- Loại 1: “1 k a₁ a₂ … a_k” – yêu cầu cho biết diện tích vùng giao giữa vùng đất của k lãnh chúa: a₁, a₂, …, cho tới a_k.

- Loại 2: “2 x” – yêu cầu cho biết tổng diện tích các vùng đất của lãnh chúa thứ x mà không giao cắt với đất đai của bất kỳ lãnh chúa nào khác.

Với vai trò là đại diện của đội ngũ quân sư của Mai, bạn cần phải trả lời kết quả công việc sớm nhất có thể (trước khi cô ấy nổi điên và trừng phạt bạn cùng toàn bộ đội ngũ vì làm việc trễ nải). Hẳn bạn không muốn tình huống xấu nhất xảy ra chứ?

Input

Dòng đầu tiên chứa một số nguyên dương n (2 ≤ n ≤ 10) là số lượng lãnh chúa trên hành tinh E.

Phần input tiếp theo là thông tin về mỗi lãnh chúa, với lãnh chúa thứ i:

- Khởi đầu bằng dòng chứa một số nguyên dương m_i (3 ≤ m_i ≤ 100), là số lượng đỉnh trong đa giác lồi đại diện cho lãnh địa của lãnh chúa thứ i.

- m_i dòng tiếp theo, dòng thứ j gồm 2 số nguyên x_j, y_j (-10⁶ ≤ x_j, y_j ≤ 10⁶); cho biết tọa độ của đỉnh thứ j trong đa giác lồi đại diện cho lãnh địa của lãnh chúa thứ i.

- Input đảm bảo, m_i điểm đã cho ở trên hợp thành một đa giác lồi, và các đỉnh được sắp xếp theo thứ tự thuận chiều kim đồng hồ (với điểm đầu tiên được chọn bất kỳ).

Dòng tiếp theo chứa một số nguyên dương q (1 ≤ q ≤ 5000) là số lượng truy vấn trong khối công việc mà Ngọc Mai yêu cầu.

q dòng tiếp theo, mỗi dòng gồm 1 truy vấn, bắt đầu bằng số nguyên t (1 ≤ t ≤ 2) là loại truy vấn:

- Nếu t = 1, tiếp theo t là một số nguyên k (2 ≤ k ≤ n), rồi tiếp đến là k số nguyên a₁, a₂, …, a_k (1 ≤ a_j ≤ n). Input đảm bảo trong mỗi truy vấn thì các giá trị trên là đôi một khác nhau.

- Nếu t = 2, tiếp theo t là một số nguyên x (1 ≤ x ≤ n).

Output

In ra q dòng, dòng thứ i là câu trả lời cho truy vấn thứ i của Ngọc Mai. Đáp án được chấp nhận với sai số tương đối hoặc tuyệt đối không quá 10 ^-6 với mỗi truy vấn.

Example

Input:
2
4
0 0
0 2
2 2
2 0
4
1 1
1 3
3 3
3 1
4
1 2 1 2
1 2 2 1
2 1
2 2
Output:
1.000000000
1.000000000
3.000000000
3.000000000

Giải thích:

Bản đồ lãnh địa của hành tinh E cho test 1. Lãnh chúa 1 được biểu diễn bằng màu tím, lãnh chúa 2 được biểu diễn bằng màu xanh. Vùng giao của 2 lãnh chúa là tứ giác ICJE.