ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1392. Dreaming of Stars

Time limit: 0.5 second
Memory limit: 64 MB
For the whole last week Ilya Petrov spent his time sitting at the computer and playing his favourite game "Perimeter". But today he suddenly realized that he does not want to look at the monitor. "Hm… It is so strange… What will I do now?" thought Ilya. "Oh! Astronomy! — most wonderful of all sciences. This is what I need!" — he exclaimed. So he did not lose time, he came to a store and bought a big black telescope. This night he spent admiring the beauty of distant galaxies, unreachable (so far) for a human…
The magic of the moment was broken suddenly as Ilya noticed two planets, which have stuck each other. "What is it?" — exclaimed Ilya. He was really amazed. But he thought a little, took a paper and wrote down the following.
"Two planets have stuck each other if they have at least two common points. In this case we will say that each of the planets is reachable from another one. Then an archipelago is a group of planets for which the following conditions are true:
  • Each of planets of archipelago is reachable from any other planet of the archipelago (possibly in a several steps).
  • There are no planets of the archipelago reachable from any planet outside of archipelago.
Clearly, any set of planets can be uniquely split into archipelagos. You have to find the number of archipelagos for a given set of planets and from which planets each archipelago consists of. The solution of this task will make the humans more powerful and flawless race. So this task is to be solved immediately."


The first line of input contains a number K (0 < K ≤ 1000) — the number of the planets in a set. Then K lines with planet center coordinates X, Y, Z and planet radius R follow. All numbers are integer and they do not exceed 1000 by absolute value. Absence of coinciding planets is guaranteed. All the planets are balls.


Output must contain exactly P lines. Here P is the number of archipelagos in a given set of planets. The i-th line of output should contain the list of planets constituting the i-th archipelago. Each planet in a list is present by its number (planets are numbered by integers starting from 0). Planet numbers in a list must be printed in increasing order with a comma and a space as a separator. Do not print a comma after last number in a list.
Archipelagos must be printed in the following order. If the least number of the planet of one archipelago is less than the least number of the planet of another, then the first archipelago must precede the second in output.


1 1 1 1
1 3 1 1
1 1 1 1
1 3 1 1
1 4 1 1
1, 2
1000 1000 1000 1
 999 1000 1000 1
   1    1    1 1
0, 1
Problem Author: Fedor Fominykh
Problem Source: The 1st Collegiate Programming Contest of the High School Pupils of the Novouralsk Town (April, 2005)