في المستقبل البعيد، عثرت البشرية على كوكب كبير ودافئ وخصب لاستعماره، وهي تبني الكثير من محطات الطاقة لدعم المستعمرة الجديدة. تتيح التكنولوجيا المذهلة للبناة تسخير الطاقة الهائلة للكون. ومع ذلك، هناك حقيقة صغيرة أغفلوها: إن بناء محطتي طاقة قريبتين جدًا من بعضهما ينطوي على خطر كبير لحدوث تفاعل متسلسل، وهو ما سيؤدي بدوره إلى انفجار هائل. ومن الواضح أنه يجب تجنب ذلك.

لحسن الحظ، هناك نوعان من الطاقة يمكن استخدامهما في المحطات، يُسمّيان الطاقة الضوئية والطاقة المظلمة، وهما لا يتفاعلان مع بعضهما البعض. إذا عملت بعض محطات الطاقة بالطاقة الضوئية وبعضها الآخر بالطاقة المظلمة، فقد تصبح المسافة بين المحطات المتماثلة أكبر من ذي قبل، مما يجعل المشروع بأكمله أقل خطورة.

المهمة

بالنظر إلى مواقع $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