In un futuro lontano, l'umanità ha trovato un pianeta grande, caldo e rigoglioso da colonizzare, e sta costruendo molte centrali elettriche per sostenere la nuova colonia. Questa straordinaria tecnologia permette ai costruttori di sfruttare l'immensa energia dell'Universo. Tuttavia, c'è un piccolo dettaglio che hanno trascurato: costruire due centrali elettriche troppo vicine tra loro comporta un rischio considerevole di reazione a catena, che a sua volta porterebbe a un'esplosione spettacolare. Questo, ovviamente, va evitato.

Fortunatamente, esistono due tipi di energia utilizzabili nelle centrali, chiamati energia chiara ed energia oscura, che non interagiscono tra loro. Se alcune centrali elettriche funzionano a energia chiara e altre a energia oscura, la distanza tra centrali identiche può essere maggiore rispetto a prima, rendendo l'intera impresa meno pericolosa.

Compito

Date le posizioni di $n$ centrali (il pianeta è abbastanza grande da poterle trattare come punti su un piano), assegna a ogni centrale l'energia chiara oppure l'energia oscura in modo che la distanza euclidea tra due centrali dello stesso tipo sia la massima possibile. Per evitare l'output di numeri reali, stampa come risposta il quadrato di tale distanza massima, insieme alla partizione delle centrali in «chiare» e «oscure».

Dati di input

Nella prima riga di input si trova un singolo intero $N$ ($3 \le N \le 100\,000$) — il numero di centrali elettriche. Delle successive $N$ righe, la $i$-esima contiene due interi $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$) — le coordinate della $i$-esima centrale. Tutti i punti sono distinti.

Dati di output

Nella prima riga di output stampa un singolo intero — il quadrato della distanza massima che può essere raggiunta. La seconda riga deve contenere il numero di centrali che funzionano a energia chiara, la terza riga — un elenco separato da spazi dei numeri di queste centrali. La quarta e la quinta riga devono descrivere le centrali a energia oscura, nello stesso formato. Se esistono più soluzioni valide, stampane una qualsiasi.

Subtask

Examples

Input 1

4
0 3
0 0
3 0
3 3

Output 1

18
2
1 3
2
2 4