Dr. Evil has contracted your valuable services to build for him the world's most powerful "laser". Of course before you spend one billion dollars building the thing, you want to run some simulations first to make sure everything will work as designed. For this phase of the project, you will be simulating part of the aiming system which uses mirrors and other optics to change the direction of the laser beam.
The simulation consists of a flat square table with mirrors, beam splitters, and beam detectors arranged on the tabletop, and with each object represented by a one dimensional line segment. The list below describes each of the object types in detail:
detector : A detector is an opaque object which absorbs any laser beam striking it. The simulation must also keep track of which detectors are struck by a laser for program output purposes. Note that a laser beam strike on either side of a detector counts as a "hit".
splitter : When a laser beam strikes a splitter, it divides into two beams. One of the new beams will reflect from the splitter surface (as with a mirror), and the other beam will pass through the splitter without changing direction. A splitter will function the same way regardless which side of it is struck by a laser beam.
See the figures below for examples of a laser beam's interaction with each of the possible object types:
|Mirror Object||Splitter Object||Detector Object|
For each simulation, a single laser beam enters the tabletop area. The program must compute the path taken by the laser beam (including secondary beams due to splitters), and it must determine which detectors are struck by a laser beam.
You can make the following assumptions in the program:
Input to this problem will begin with a line containing a single integer N (1 ≤ N ≤ 100) indicating the number of data sets. Each data set consists of the following components:
For each data set in the input, output the heading "DATA SET #k" where k is 1 for the first data set, 2 for the second, etc. If in this data set none of the detector objects are struck by any laser beams, output the message "NO BEAMS DETECTED". Otherwise, output the object number, one per line, of each detector struck by a laser beam. The list of detectors should be sorted by their object numbers and output in ascending order. If a detector is struck by more than one laser beam, it should only be listed once in the output.
1 50,100 0,-1 6 D 0,40 20,20 M 40,20 60,40 D 80,20 100,40 D 0,70 20,90 S 40,90 60,70 D 80,90 100,70
DATA SET #1 1 6