Dans un futur lointain, l'humanité a découvert une grande planète chaude et luxuriante à coloniser, et construit de nombreuses centrales électriques pour alimenter la nouvelle colonie. Cette technologie stupéfiante permet aux bâtisseurs d'exploiter la vaste énergie de l'Univers. Cependant, ils ont négligé un petit détail : construire deux centrales électriques trop près l'une de l'autre engendre un risque considérable de réaction en chaîne, ce qui mènerait à son tour à une explosion spectaculaire. Cela doit évidemment être évité.

Heureusement, il existe deux types d'énergie utilisables dans les centrales, appelés énergie claire et énergie sombre, qui n'interagissent pas entre eux. Si certaines centrales électriques fonctionnent à l'énergie claire et d'autres à l'énergie sombre, la distance entre des centrales identiques peut être plus grande qu'auparavant, ce qui rendrait l'ensemble du projet moins dangereux.

Tâche

Étant donné les emplacements de $n$ centrales (la planète est suffisamment grande pour qu'on puisse les considérer comme des points dans un plan), attribuez à chaque centrale soit l'énergie claire, soit l'énergie sombre, de sorte que la distance euclidienne entre deux centrales de même type soit la plus grande possible. Pour éviter d'afficher des nombres réels, affichez comme réponse le carré de cette distance maximale, ainsi que la partition des centrales en centrales « claires » et « sombres ».

Entrée

La première ligne de l'entrée contient un seul entier $N$ ($3 \le N \le 100\,000$) — le nombre de centrales électriques. Parmi les $N$ lignes suivantes, la $i$-ème contient deux entiers $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$) — les coordonnées de la $i$-ème centrale. Tous les points sont distincts.

Sortie

Sur la première ligne de la sortie, affichez un seul entier — le carré de la distance maximale pouvant être atteinte. La deuxième ligne doit contenir le nombre de centrales fonctionnant à l'énergie claire, et la troisième ligne — une liste des numéros de ces centrales séparés par des espaces. Les quatrième et cinquième lignes doivent décrire les centrales à énergie sombre, dans le même format. S'il existe plusieurs solutions valides, affichez l'une quelconque d'entre elles.

Sous-tâches

Exemples

Entrée 1

4
0 3
0 0
3 0
3 3

Sortie 1

18
2
1 3
2
2 4