#include <math.h>
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <map>

using namespace std;

/*
 * DEBUG ONLY: If compiled -DDEBUG, each data set will produce a file named
 * "lasersN.svg". This is a graphic containing all objects from the input and a
 * trace of the laser beam path.
 */

/* Maximum vertex coordinate value. Used for error checking */
#define MAXPOS 100

/* Values smaller than EPSILON are considered zero to avoid round off errors */
#define EPSILON 0.001

/* A 2D point (or 2D vector) is represented as a pair of doubles */
typedef pair<double, double> point;

/* A line/ray/segment is uniquely defined by two points */
typedef pair<point, point> line;

/* Represents a single mirror, splitter, or detector on the table */
typedef struct {
    char type;    /* Either 'M', 'S', or 'D' */
    int number;   /* Object number (for output display) */
    line pos;     /* Line segment defining the object's position */
} object_t;

/* A dataset consists of an object list */
typedef vector<object_t> dataset;

/* DEBUG ONLY: Current .svg file being drawn for this data set */
ofstream svgout;
        
/* SANITY CHECK: Max number of reflections allowes per dataset */
#define MAXREFLECT 100

/* SANITY CHECK: Current running total of reflection in this dataset */
int reflectcount;

/*
 * The resultset is a list of detector numbers that were hit by a laser.
 * Using a map automatically eliminates duplicates and keeps the results
 * in sorted order by object number, which is needed for final program
 * output
 */
typedef map<int, bool> resultset;

/* Adding/Subtracting 2D points/vectors together adds/subtracts dimensions */
inline point operator+(point const &a, point const &b) {
    return point(a.first + b.first, a.second + b.second);
}
inline point operator-(point const &a, point const &b) {
    return point(a.first - b.first, a.second - b.second);
}

/* Multiplying by a scalar, simply scales length of the vector */
inline point const operator*(double i, point const &o) {
    return point(i * o.first, i * o.second);
}

/* Multiplying 2D vectors together computes dot product */
inline double operator*(point const &a, point const &b)
{
    return (a.first * b.first) + (a.second * b.second);
}

/* Normalize vector p to unity length */
inline point norm(point const &p)
{
    double magnitude = sqrt(p.first * p.first + p.second * p.second);
    return point(p.first / magnitude, p.second / magnitude);
}

/* The ~ is a "perp operator". Rotates vector 90 degrees to the left */
inline point operator~(point const &a)
{
    return point(-a.second, a.first);
}

/* Extraction operator for a 2D point reads coordinates of the form "x,y" */
istream &operator>>(istream &in, point &p)
{
    char c; /* Dummy variable to skip past the comma "," */

    /* Parse the coordinate points */
    cin >> p.first >> c >> p.second;
    
    return in;
}

/*
 * Computes the intersection between a line segment "p" and a ray "q" and
 * returns the parametric values for the two vector equations at the
 * intersection point. The line "p" consists of its two endpoints and ray "q"
 * consists of one endpoint (q.first) and a direction vector (q.second).  If
 * the line segment parametric value is between 0 and 1, then the intersection
 * occurs within the line segment (otherwise the line intersects but not the
 * segment). Likewise, if the ray parametric value is greater than 0, then the
 * ray intersects (the ray extends only in one direction while a line extends
 * in both).
 *
 * For reference see:
 * http://www.geometryalgorithms.com/Archive/algorithm_0104/algorithm_0104B.htm
 * http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
 */
point intersect(line const &p, line const &q)
{
    point param;

    /* The ray already includes a direction vector */
    point u = p.second;

    /* Compute the w and v vectors and common denominator */
    point w = p.first - q.first;
    point v = q.second - q.first;
    double denom = ~v * u;
    
    /* Compute the parametric value for each line at point of intersection */
    param.first = (~w * v) / denom;
    param.second = (~u * w) / -denom;
    
    return param;
}

/*
 * Given a laser direction (as a unity vector) and a line segment representing
 * the mirror surface, return the direction of the reflected laser beam.
 *
 * Using dot products, it is possible to split the laser beam direction vector
 * into two independent vectors: one tangent to the mirror surface and one
 * perpendicular (or normal) to it. The tangent component is not affected by
 * the reflection and the normal component is simply flipped. The two components
 * are then recombined to give the new reflected direction.
 */
point reflect(point const &laser_dir, line const &mirror)
{
    /* Convert mirror line segment into a vector direction */
    point mirror_dir = mirror.second - mirror.first;

    /* Split laser direction into tangent and normal components to mirror */
    point tangent = (laser_dir * mirror_dir) * mirror_dir;
    point normal = (laser_dir * ~mirror_dir) * ~mirror_dir;
    
    /* Flip normal component, recombine with tangent, normalize new direction */
    return norm((-1 * normal) + tangent);
}

/* If in debug mode, dump out all objects and laser start to .svg file */
void dump_header(int data_idx, dataset &input, point &start)
{
#ifdef DEBUG
    /* Create a filename based on the current data set number */
    ostringstream filename;
    filename << "lasers" << data_idx + 1 << ".svg";
    
    /* Open the .svg file overwriting any existing files with the same name */
    svgout.open(filename.str().c_str(), ios::trunc);

    /* Write out XML and SVG boilerplate */    
    svgout <<
    "<?xml version='1.0' standalone='no'?>\n"
    "<svg width='100' height='100'\n"
    "xmlns='http://www.w3.org/2000/svg'\n"
    "xmlns:xlink='http://www.w3.org/1999/xlink'>\n"
    "\n"
    "<!-- auto generated with lasers.cpp; view with Inkscape -->\n"
    "\n"
    "<!-- style and marker definitions -->\n"
    "<defs>\n"
    "<style type='text/css'>\n"
    "  text    { font-size: 3px; }\n"
    "  .table  { fill: none; stroke: black; stroke-width: 0.5; }\n"
    "  .laser  { stroke: red; marker-end: url(#arrow); }\n"
    "  .object { stroke: black; }\n"
    "  .marker { fill: red; }\n"
    "</style>\n"
    "<marker orient='auto' id='arrow' class='marker'>\n"
    "  <path transform='scale(0.4) rotate(180) translate(10,0)'\n"
    "    d='M 0.0,0.0 L 5.0,-5.0 L -12.5,0.0 L 5.0,5.0 L 0.0,0.0 z'\n"
    "  />\n"
    "</marker>\n"
    "</defs>\n"
    "\n"
    "<!-- table edges -->\n"
    "<rect x='0' y='0' width='100' height='100' class='table'/>\n"    
    "\n"
    "<!-- laser starting point -->"
    << endl;
    
    /* Draw a circle to mark the starting laser point */
    svgout <<
    "<circle r='2' class='marker' " <<
    "cx='" << start.first << "' cy='" << start.second << "'/>\n" << endl;
    
    /* Dump out all of the objects */
    svgout << "<!-- input objects -->" << endl;
    for(int i = 0; i < input.size(); i++) {         
        object_t &o = input[i];
        line &l = o.pos;
        ostringstream id;
        
        /* The object type and number is used as a unique label in graphic */
        id << o.type << o.number + 1;
                
        /* Draw the line segment representing object */
        svgout <<
        "<line x1='" << l.first.first   << "' y1='" << l.first.second  << "' "
              "x2='" << l.second.first  << "' y2='" << l.second.second << "' "
              "class='object' id='" << id.str() << "'/>\n"
        
        /* Draw text label flowing along the line segment path */
        "<text><textPath xlink:href='#" << id.str() << "'><tspan>" << id.str() <<
        "</tspan></textPath></text>" << endl;
    }
    
    /* Write out boiler plate for laser path drawing */
    svgout << "\n<!-- laser paths -->" << endl;
    
#endif
}

/* Show laser beam path as a line segment going from l.first to l.second */
void dump_laser(line const &l)
{
#ifdef DEBUG
    svgout <<
    "<line x1='" << l.first.first   << "' y1='" << l.first.second  << "' "
          "x2='" << l.second.first  << "' y2='" << l.second.second << "' "
          "class='laser'"
    "/>" << endl;
#endif
}

/* If in debug mode, write SVG trailer and close current svg file */
void dump_trailer(void)
{
#ifdef DEBUG
    svgout << "\n</svg>" << endl;
    svgout.close();
#endif
}

void raytrace(line laser, dataset &input, resultset &output)
{
    /* Keep tracing laser paths until beam hits a mirror or exit table area */
    for(;;) {
    
        /* SANITY CHECK: Check if total number of reflections exceeded */
        if(reflectcount > MAXREFLECT) {
            cerr << "Total reflection count exceeded" << endl;
            throw;
        }

        /* Laser beam vector equation param of closest intersecting object */
        double minparam = -1;

        /* The closest object intersected by the laser beam */
        object_t obj;

        /* Coordinate point at which laser intersects "obj" */
        point endpoint;

        /* Check laser beam intersection with any of the data set objects */
        for(int i = 0; i < input.size(); i++) {

            /* Compute vector equation parameters for intersection point */
            point p = intersect(laser, input[i].pos);

            /* Check if laser beam ray intersected object line segment */
            if(p.first > EPSILON && p.second > 0 && p.second < 1) {

                /* Remember object if it is in front of others on laser path */
                if(minparam == -1 || p.first < minparam) {
                    minparam = p.first;
                    obj = input[i];
                    endpoint = laser.first + (p.first * laser.second);
                }
            }
        }

        /* If no objects intersected, then laser left table; stop raytracing */
        if(minparam == -1) {
            /* DEBUG ONLY: show laser beam exiting the table */
            dump_laser(line(laser.first, laser.first + 100 * laser.second));
           
            break;
        }

        /* If laser beam intersects another object, continue tracing */
        else {
            /* DEBUG ONLY: print laser beam path leading up to object */
            dump_laser(line(laser.first, endpoint));
            
            /* If mirror is hit, compute reflected ray and continue tracing */
            if(obj.type == 'M') {
                laser = line(endpoint, reflect(laser.second, obj.pos));
                reflectcount++; /* SANITY CHECK */
            }
            
            /* If splitter hit, continue tracing both rays */
            else if(obj.type == 'S') {
            
                /* Recursively trace laser beam passing through splitter */
                raytrace(line(endpoint, laser.second), input, output);

                /* Iteratively trace reflected beam */
                laser = line(endpoint, reflect(laser.second, obj.pos));
                reflectcount++; /* SANITY CHECK */
            }

            /* If detector object is hit, record it and stop raytracing */
            else {
                output[obj.number] = true;
                break;
            }            
        }
    }
}

/* Main body of program */
void process(void)
{
    int data_num, data_idx;

    /* Read how many data sets to process */
    cin >> data_num;
    
    /* Process each data set separately */
    for(data_idx = 0; data_idx < data_num; data_idx++) {
        int obj_num, obj_idx;

        dataset input;      /* List of objects on the table */
        resultset output;   /* List of detectors hit by laser */
        line laser;         /* Initial laser position and direction */

        /* Read in the initial laser position and direction */
        cin >> laser.first;
        cin >> laser.second;
        
        /* Normalize the laser's initial direction vector */
        laser = line(laser.first, norm(laser.second));

        /* Read how many objects exist in this data set */
        cin >> obj_num;
        
        /* Read in each object description */
        for(obj_idx = 0; obj_idx < obj_num; obj_idx++) {
            object_t obj;

            /* Objects are numbered in the order they are read in */
            obj.number = obj_idx;
            
            /* Read object type and location */
            cin >> obj.type >> obj.pos.first >> obj.pos.second;
            
            /* Add the object to the data set list */
            input.push_back(obj);
        }
        
        /* If in debug mode, create the .svg file and dump all objects */
        dump_header(data_idx, input, laser.first);

        /* SANITY CHECK: Reset the total reflection count */
        reflectcount = 0;
        
        /* Begin ray tracing from laser origin */
        raytrace(laser, input, output);
        
        /* If in debug mode, close the .svg file */
        dump_trailer();

        /* Print out the object number of each detector hit */
        cout << "DATA SET #" << data_idx + 1 << endl;        
        
        /* If at least one detector hit, print out their object numbers */
        if(output.size()) {
            resultset::iterator i;
            for(i = output.begin(); i != output.end(); ++i) {
                cout << i->first + 1 << endl;
            }
        }
        
        /* If no detectors hit, then print a message to that effect */
        else {
            cout << "NO BEAMS DETECTED" << endl;
        }
        
        /* TODO: Need to count for maximum reflection */
    }
}

/* Run program and print out any exceptions that occur */
int main(void)
{
    /* Throw exceptions on EOF or failed data extraction in >> operator */
    cin.exceptions(ios::eofbit | ios::failbit);
    svgout.exceptions(ios::failbit);
    
    /* Run main body of code */
    try {
        process();
    }
    
    /* Catch unexpected EOF or bad input data */
    catch(ios::failure const &e) {
        cerr << "Unexpected EOF or data type mismatch on input" << endl;
    }

    return 0;
}