#!/usr/bin/env python

# Defrag
# Phil Bordelon

import os
import sys

DEBUG = os.getenv("DEBUG", False)
ROUND_DEBUG = os.getenv("ROUND_DEBUG", False)

MAX_DISK_SIZE = 100000

# As usual, we use classes as structures.
class Struct(object):

# getEmptyList takes a list representing a map of the blocks on disk
# and returns a list representing the ranges of empty blocks, for use
# with the defragmentation algorithms.
def getEmptyList(disk):
   empty_list = []
   on_empty = False
   start = 0
   end = 0
   for i in range(disk.size):

      # Is this block empty?
      if disk.map[i].empty == True:

         # Are we already tracking a list of empty blocks?
         if on_empty:
            end += 1
            # The first empty block of a new stretch.
            start = i
            end = i
            on_empty = True


         # Were we tracking a list of empty blocks?
         if on_empty:

            # Log it into the empty_list.
            empty_list.append((start, end))
            on_empty = False

         # else pass; we don't care about blocks with files.

   # If the disk ends in empty blocks, we need to append that too.
   if on_empty:
      empty_list.append((start, end))

   if DEBUG:
      print("Empty List: %s" % (repr(empty_list)))

   return empty_list

# convertExtentRanges converts the text extent ranges into tuples
# and sorts them.
def convertExtentRanges(extent_ranges):

   extent_list = []
   for extent in extent_ranges:
      start, finish = [int(x) - 1 for x in extent.split("-")]
      extent_list.append((start, finish))

   return extent_list

# sizeFromExtents returns the size of a file by poking at its extents.
def sizeFromExtents(extents):

   total_size = 0
   for extent in extents:

      # An extent from block 1 to 4 is 4 blocks, not 3.  BUT the metadata
      # block is one of those blocks, and we want the true size.
      total_size += extent[1] - extent[0]

   return total_size

# markExtents marks extents, either clearing them or assigning them to a file.
def markExtents(disk, extents, diskfile, bailIfMarked = False):

   for extent in extents:
      for i in range(extent[0], extent[1] + 1):
         if diskfile:
            if bailIfMarked and not disk.map[i].empty:
               print("ERROR: Attempting to assign block %d to %s, but %s already has it!" % (i, diskfile.name, disk.map[i].file.name))
            disk.map[i].empty = False
            disk.map[i].file = diskfile
            disk.map[i].type = diskfile.type
            disk.map[i].empty = True
            disk.map[i].file = None
            disk.map[i].type = None

# updateDiskMap goes through the list of files and tags all of the
# blocks with whether they are empty or full, along with a pointer
# to the file that resides on them.
def updateDiskMap(disk):

   # First, we clear the disk map.
   markExtents(disk, [(0, disk.size - 1)], None)

   # Now, loop through the files and mark the extents.
   for diskfile in disk.file_list:
      markExtents(disk, diskfile.extents, diskfile, True)

   # For safety's sake, return the map.
   return disk.map

# printDiskMap is a debug function to print a map of the disk.
def printDiskMap(disk):
   for i in range(disk.size):
      if disk.map[i].empty:
         print("%d: empty" % (i + 1))
         thisfile = disk.map[i].file
         print("%d: %s/%s (%d)" % (i + 1, thisfile.name, thisfile.type, thisfile.size))

# updateEmptyList updates the disk's empty list, given a collection of extents
# that have become empty (potentially none), and a different collection of
# extents that are now occupied (potentially none).  These lists must be
# exclusive.
def updateEmptyList(disk, empty_extents, filled_extents):

   # First, make a copy of the current empty list.
   new_list = disk.empty_list[:]

   # Do the easy part first: add the newly empty extents to the list and
   # re-sort.

   # Now we have to coalesce empty space.
   curr_loc = 0
   done = False
   while not done:
      if curr_loc >= len(new_list) - 2:
         done = True

      # We can only coalesce if there's another block after this one.
      elif new_list[curr_loc][1] + 1 == new_list[curr_loc + 1][0]:
         # Coalesce!  Replace this entry and the next with a single new one.
         new_list[curr_loc] = (new_list[curr_loc][0], new_list[curr_loc + 1][1])
         del new_list[curr_loc + 1]

         # We don't want to go further down the list, as this entry may
         # coalesce again with the next one.

         # Increment curr_loc to make sure we end when we should.
         curr_loc += 1

   # Okay, we've coalesced free space.  Now we have to shrink free space
   # available based on the newly occupied bits.  We /used/ to take advantage
   # of the mistaken belief that filled extents are always at the beginning
   # or end of a chunk of free space.  However, after the coalescing we just
   # did, that's not actually the case!
   for extent in filled_extents:
      list_loc = 0
      done = False
      while not done:
         if list_loc >= len(new_list):
            done = True

         elif (extent[0] == new_list[list_loc][0] and
          extent[1] == new_list[list_loc][1]):

            # It occupies the entire free space.  Remove this entry from the list.
            del new_list[list_loc]
            done = True

         elif extent[0] == new_list[list_loc][0]:

            # It fills part of the beginning of this free space block.  Update.
            new_list[list_loc] = (extent[1] + 1, new_list[list_loc][1])
            done = True

         elif extent[1] == new_list[list_loc][1]:

            # It fills part of the end of this free space block.
            new_list[list_loc] = (new_list[list_loc][0], extent[0] - 1)
            done = True

         elif (extent[0] > new_list[list_loc][0] and 
          extent[1] < new_list[list_loc][1]):

            # Ugh.  The filled bits are in the middle of a free space block.
            new_before_block = (new_list[list_loc][0], extent[0] - 1)
            new_after_block = (extent[1] + 1, new_list[list_loc][1])
            del new_list[list_loc]

            # We resort too.

            done = True

            # No match.  Continue down the list.
            list_loc += 1

   # After all of those shenanigans, return the updated list.
   return new_list

# moveFile handles the grotty business of actually moving a file on the disk.
def moveFile(disk, move_file, empty_range, dir):

   # We're going to put it at the beginning or end of the range depending on
   # the direction we're running.
   first_empty, last_empty = empty_range

   if dir == "front":

      # This is the easy one.  The file will now occupy the first blocks in
      # this range.
      new_extents = [(first_empty, first_empty + move_file.size)]
      # Slightly more complicated; it needs to be in the last blocks of the
      # range.  Things are nice and easy thanks to the obligatory metadata
      # block!
      new_extents = [(last_empty - move_file.size, last_empty)]

   # Clear out the old extents ...
   markExtents(disk, move_file.extents, None)

   # And mark the new ones.
   markExtents(disk, new_extents, move_file)

   # We also need to update the empty list.
   disk.empty_list = updateEmptyList(disk, move_file.extents, new_extents)
   # Lastly, assign the file the new extents "on-disk."
   move_file.extents = new_extents

   if DEBUG:
      print("%s moved to %s." % (move_file.name, repr(move_file.extents)))

# getSortedFileList does as the name implies.  It can get it in forward or
# reverse order, as you please.
def getSortedFileList(disk, reverse = False):

   if not reverse:
      file_tuples = [(x.extents[0][0], x) for x in disk.file_list]
      file_tuples = [(x.extents[-1][1], x) for x in disk.file_list]

   return [x[1] for x in file_tuples]

# handlePass handles either pass, depending on what direction it's told to run
# in.
def handlePass(disk, dir):

   # Get a list of either last blocks in files or first blocks in files,
   # sort them and loop.
   if dir == "back":
      file_list = getSortedFileList(disk)
      file_list = getSortedFileList(disk, reverse = True)

   # Loop through those blocks, one at a time.  Each file will only show
   # up once.
   for this_file in file_list:

      # We only care if the file is mobile.
      if this_file.type == "M":

         # A potential file to defrag!  Get the list of free blocks.
         empty_list = disk.empty_list[:]

         # If this is to the back, we need to reverse the empty list,
         # as we want the ones furthest back first.
         if dir == "back":

         # Loop through all of the potential empty locations.
         done = False
         i = 0
         while not done:

            # Get the size of the space.  It's actually one more than
            # this, but we need that one for the metadata ... nice how
            # that works out.
            space_size = empty_list[i][1] - empty_list[i][0]
            if space_size >= this_file.size:

               # Move the file.
               moveFile(disk, this_file, empty_list[i], dir)

               done = True

               i += 1
               if i >= len(empty_list):

                  # Didn't find a spot; the file can't move :|
                  done = True

# run is the big one.
def run(disk, passes):

   # For each pass ...
   for i in range(passes):

      # To the back!
      handlePass(disk, "back")

      if DEBUG:
         print("Pass %d: To the Back" % (i + 1))

      if ROUND_DEBUG:

      # To the front!
      handlePass(disk, "front")

      if DEBUG:
         print("Pass %d: To the Front" % (i + 1))

      if ROUND_DEBUG:

# printDisk prints out the disk contents as the problem asks.
def printDisk(disk):

   # Get the list of files to print in sorted order.
   file_list = getSortedFileList(disk)

   for this_file in file_list:

      # Time to print!
      to_print = ""
      to_print += "%s %s %d" % (this_file.name, this_file.type,
      extent_stringlist = []
      for extent in this_file.extents:
         to_print += " %d-%d" % (extent[0] + 1, extent[1] + 1)


def main():

   dataset_count = int(sys.stdin.readline())

   disk = Struct()

   # Prebuild a maximum-size disk map for speed reasons.
   disk.map = []
   for i in range(MAX_DISK_SIZE):
      disk.map[i].empty = True

   for dataset_loop in range(dataset_count):

      print("DATA SET #%d" % (dataset_loop + 1))
      # Read how many blocks there are.
      disk.size = int(sys.stdin.readline())

      # Fill up the disk map with empty blocks.
      for i in range(disk.size):
         disk.map[i].empty = True

      # Get the count of files.
      disk.file_count = int(sys.stdin.readline())

      disk.file_list = []

      # Read in the files.
      for i in range(disk.file_count):
         new_file = Struct()

         # Get all of the interesting bits out of the line.
         line = sys.stdin.readline().strip()
         line_list = line.split(" ")
         new_file.name, new_file.type = line_list[0:2]
         extent_ranges = line_list[3:]
         new_file.extents = convertExtentRanges(extent_ranges)
         new_file.size = sizeFromExtents(new_file.extents)

         # Append this file to the file list.

      # Now that we've read the files in, update the disk map.
      disk.map = updateDiskMap(disk)

      # Build the starting empty list.
      disk.empty_list = getEmptyList(disk)

      if DEBUG:

      # Read the number of passes to run.
      passes = int(sys.stdin.readline())

      # Run!
      run(disk, passes)

      # Finally, print out the results.

if "__main__" == __name__: