В далёком будущем человечество обнаружило большую, тёплую и цветущую планету для колонизации и строит множество электростанций для обеспечения новой колонии. Потрясающие технологии позволяют строителям обуздать необъятную энергию Вселенной. Однако есть одна маленькая деталь, которую они упустили из виду: строительство двух электростанций слишком близко друг к другу несёт значительный риск цепной реакции, которая, в свою очередь, приведёт к грандиозному взрыву. Этого, очевидно, следует избегать.

К счастью, существуют два вида энергии, которые можно использовать на станциях, называемые светлой и тёмной энергией, и они не взаимодействуют друг с другом. Если часть электростанций будет работать на светлой энергии, а часть — на тёмной, расстояние между одинаковыми станциями может стать больше, чем прежде, что сделает всё предприятие менее опасным.

Задача

По заданным координатам $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