Di masa depan yang jauh, umat manusia menemukan sebuah planet yang besar, hangat, dan subur untuk dikolonisasi, serta sedang membangun banyak pembangkit listrik guna menopang koloni baru tersebut. Teknologi yang menakjubkan memungkinkan para pembangun memanfaatkan energi Alam Semesta yang sangat besar. Namun, ada satu fakta kecil yang mereka lewatkan: membangun dua pembangkit listrik terlalu dekat satu sama lain menimbulkan risiko besar terjadinya reaksi berantai, yang pada gilirannya akan memicu ledakan dahsyat. Hal ini tentu saja harus dihindari.

Untungnya, terdapat dua jenis energi yang dapat digunakan pada pembangkit listrik, yang disebut energi terang dan energi gelap, yang tidak saling berinteraksi. Jika sebagian pembangkit listrik bekerja dengan energi terang dan sebagian lainnya dengan energi gelap, jarak antar pembangkit yang sejenis dapat menjadi lebih besar daripada sebelumnya, sehingga membuat keseluruhan proyek menjadi tidak terlalu berbahaya.

Tugas

Diberikan lokasi dari $n$ pembangkit listrik (planet tersebut cukup besar sehingga kita dapat memperlakukannya sebagai titik-titik pada bidang datar), tetapkan pada setiap pembangkit apakah menggunakan energi terang atau energi gelap sedemikian sehingga jarak Euklides antara dua pembangkit bertipe sama menjadi sebesar mungkin. Untuk menghindari keluaran bilangan riil, keluarkan kuadrat dari jarak maksimum ini sebagai jawaban, beserta pembagian pembangkit listrik ke dalam kelompok “terang” dan “gelap”.

Masukan

Pada baris pertama masukan terdapat sebuah bilangan bulat $N$ ($3 \le N \le 100\,000$) – banyaknya pembangkit listrik. Dari $N$ baris berikutnya, baris ke-$i$ berisi dua bilangan bulat $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$) – koordinat dari pembangkit ke-$i$. Semua titik berbeda satu sama lain.

Keluaran

Pada baris pertama keluaran, cetak sebuah bilangan bulat – kuadrat dari jarak maksimum yang dapat dicapai. Baris kedua harus berisi banyaknya pembangkit yang bekerja dengan energi terang, dan baris ketiga – daftar nomor pembangkit tersebut yang dipisahkan oleh spasi. Baris keempat dan kelima harus menjelaskan pembangkit energi gelap dalam format yang sama. Jika terdapat beberapa solusi yang valid, keluarkan salah satu saja di antaranya.

Subsoal

Examples

Input 1

4
0 3
0 0
3 0
3 3

Output 1

18
2
1 3
2
2 4