En un futuro lejano, la humanidad encontró un planeta grande, cálido y exuberante para colonizar, y está construyendo muchas centrales eléctricas para abastecer a la nueva colonia. Esta asombrosa tecnología permite a los constructores aprovechar la vasta energía del Universo. Sin embargo, hay un pequeño detalle que pasaron por alto: construir dos centrales eléctricas demasiado cerca la una de la otra conlleva un riesgo considerable de reacción en cadena, lo que a su vez provocaría una explosión espectacular. Esto, obviamente, debe evitarse.

Afortunadamente, existen dos tipos de energía que se pueden utilizar en las centrales, llamadas energía luminosa y energía oscura, las cuales no interactúan entre sí. Si algunas de las centrales eléctricas funcionan con energía luminosa y otras con energía oscura, la distancia entre centrales idénticas puede ser mayor que antes, lo que haría que toda la empresa fuera menos peligrosa.

Tarea

Dadas las ubicaciones de $n$ centrales (el planeta es lo suficientemente grande como para tratarlas como puntos en un plano), asigna a cada central energía luminosa u oscura de modo que la distancia euclidiana entre dos centrales del mismo tipo sea la máxima posible. Para evitar imprimir números reales, muestra como respuesta el cuadrado de esta distancia máxima, así como la partición de las centrales en «luminosas» y «oscuras».

Entrada

En la primera línea de la entrada hay un único entero $N$ ($3 \le N \le 100\,000$): el número de centrales eléctricas. De las siguientes $N$ líneas, la $i$-ésima contiene dos enteros $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$): las coordenadas de la $i$-ésima central. Todos los puntos son distintos.

Salida

En la primera línea de la salida, imprime un único entero: el cuadrado de la distancia máxima que se puede alcanzar. La segunda línea debe contener el número de centrales que funcionan con energía luminosa, y la tercera línea, una lista separada por espacios con los números de dichas centrales. La cuarta y la quinta línea deben describir las centrales de energía oscura en el mismo formato. Si existen múltiples soluciones válidas, imprime cualquiera de ellas.

Subtareas

Ejemplos

Entrada 1

4
0 3
0 0
3 0
3 3

Salida 1

18
2
1 3
2
2 4