In ferner Zukunft hat die Menschheit einen großen, warmen und üppigen Planeten zur Kolonisierung gefunden und baut viele Kraftwerke, um die neue Kolonie zu versorgen. Die beeindruckende Technologie ermöglicht es den Erbauern, die gewaltige Energie des Universums zu nutzen. Allerdings gibt es eine Kleinigkeit, die sie übersehen haben: Baut man zwei Kraftwerke zu nah beieinander, besteht ein erhebliches Risiko einer Kettenreaktion, die wiederum zu einer spektakulären Explosion führen würde. Dies sollte offensichtlich vermieden werden.

Glücklicherweise gibt es zwei Arten von Energie, die in Kraftwerken genutzt werden können, genannt helle und dunkle Energie, welche nicht miteinander wechselwirken. Wenn einige der Kraftwerke mit heller und andere mit dunkler Energie betrieben werden, kann der Abstand zwischen gleichartigen Kraftwerken größer sein als zuvor, was das gesamte Unterfangen weniger gefährlich machen würde.

Aufgabe

Gegeben sind die Standorte von $n$ Kraftwerken (der Planet ist groß genug, sodass wir sie als Punkte in einer Ebene betrachten können). Weise jedem Kraftwerk entweder helle oder dunkle Energie zu, sodass der euklidische Abstand zwischen zwei Kraftwerken desselben Typs größtmöglich ist. Um die Ausgabe reeller Zahlen zu vermeiden, gib als Antwort das Quadrat dieses maximalen Abstands sowie die Aufteilung der Kraftwerke in „helle“ und „dunkle“ aus.

Eingabe

In der ersten Zeile der Eingabe steht eine einzelne ganze Zahl $N$ ($3 \le N \le 100\,000$) – die Anzahl der Kraftwerke. Von den folgenden $N$ Zeilen enthält die $i$-te jeweils zwei ganze Zahlen $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$) – die Koordinaten des $i$-ten Kraftwerks. Alle Punkte sind paarweise verschieden.

Ausgabe

Gib in der ersten Zeile der Ausgabe eine einzelne ganze Zahl aus – das Quadrat des maximal erreichbaren Abstands. Die zweite Zeile soll die Anzahl der mit heller Energie betriebenen Kraftwerke enthalten, die dritte Zeile eine durch Leerzeichen getrennte Liste der Nummern dieser Kraftwerke. Die vierte und fünfte Zeile sollen im gleichen Format die Kraftwerke mit dunkler Energie beschreiben. Falls es mehrere gültige Lösungen gibt, gib eine beliebige davon aus.

Teilaufgaben

Beispiele

Eingabe 1

4
0 3
0 0
3 0
3 3

Ausgabe 1

18
2
1 3
2
2 4