Trong tương lai xa, nhân loại đã tìm thấy một hành tinh rộng lớn, ấm áp và trù phú để định cư, đồng thời đang xây dựng rất nhiều nhà máy điện nhằm cung cấp năng lượng cho thuộc địa mới. Công nghệ đáng kinh ngạc cho phép những người xây dựng khai thác nguồn năng lượng bao la của Vũ trụ. Tuy nhiên, có một chi tiết nhỏ mà họ đã bỏ sót: việc xây dựng hai nhà máy điện quá gần nhau mang lại nguy cơ đáng kể gây ra phản ứng dây chuyền, từ đó dẫn đến một vụ nổ kinh hoàng. Hiển nhiên, điều này cần phải tránh.

May mắn thay, có hai loại năng lượng có thể sử dụng trong các nhà máy, được gọi là năng lượng ánh sáng và năng lượng bóng tối, không tương tác với nhau. Nếu một số nhà máy điện hoạt động bằng năng lượng ánh sáng và một số hoạt động bằng năng lượng bóng tối, khoảng cách giữa các nhà máy cùng loại có thể lớn hơn trước, giúp toàn bộ công trình bớt nguy hiểm hơn.

Yêu cầu

Cho vị trí của $n$ nhà máy (hành tinh đủ lớn để ta có thể coi chúng là các điểm trên mặt phẳng), hãy gán cho mỗi nhà máy năng lượng ánh sáng hoặc năng lượng bóng tối sao cho khoảng cách Euclid giữa hai nhà máy cùng loại là lớn nhất có thể. Để tránh việc in ra số thực, hãy in ra bình phương của khoảng cách lớn nhất này làm đáp án, cũng như cách phân hoạch các nhà máy thành nhóm “ánh sáng” và nhóm “bóng tối”.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $N$ ($3 \le N \le 100\,000$) – số lượng nhà máy điện. Trong $N$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$) – tọa độ của nhà máy thứ $i$. Tất cả các điểm đều phân biệt.

Dữ liệu ra

Ở dòng đầu tiên của dữ liệu ra, hãy in một số nguyên duy nhất – bình phương của khoảng cách lớn nhất có thể đạt được. Dòng thứ hai chứa số lượng nhà máy hoạt động bằng năng lượng ánh sáng, dòng thứ ba – danh sách chỉ số của các nhà máy này, cách nhau bởi dấu cách. Dòng thứ tư và dòng thứ năm mô tả các nhà máy năng lượng bóng tối theo cùng định dạng. Nếu có nhiều phương án hợp lệ, hãy in ra bất kỳ phương án nào trong số đó.

Nhiệm vụ con

Ví dụ

Dữ liệu vào 1

4
0 3
0 0
3 0
3 3

Dữ liệu ra 1

18
2
1 3
2
2 4