#include <functional>
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <map>

using namespace std;

/*
 * DEBUG ONLY: If compiled -DDEBUG, the intermediate state of the disk after
 * each step of the defrag pass is printed to stderr.
 */

/* SANITY CHECK: assertion macro for verifying input data and internal state */
#define ASSERT(e) { if(!(e)) { cerr << #e << endl; throw; } }

/* A single extent represented as a (block, count) tuple. */
typedef pair<int, int> ext_t;
typedef vector<ext_t> extlist_t;

/* Representation of a single file in the data set */
typedef struct {
  string name;           /* File name from data set */
  bool immobile;         /* True if file is immobile */
  int size;              /* Size in blocks of file (not including metadata) */
  int defrag;            /* How many defrag passes has this file been through */
  int print;             /* Number times printed (see output() function) */
  vector<ext_t> extlist; /* List of extents for this file */
} file_t;

/*
 * The extent map tracks all the currently allocated blocks on disk. Individual
 * extents are the keys and they map to the actual file_t structures that own
 * the extent. Since STL maps are sorted, we can use one in ascending order and
 * one in descending to determine the order in which files are processed during
 * the two defrag steps.
 */
typedef map<ext_t, file_t *, bool (*)(ext_t const &,ext_t const &)> extmap_t;

/* Comparison functions for the two extent maps */
bool ascending(ext_t const &a, ext_t const &b)
{
    return a.first < b.first;
}
bool descending(ext_t const &a, ext_t const &b)
{
    return a.second > b.second;
}

/*
 * Print info about all the files on disk. Files are printed in the order that
 * their first extent appears in "first". As each file is printed, its "print"
 * flag is incremented so that if we find another extend in "first" that belongs
 * to this file, then we skip printing that file during this print pass. The
 * extent list for each file is also sorted in ascending order.
 */
void output(ostream &out, extmap_t &first)
{
    static int print_count = 0;
    extmap_t::iterator i;
    extlist_t::iterator j;

    print_count++;
          
    for(i = first.begin(); i != first.end(); ++i) {
        file_t &file = *i->second;
        
        /* Print each file only once per output() call */
        if(file.print == print_count)
            continue;        
        file.print = print_count;
        
        out << file.name << (file.immobile ? " I " : " M ");
        out << file.extlist.size();
                
        /* Print the extent list in numerically ascending order */
        sort(file.extlist.begin(), file.extlist.end());        
        for(j = file.extlist.begin(); j != file.extlist.end(); ++j) {
            out << " " << j->first << "-" << j->second;
        }
        
        out << endl;
    }    
}

/*
 * These are helper functions for use by the generic find_free(). Depending on
 * which order we iterate over the *used* extents, these helpers compute and
 * return the size of the *free* extent that is found between the currently
 * allocated "prev" and "next" extents.
 */
typedef ext_t (*free_helper_t)(ext_t, ext_t);
ext_t first_free(ext_t prev, ext_t next)
{
    return ext_t(prev.second + 1, next.first - 1);
}
ext_t last_free(ext_t prev, ext_t next)
{
    return ext_t(next.second + 1, prev.first - 1);
}

/*
 * These helper functions are for use by defrag() to align "size" blocks either
 * to the front of or the back of the available "free" extent. Here "size" does
 * not include the metadata so these functions account for it.
 */
typedef ext_t (*alloc_helper_t)(ext_t, int);
ext_t to_front(ext_t free, int size)
{
    return ext_t(free.first, free.first + size);
}
ext_t to_back(ext_t free, int size)
{
    return ext_t(free.second - size, free.second);
}

/*
 * Using the sort ordering of the extent map "extmap", find the first or last
 * available extent on the disk that is big enough to hold a file "size"
 * blocks long. The "size" parameter does not include metadata so this
 * function takes it into account. Return "true" if an available extent was
 * found, in which case "free" will contain the available extent.
 *
 * The "initial" and "final" arguments are needed to find the gaps at the very
 * beginning and end of the disk (if N is the number of used extends, there
 * could be N - 1, N, or N + 1 free extents *betweem* the used extents).
 *
 * The "helper" function returns an extent representing the free space between
 * the two already allocated extents "prev" and "next".
 */
bool find_free(extmap_t &extmap, free_helper_t helper,
    ext_t initial, ext_t final, ext_t &free, int size)
{   
    extmap_t::iterator i = extmap.begin();
    ext_t prev;
    
    for(prev = initial; i != extmap.end(); ++i) {
        free = helper(prev, i->first);
        if(free.second - free.first + 1 >= size + 1)
            return true;        
        prev = i->first;
    }
   
    free = helper(prev, final);
    if(free.second - free.first + 1 >= size + 1)
        return true;
       
    return false;  
}

/*
 * Defragment the disk by picking files in order from "first" and putting them,
 * in order, into any free space found between the extents in "last". By calling
 * this function twice but with "first" and "last" reversed, we can do both
 * steps of a defragmentation pass. The "defrag" flag is incremented for
 * each file as we process it since "first" can have multiple extents for the
 * same file, but each file must be processed only once per step/pass.
 */
void defrag(extmap_t &first, extmap_t &last, free_helper_t free_helper,
    alloc_helper_t alloc_helper, ext_t initial, ext_t final)
{
    static int defrag_count = 0;
    extmap_t::iterator i;
    
    defrag_count++;
    
    /* Defragment files in ascending order by their first blocks */
    for(i = first.begin(); i != first.end(); ++i) {
        file_t &file = *i->second;

        /* Defrag each file only once per defrag() call */
        if(file.defrag == defrag_count)
            continue;        
        file.defrag = defrag_count;

        /* Do not attempt moving an immobile file */
        if(file.immobile)
            continue;

        /*
         * Search through the extents in reverse order and try to find an empty
         * spot between allocated extents that's big enough to hold our file.
         * If a free spot was found, move the file info the free spot by
         * updating the file's own extent list and updating the "last" extent
         * map to reflect the new allocation. Note that at this point we
         * cannot update "first" yet because that would invalidate the iterator
         * on it.
         */
        ext_t free;
        if(find_free(last, free_helper, initial, final, free, file.size)) {
            ext_t used = alloc_helper(free, file.size);
            vector<ext_t>::iterator j;
                
            /* Release old file extents from the global "last" map */
            for(j = file.extlist.begin(); j != file.extlist.end(); ++j) {
                last.erase(*j);
            }
            
            /* Allocate new single file extent into the global "last" map */
            last[used] = &file;
            
            /* Update the file's own extent list */
            file.extlist.clear();
            file.extlist.push_back(used);
        }
    }
    
    /* Now we can rebuild "first" map by using the updated "last" map */
    first.clear();
    first.insert(last.begin(), last.end());
}

/* 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 file_idx, file_num;    /* Looping over filenames */
        int ext_idx, ext_num;      /* Looping over file extents */
        int pass_idx, pass_num;    /* Looping over defrag passes */
        int size;                  /* Total size of disk in blocks */
        int passes;                /* How many defrag passes to run */
        vector<file_t> files;      /* Detailed info about each file */
        extmap_t first(ascending); /* Extent map sorted by first block */
        extmap_t last(descending); /* Extent map sorted by last block */
        
        /* Read total disk size */        
        cin >> size;
        ASSERT(2 <= size && size <= 100000);
             
        /*
         * Read count of files and pre-populate "files" vector so that addresses
         * to vector elements are guaranteed to not change because we'll do no
         * further modifications to the vector.
         */
        cin >> file_num;
        ASSERT(1 <= file_num && file_num <= 100);
        files.resize(file_num);
        
        /* Read file info, fill in file_t structures, populate extent maps */   
        for(file_idx = 0; file_idx < file_num; file_idx++) {
            file_t &file = files[file_idx];
            int ext_idx, ext_num;
            char flag;
            
            file.defrag = 0;
            file.print = 0;            
            file.size = 0;
            
            cin >> file.name;
            
            cin >> flag;            
            ASSERT(flag == 'M' || flag == 'I');
            file.immobile = (flag == 'I');
            
            /* Read number of extents and parse extent list */
            cin >> ext_num;
            ASSERT(1 <= ext_num && ext_num <= 20);            
            for(ext_idx = 0; ext_idx < ext_num; ext_idx++) {
                char dummy;     /* To skip over the '-' character */
                ext_t ext;
                
                cin >> ext.first >> dummy >> ext.second;
                ASSERT(1 <= ext.first && ext.first <= size);
                ASSERT(1 <= ext.second && ext.second <= size);
                ASSERT(ext.first <= ext.second);
                
                file.extlist.push_back(ext);
                file.size += ext.second - ext.first;

                first[ext] = &file;
                last[ext] = &file;
            }
        }
        
        /* Print the data set label */
        cout << "DATA SET #" << data_idx + 1 << endl;
#ifdef DEBUG
        cerr << "\nDATA SET #" << data_idx + 1 << endl;
        cerr << "Initial layout:" << endl;
        output(cerr, first);
#endif
       
        /* Perform the requested number of defrag passes */
        cin >> pass_num;
        ASSERT(1 <= pass_num && pass_num <= 100);
        for(pass_idx = 0; pass_idx < pass_num; pass_idx++) {

            defrag(first, last, last_free, to_back,
                ext_t(size + 1, 0), ext_t(0, 0));
#ifdef DEBUG
            cerr << "\nPass " << pass_idx + 1 << " (to the back):" << endl;
            output(cerr, first);
#endif

            defrag(last, first, first_free, to_front,
                ext_t(0, 0), ext_t(size + 1, 0));
#ifdef DEBUG
            cerr << "\nPass " << pass_idx + 1 << " (to the front):" << endl;
            output(cerr, first);
#endif
        }
        
        /* Print the final disk layout */
        output(cout, first);
    }
}

/* Run program and print out any exceptions that occur */
int main(void)
{
    /* Throw exceptions on failed data extraction in >> operator */
    cin.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;
}