在遙遠的未來，人類發現了一顆巨大、溫暖且鬱鬱蔥蔥的行星進行殖民，並正在建造大量發電廠以維持新殖民地的運轉。這項驚人的技術使建造者能夠利用宇宙的浩瀚能量。然而，他們忽略了一個小事實：把兩座發電廠建得離彼此太近會帶來引發連鎖反應的巨大風險，進而導致一場驚天動地的爆炸。顯然，這應當避免。

幸運的是，發電廠可以使用兩種能量，稱為光能和暗能，它們互不發生作用。如果一部分發電廠使用光能運作，另一部分使用暗能運作，那麼同類發電廠之間的距離就可能比之前更大，從而使整個工程的危險性降低。

任務

給定 $n$ 座發電廠的位置（該行星足夠大，我們可以將它們視為平面上的點），為每座發電廠分配光能或暗能，使得兩座同類型發電廠之間的歐幾里得距離盡可能大。為了避免實數輸出，請輸出該最大距離的平方作為答案，同時輸出將發電廠劃分為「光能」和「暗能」兩類的方案。

輸入格式

輸入的第一行包含一個整數 $N$（$3 \le N \le 100\,000$）——發電廠的數量。接下來的 $N$ 行中，第 $i$ 行包含兩個整數 $x_i, y_i$（$0 \le x_i, y_i \le 10^9$）——第 $i$ 座發電廠的座標。所有點互不相同。

輸出格式

在輸出的第一行印出一個整數——能夠達到的最大距離的平方。第二行應包含使用光能運作的發電廠數量，第三行——以空格分隔的這些發電廠的編號列表。第四行和第五行應以相同格式描述暗能發電廠。如果存在多種合法方案，輸出其中任意一種即可。

子任務

範例

輸入格式 1

4
0 3
0 0
3 0
3 3

輸出格式 1

18
2
1 3
2
2 4