Astrologists took a hard scientific look at their zodiac horoscope predictions and realised that their methodology doesn't provide future insight better than chance. Instead of looking inwards they blame the stars and historical construction of constellations for their inability to predict the future. They're testing out a new way of constructing constellations that will renew their powers of future-sight.

They need your help to implement their iterative constellation creation system. Initially every star represents its own constellation. In every step you should merge two constellations into one, by picking the constellations that are closest to each other. The distance between two constellations $$$A$$$ and $$$B$$$ is defined as the average squared Euclidean distance of pairs of stars from each constellation:

$$$$$$ d(A, B) = \frac{1}{|A||B|}\sum_{a\in A}\sum_{b\in B}||a-b||^2.$$$$$$

If multiple pairs have the same distance you should merge older constellations first. When comparing two pairs of constellations that could be merged, first compare the distances between constellations. If both pairs are at exactly the same distance, compare them by the age of the older constellation in a pair. If there is still a tie, compare them by the age of the newer constellation in a pair. A constellation's age is defined by the time when it was formed with the last merge, or in case of single-star constellations by the age of the star. The stars in the input are listed from oldest to youngest.