Battle II

Daltons (Daida, Alhar, Tara, and Reyton) love playing games. One of their favorite games is ’Battle II’. In order to play this game, first, one of them is chosen as a problem-setter. The problem-setter starts drawing some bombs on a piece of paper (each bomb is a circle: has a center and a radius). She then associates to each bomb a destruction range. There are three rules defined in this game:

1. If a bomb explodes, all the bombs in its destruction range will also explode. A bomb b1 is in destruction range of another bomb b2 if distance of b2 from the perimeter of b1 is less than the range of b1. (i.e. b2.range + b1.radius + b2.radius ≥ Distance(b1.center, b2.center))
2. A bomb may explode due to either being affected by explosion of another bomb according to the first rule or manually being fired.
3. Firing a bomb manually has a cost which is equal to the range of it. She finally gives the configuration of the bombs to the others and asks them to find a sequence of bombs to fire which should satisfy the following conditions:
4. All the bombs should be exploded as a result of firing and explosion of the bombs in this sequence. 2. The i-th bomb in the sequence should not result explosion of the j-th bomb where j > i.
5. The average cost of firing the bombs that are in the sequence must be minimum. You should help the players find the solution to this problem by writing a program which is able to find such a sequence given the specifications and configuration of the bombs in the paper. Input The first line of input gives the number of cases, N. N test cases will follow. Each one starts with a line containing the number of bombs (0 < n ≤ 300). Each of the next n lines contains four integers Xi, Yi, Ri, Ei, meaning that the i-th bomb is located at (Xi, Yi), has a radius of Ri, and has a range of Ei. There will be a blank line after each block of test case. Output For each test case, output the line containing ‘Case #x:’, followed by list of bombs in the order that should be fired, seperated by a single space. Follow the output format used in sample output. If there are more than one solution, any of them is acceptable. “Marriage, in life, is like a duel in the midst of the battle” Edmond About

2/2 Sample Input 1 3 4722 8510 3 -3 1 1 Sample Output Case #1: 1 0 2