Base Stations

Viracell Telecommunication is the largest mobile network operator in Nevercity. To serve its customers better, the operator has mounted a large number of base transceiver stations (BTSs) across the city. Each BTS works on one of the predefined frequencies.

The network grew fast over the past few years, service quality dropped, and customers complained. The national regulator decided to investigate the issue and prepare an official report. For that, the regulator asked the operator to mount two special receivers, provided by the regulator, on two BTSs, so that signaling data from every BTS is collected for the investigation. The operator chooses which two BTSs carry the receivers. Short on time, the operator hired you to advise where to mount them.

What you found is that the best results come only when the signal interference between the two receivers is at its minimum. You also found two simple rules for reducing that interference. The first rule is that the receivers must be mounted on two BTSs with different frequencies. The second rule is that the receivers must be placed as far apart as possible. So your advice is to mount the receivers on the farthest pair of BTSs with different frequencies. The operator now asks you to find such a pair.

The input holds several test cases. The first line of each test case has a positive integer $n$, the number of BTSs in that test case ($2 \le n \le 100000$). Each of the next $n$ lines has three integers $x$, $y$, and $k$, where $(x, y)$ is the location of a BTS and $k$ is its frequency number ($0 \le x, y \le 10000$, $0 \le k < 100$). Each frequency number refers to one of the 100 predefined frequencies of the network. Every test case has at least two BTSs with different frequencies. Two different BTSs may share the same location. The input ends with a line holding a single 0, which must not be processed.

For each test case, print one line with the square of the distance of the farthest pair of BTSs with different frequencies.