The Screen Behind the Mirror

The demon Park Seung-won is looking for the most powerful laser in the world and has hired you for the task. You have a laser prototype, but before you can receive a budget to build it, you must show Park Seung-won a simulation.

The simulation begins by placing "mirrors", "beam splitters", and "beam detectors" on a 2D plane. Each object is modeled as a line segment.

• Mirror (M): a beam that hits a mirror is reflected across the mirror's segment.
• Detector (D): absorbs any incoming beam.
• Splitter (S): splits an incoming beam into two. One beam passes straight through the splitter with its direction unchanged; the other is reflected across the splitter's segment.

Given a laser fired from a starting point in a given direction, determine which detectors absorb a beam. To simplify the problem, you may assume the following.

• You only need to simulate a square region with side length $100$, and every object lies inside this region.
• The given segments never overlap or touch one another.
• The laser is fired from the edge of the square region.
• The simulation ends once every beam has either left the region or been absorbed by a detector.
• Over the whole simulation, the laser beam is reflected fewer than $100$ times.
• There is at least $1$ detector.
• During the simulation, the laser beam is never collinear with any object.

The first line contains the number of test cases $N$. Each test case is given as follows.

• The first line gives the laser's starting point $(x, y)$ and direction vector $(i, j)$ in the format "x,y i,j". The starting point lies on the edge of the region. All numbers are integers with $-1024 \le i, j \le 1024$.
• The second line gives the number of objects $P$. $(1 \le P \le 100)$
• Each of the next $P$ lines describes one object. The line begins with a character giving the object type — "M" for a mirror, "S" for a splitter, and "D" for a detector — followed by the two endpoints of the segment, each in the format "x,y".
• Objects are numbered from $1$ to $P$ in the order they appear in the input.

For each test case, first print "DATA SET #k", where $k$ is the test case number (starting from $1$).

If no detector absorbed a beam, print "NO BEAMS DETECTED".

Otherwise, print the numbers of the detectors that absorbed a beam (their object numbers from the input) in ascending order, one per line. Even if the same detector absorbs several beams, print its number only once.

Enigma - The Screen Behind The Mirror