먼 미래에 인류는 식민지로 삼을 거대하고 따뜻하며 울창한 행성을 발견했고, 새로운 식민지를 지탱하기 위해 수많은 발전소를 건설하고 있다. 놀라운 기술 덕분에 건설자들은 우주의 방대한 에너지를 활용할 수 있다. 하지만 그들이 간과한 작은 사실이 하나 있다. 두 발전소를 서로 너무 가깝게 지으면 연쇄 반응이 일어날 상당한 위험이 발생하며, 이는 결국 거대한 폭발로 이어지게 된다. 물론 이러한 일은 피해야 한다.

다행히도 발전소에서 사용할 수 있는 에너지에는 빛 에너지와 어둠 에너지라고 불리는 두 가지 종류가 있으며, 이 둘은 서로 상호작용하지 않는다. 일부 발전소가 빛 에너지로 작동하고 일부가 어둠 에너지로 작동한다면, 같은 종류의 발전소 사이의 거리가 이전보다 더 멀어질 수 있어 전체 사업의 위험성을 줄일 수 있다.

과제

$n$개의 발전소의 위치가 주어질 때(행성이 충분히 크므로 이들을 평면 위의 점으로 취급할 수 있다), 같은 종류의 두 발전소 사이의 유클리드 거리가 가능한 한 최대가 되도록 모든 발전소에 빛 에너지 또는 어둠 에너지를 배정하라. 실수 출력을 피하기 위해, 정답으로 이 최대 거리의 제곱과 발전소들을 “빛”과 “어둠”으로 분할한 결과를 함께 출력하라.

입력

입력의 첫째 줄에는 발전소의 개수를 나타내는 하나의 정수 $N$ ($3 \le N \le 100\,000$)이 주어진다. 다음 $N$개의 줄 중 $i$번째 줄에는 $i$번째 발전소의 좌표를 나타내는 두 정수 $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$)가 주어진다. 모든 점은 서로 다르다.

출력

출력의 첫째 줄에 달성할 수 있는 최대 거리의 제곱을 나타내는 정수 하나를 출력한다. 둘째 줄에는 빛 에너지로 작동하는 발전소의 개수를, 셋째 줄에는 이 발전소들의 번호를 공백으로 구분한 목록을 출력해야 한다. 넷째 줄과 다섯째 줄에는 어둠 에너지 발전소들을 같은 형식으로 기술해야 한다. 올바른 해가 여러 개라면 그중 아무것이나 하나를 출력한다.

서브태스크

예제

입력 1

4
0 3
0 0
3 0
3 3

출력 1

18
2
1 3
2
2 4