ในอนาคตอันไกลโพ้น มนุษยชาติได้ค้นพบดาวเคราะห์ดวงใหญ่ที่อบอุ่นและอุดมสมบูรณ์เพื่อตั้งอาณานิคม และกำลังสร้างโรงไฟฟ้าจำนวนมากเพื่อหล่อเลี้ยงอาณานิคมแห่งใหม่ เทคโนโลยีอันน่าทึ่งช่วยให้ผู้สร้างสามารถนำพลังงานอันมหาศาลของจักรวาลมาใช้ได้ อย่างไรก็ตาม มีข้อเท็จจริงเล็กๆ ข้อหนึ่งที่พวกเขามองข้ามไป นั่นคือการสร้างโรงไฟฟ้าสองแห่งใกล้กันเกินไปก่อให้เกิดความเสี่ยงอย่างมากที่จะเกิดปฏิกิริยาลูกโซ่ ซึ่งจะนำไปสู่การระเบิดครั้งมโหฬารในที่สุด เห็นได้ชัดว่าควรหลีกเลี่ยงสิ่งนี้

โชคดีที่มีพลังงานสองประเภทที่สามารถนำมาใช้ในโรงไฟฟ้าได้ เรียกว่าพลังงานสว่างและพลังงานมืด ซึ่งไม่ทำปฏิกิริยากันเอง หากโรงไฟฟ้าบางแห่งทำงานด้วยพลังงานสว่าง และบางแห่งทำงานด้วยพลังงานมืด ระยะห่างระหว่างโรงไฟฟ้าชนิดเดียวกันก็อาจมากกว่าเดิม ซึ่งจะทำให้โครงการทั้งหมดมีความเสี่ยงลดลง

งาน

กำหนดตำแหน่งของโรงไฟฟ้า $n$ แห่ง (ดาวเคราะห์มีขนาดใหญ่พอที่เราจะถือว่าโรงไฟฟ้าเหล่านั้นเป็นจุดบนระนาบได้) จงกำหนดให้โรงไฟฟ้าแต่ละแห่งใช้พลังงานสว่างหรือพลังงานมืด เพื่อทำให้ระยะทางแบบยุคลิดระหว่างโรงไฟฟ้าชนิดเดียวกันสองแห่งมีค่ามากที่สุดเท่าที่เป็นไปได้ เพื่อหลีกเลี่ยงการแสดงผลเป็นจำนวนจริง ให้แสดงผลคำตอบเป็นกำลังสองของระยะทางมากที่สุดนี้ พร้อมทั้งการแบ่งกลุ่มโรงไฟฟ้าออกเป็นกลุ่ม “สว่าง” และกลุ่ม “มืด”

ข้อมูลนำเข้า

ในบรรทัดแรกของข้อมูลนำเข้ามีจำนวนเต็มหนึ่งจำนวนคือ $N$ ($3 \le N \le 100\,000$) แทนจำนวนโรงไฟฟ้า ในอีก $N$ บรรทัดถัดมา บรรทัดที่ $i$ มีจำนวนเต็มสองจำนวนคือ $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$) แทนพิกัดของโรงไฟฟ้าแห่งที่ $i$ จุดทุกจุดแตกต่างกันทั้งหมด

ข้อมูลส่งออก

ในบรรทัดแรกของข้อมูลส่งออก ให้พิมพ์จำนวนเต็มหนึ่งจำนวน คือกำลังสองของระยะทางมากที่สุดที่สามารถทำได้ บรรทัดที่สองควรระบุจำนวนโรงไฟฟ้าที่ทำงานด้วยพลังงานสว่าง ส่วนบรรทัดที่สามเป็นรายการหมายเลขของโรงไฟฟ้าเหล่านี้คั่นด้วยช่องว่าง บรรทัดที่สี่และบรรทัดที่ห้าควรอธิบายโรงไฟฟ้าพลังงานมืดในรูปแบบเดียวกัน หากมีคำตอบที่ถูกต้องได้หลายแบบ ให้แสดงคำตอบใดคำตอบหนึ่ง

งานย่อย

ตัวอย่าง

ข้อมูลนำเข้า 1

4
0 3
0 0
3 0
3 3

ข้อมูลส่งออก 1

18
2
1 3
2
2 4