The Extent of the Problem

Files on modern filesystems are not always stored contiguously. Instead they are split into chunks called extents, each of which may sit almost anywhere on the underlying disk. An extent occupies one or more contiguous blocks, the unit of the physical disk. Two files never share blocks or extents, though some blocks may sit unused.

Scattering a file's data this way makes access slower than when every block of the file is in order and adjacent (a single extent). For this reason many filesystems support defragmentation: reorganizing files so that each file's blocks are contiguous and in order.

On RAD's Awesome Dynamic Filesystem (RADfs) a file may occupy any number of extents, and every extent consists of at least two adjacent blocks. The first block of an extent stores metadata about that extent; the remaining blocks store part of the file. For example:

RADfs.doc: 37-38,102-114,23-47

Here RADfs.doc occupies 40 blocks on disk ($2 + 13 + 25$), even though the file itself is only 37 blocks of data (each extent contributes one metadata block, so $40 - 3 = 37$). The smallest possible on-disk size is 38 blocks (37 data blocks plus one metadata block), achievable only when the whole file lives in a single extent, for example:

RADfs.doc: 115-152

Now the metadata block (115) is followed by the 37 data blocks in one extent.

The RADfs team also wrote the RADical Defragmentation Daemon (RADDD). Given enough free space, its simple two-step algorithm significantly reduces the number of extents files consume.

A single RADDD pass works as follows.

Step 1 ("to the back"). For every file not yet processed in this step during this pass, taken in ascending order of the first block it currently occupies:

• Find the run of adjacent unused blocks nearest the end of the disk that is large enough to hold the file plus a single metadata block (that is, $(\text{data blocks}) + 1$ contiguous free blocks).
• If such a run exists, move the file into those blocks, placed as close to the end of the disk as possible, and mark its former blocks as unused.
• Otherwise leave the file unchanged.

Step 2 ("to the front"). For every file not yet processed in this step during this pass, taken in descending order of the last block it currently occupies:

• Find the run of adjacent unused blocks nearest the beginning of the disk that is large enough to hold the file plus a single metadata block.
• If such a run exists, move the file into those blocks, placed as close to the beginning of the disk as possible, and mark its former blocks as unused.
• Otherwise leave the file unchanged.

While a file is being relocated, the blocks it currently occupies count as free, since the file is being moved. After a pass, some files may be reduced to a single extent; running more passes can defragment the disk further.

Some files cannot be moved (for example, because they are in use). These are marked immobile and are ignored by RADDD entirely, though the blocks they occupy stay in use.

Given the size of a disk, the current layout of its files, and a number of RADDD passes to run, determine the final layout.

The first line contains an integer $N$ ($1 \le N \le 100$), the number of data sets. Each data set consists of:

• a line with an integer $S$ ($2 \le S \le 100000$), the number of blocks on the filesystem;
• a line with an integer $C$ ($1 \le C \le 100$), the number of files;
• $C$ lines describing the files, each in the form NAME TYPE E A-B[ X-Y ...], where:
  • NAME is an identifier unique within the data set, 1 to 16 lowercase letters;
  • TYPE is I if the file is immobile, or M otherwise;
  • E ($1 \le E \le 20$) is the number of extents the file occupies;
  • A and B ($1 \le A, B \le S$) are the first and last blocks of the first extent;
  • X and Y, if present, are the first and last blocks of the second extent, and so on;
• a line with an integer $P$ ($1 \le P \le 100$), the number of RADDD passes to run.

For each data set, print a line DATA SET #k, where $k$ is 1 for the first data set, 2 for the second, and so on. Then print $C$ lines giving the file layouts after the RADDD passes, in ascending order of the first block each file occupies. Use the same format as the input; when a file occupies multiple extents, list them in ascending order of their first block.