기지국

비라셀 통신은 네버시티에서 가장 큰 이동통신 사업자다. 고객에게 더 나은 서비스를 제공하려고 도시 곳곳에 기지국을 아주 많이 세웠다. 각 기지국은 미리 정해 둔 주파수 중 하나를 쓴다.

지난 몇 년 동안 망이 빠르게 커지면서 서비스 품질이 떨어졌고 고객 불만이 많아졌다. 규제 기관은 이 문제를 조사해 공식 보고서를 쓰기로 했다. 그래서 규제 기관은 자신들이 마련한 특수 수신기 두 대를 기지국 두 곳에 설치하라고 사업자에게 요청했다. 두 수신기는 모든 기지국의 신호 데이터를 모은다. 어느 기지국에 설치할지는 사업자가 자유롭게 고를 수 있다. 시간이 부족한 사업자는 어디에 설치해야 가장 좋은 결과가 나오는지 자문을 구하려고 당신을 고용했다.

당신이 알아낸 바로는 두 수신기의 신호 간섭이 가장 작을 때만 가장 좋은 결과가 나온다. 간섭을 줄이는 간단한 규칙도 두 가지 찾았다. 첫째, 두 수신기는 주파수가 서로 다른 기지국에 설치해야 한다. 둘째, 두 수신기는 될 수 있는 대로 멀리 떨어져 있어야 한다. 그래서 당신은 주파수가 서로 다른 기지국 쌍 가운데 가장 멀리 떨어진 쌍에 수신기를 설치하라고 권하기로 했다. 사업자는 그런 쌍을 찾아 달라고 한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 기지국의 개수를 나타내는 양의 정수 $n$이 주어진다 ($2 \le n \le 100000$). 이어지는 $n$개의 줄에는 각각 세 정수 $x$, $y$, $k$가 주어진다. $(x, y)$는 기지국의 위치이고 $k$는 주파수 번호다 ($0 \le x, y \le 10000$, $0 \le k < 100$). 주파수 번호는 망에 미리 정해 둔 서로 다른 주파수 100개 중 하나를 가리킨다. 각 테스트 케이스에는 주파수가 서로 다른 기지국이 적어도 두 개 있다. 서로 다른 기지국의 위치가 같을 수도 있다. 입력의 마지막 줄에는 0이 하나 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 주파수가 서로 다른 기지국 쌍 중 가장 멀리 떨어진 쌍의 거리의 제곱을 한 줄에 출력한다.