Sau nhiều ngày quan sát các ngôi sao trên bầu trời, Alice nhận thấy có chòm sao. Mỗi chòm sao bao gồm một số lượng chẵn các ngôi sao có quy luật vận động giống nhau. Để thuận lợi cho việc theo dõi và khảo sát, Alice đánh số các chòm sao từ đến . Trong mỗi chòm sao đó, các ngôi sao được đánh thứ tự từ cho đến số lượng ngôi sao có trong chòm sao. Alice xem xét các ngôi sao trên một hệ trục tọa độ Đề-các, trong đó ngôi sao thứ trong chòm sao thứ có tọa độ nguyên . Sau khi phân tích về mặt hình học, Alice phát hiện ra các đặc tính sau:
Trong mỗi chòm sao có duy nhất một ngôi sao không di chuyển, ngôi sao này được đánh số thứ tự trong chòm sao đó. Tất cả các ngôi sao còn lại, sau mỗi ngày, mỗi ngôi sao sẽ di chuyển đến một vị trí mới bằng cách thực hiện cùng một góc quay khi lấy ngôi sao được đánh số thứ tự làm tâm. Góc quay của mỗi chòm sao là một trong loại , , theo chiều kim đồng hồ;
Tại bất kỳ ngày nào, luôn tồn tại cách vẽ, nối vị trí của tất cả các ngôi sao của mỗi chòm sao thành một đa giác chuẩn không tự cắt, có số đỉnh bằng số ngôi sao trong chòm sao và các đỉnh của đa giác là vị trí của các ngôi sao. Đa giác chuẩn không tự cắt là đa giác có các cạnh song song với trục tọa độ, không có đỉnh nào liên tiếp thẳng hàng và không có cạnh không liên tiếp nào của đa giác có điểm chung.
Để khảo sát độ phân tán của các chòm sao, sau mỗi ngày, với vị trí mới của các ngôi sao trong mỗi chòm sao, Alice sẽ vẽ một đa giác chuẩn không tự cắt cho từng chòm sao để diện tích được phủ bởi tất cả đa giác trên hệ trục tọa độ là lớn nhất.
Yêu cầu: Cho tọa độ các ngôi sao của mỗi chòm sao tại ngày đâu tiên (ngày ) mà Alice tiến hành quan sát cùng với quy luật quay của từng chòm sao. Hãy tính diện tích phủ lớn nhất bởi đa giác được vẽ ở ngày thứ .
Dữ liệu vào:
Dòng đâu tiên chứa số nguyên dương và số tự nhiên ;
Tiếp theo là nhóm dòng, mỗi nhóm mô tả về một chòm sao. Nhóm dòng thứ có khuôn dạng như sau:
Dòng đầu chứa hai số , và , trong đó là số ngôi sao trong chòm sao ( là số chẵn thỏa mãn ) và là giá trị góc quay (một trong loại giá trị , , ;
Dòng thứ trong dòng tiếp theo chứa hai số nguyên . Các ngôi sao trong cùng một chòm sao có tọa độ phân biệt.
Các số trên cùng một dòng cách nhau bởi dấu cách.
Dữ liệu ra:
Ghi ra một số nguyên duy nhất là diện tích phủ lớn nhất bởi đa giác chuẩn được vẽ ở ngày thứ .
Giới hạn:
Có số test ứng với số điểm của bài thỏa mãn điều kiện: và các đều có giá trị bằng ;
số test khác ứng với số điểm của bài thỏa mãn điều kiện: và các đều có giá trị bằng ;
số test khác ứng với số điểm của bài thỏa mãn điều kiện: ;
số test còn lại ứng với số điểm của bài thỏa mãn điều kiện: .
