School Colors

Time limit1sMemory limit128 MB

Summary

Given up to 200 RGB colors, find every pair whose Euclidean distance is maximal and print the index pairs in sorted order.

Level: Easy3 of 10
Topics: Brute force, Geometry, Implementation, Math
Solved: No attempts yet

Problem

You already know a university's school colors, right? They may not be the prettiest combination, but at least each one is legible written on top of the other — much better than, say, Cardinal and Red, or Green and Turquoise. One imagines that universities make some effort to pick contrasting colors. But did they pick the most contrasting ones?

In this problem you will write a program that finds the most contrasting pair of colors in a given list. Each color is specified by a triple $(R, G, B)$ denoting its red, green, and blue values, where each value is an integer between 0 and 255. The triple $(0, 0, 0)$ is Black and $(255, 255, 255)$ is White. The contrast between two colors is the Euclidean distance between their triples: for $(R, G, B)$ and $(R', G', B')$ it is $\sqrt{(R - R')^2 + (G - G')^2 + (B - B')^2}$ .

Hint: think Cardinal and Gold.

Input

The first line contains an integer $K \ge 1$ , the number of data sets. It is followed by $K$ data sets of the following form.

The first line of a data set contains an integer $n$ ( $2 \le n \le 200$ ), the number of colors in the data set. It is followed by $n$ lines, each containing three integers $R_i$ , $G_i$ , $B_i$ ( $0 \le R_i, G_i, B_i \le 255$ ) — the red, green, and blue values of the $i$ -th color in the list.

Output

For each data set, first output a line “Data Set x:” by itself, where $x$ is the data set's number (starting from 1). Then output the pair of colors with the largest possible contrast, given as two 1-based indices per line. If several pairs achieve the largest contrast, output all of them, sorted by increasing first index, breaking ties by increasing second index.

Examples3

Example 1

Input

2
3
0 0 0
100 100 100
0 200 0
4
0 0 0
0 255 255
255 0 0
255 255 255

Expected output

Data Set 1:
1 3
Data Set 2:
1 4
2 3

Example 2
Input
```
1
2
0 0 0
255 255 255
```
Expected output
```
Data Set 1:
1 2
```

Example 3

Input

Expected output

Data Set 1:
1 2
1 3
2 3