בעתיד הרחוק מצאה האנושות כוכב לכת גדול, חמים ושופע ליישוב, והיא בונה תחנות כוח רבות כדי לתמוך במושבה החדשה. הטכנולוגיה המדהימה מאפשרת לבונים לרתום את האנרגיה העצומה של היקום. עם זאת, ישנה עובדה קטנה שהם החמיצו: בניית שתי תחנות כוח קרובות מדי זו לזו יוצרת סיכון ממשי לתגובת שרשרת, שתוביל בתורה לפיצוץ אדיר. מובן שיש להימנע מכך.
למרבה המזל, קיימים שני סוגי אנרגיה שבהם ניתן להשתמש בתחנות, הנקראים אנרגיית אור ואנרגיית חושך, אשר אינם מגיבים זה עם זה. אם חלק מתחנות הכוח יפעלו על אנרגיית אור וחלקן על אנרגיית חושך, המרחק בין תחנות זהות עשוי להיות גדול מבעבר, דבר שיהפוך את המיזם כולו למסוכן פחות.
משימה
בהינתן המיקומים של $n$ תחנות (כוכב הלכת גדול מספיק כך שנוכל להתייחס אליהן כאל נקודות במישור), הקצו לכל תחנה אנרגיית אור או אנרגיית חושך כך שהמרחק האוקלידי בין שתי תחנות מאותו סוג יהיה גדול ככל האפשר. כדי להימנע מפלט של מספרים ממשיים, הדפיסו כתשובה את ריבוע המרחק המקסימלי הזה, וכן את החלוקה של התחנות לתחנות "אור" ו"חושך".
קלט
בשורה הראשונה של הקלט מופיע מספר שלם יחיד $N$ ($3 \le N \le 100\,000$) – מספר תחנות הכוח. מבין $N$ השורות הבאות, השורה ה-$i$ מכילה שני מספרים שלמים $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$) – הקואורדינטות של התחנה ה-$i$. כל הנקודות שונות זו מזו.
פלט
בשורה הראשונה של הפלט הדפיסו מספר שלם יחיד – ריבוע המרחק המקסימלי שניתן להשיג. השורה השנייה צריכה להכיל את מספר התחנות הפועלות על אנרגיית אור, והשורה השלישית – רשימה מופרדת ברווחים של מספרי התחנות הללו. השורות הרביעית והחמישית צריכות לתאר את תחנות אנרגיית החושך, באותו פורמט. אם קיימים מספר פתרונות חוקיים, הדפיסו אחד מהם.
תת-משימות
| תת-משימה | ניקוד | $n$ מרבי |
|---|---|---|
| 1 | 10 | 100 |
| 2 | 25 | 2000 |
| 3 | 65 | $100\,000$ |
Examples
Input 1
4 0 3 0 0 3 0 3 3
Output 1
18 2 1 3 2 2 4