У далекому майбутньому людство знайшло велику, теплу та квітучу планету для колонізації й будує багато електростанцій для підтримки нової колонії. Приголомшливі технології дозволяють будівельникам приборкувати неосяжну енергію Всесвіту. Проте є один невеликий факт, який вони випустили з уваги: будівництво двох електростанцій надто близько одна до одної створює значний ризик ланцюгової реакції, яка своєю чергою призведе до грандіозного вибуху. Цього, вочевидь, слід уникати.

На щастя, існують два типи енергії, які можна використовувати на станціях, що називаються світлою та темною енергією і не взаємодіють між собою. Якщо частина електростанцій працюватиме на світлій енергії, а частина — на темній, відстань між однаковими станціями може бути більшою, ніж раніше, що зробить усю справу менш небезпечною.

Завдання

За заданими розташуваннями $n$ станцій (планета достатньо велика, тож ми можемо вважати їх точками на площині) призначте кожній станції світлу або темну енергію так, щоб евклідова відстань між двома станціями одного типу була максимально можливою. Щоб уникнути виведення дійсних чисел, виведіть як відповідь квадрат цієї максимальної відстані, а також розбиття станцій на «світлі» та «темні».

Вхідні дані

У першому рядку вхідних даних міститься одне ціле число $N$ ($3 \le N \le 100\,000$) — кількість електростанцій. Із наступних $N$ рядків $i$-й містить два цілі числа $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$) — координати $i$-ї станції. Усі точки різні.

Вихідні дані

У першому рядку вихідних даних виведіть одне ціле число — квадрат максимальної відстані, якої можна досягти. Другий рядок повинен містити кількість станцій, що працюють на світлій енергії, третій рядок — розділений пробілами список номерів цих станцій. Четвертий і п'ятий рядки повинні описувати станції на темній енергії в такому самому форматі. Якщо існує декілька коректних розв'язків, виведіть будь-який із них.

Підзадачі

Examples

Input 1

4
0 3
0 0
3 0
3 3

Output 1

18
2
1 3
2
2 4