High School Programming League Problems Archive

A new file system on a disk partition contains only a few small internal structures and one contiguous block of empty space. Once you start to use the system and fill the space with data, creating new files, deleting, truncating, and extending them, this orderly empty space becomes more and more fragmented and the performance of the system drops. This is often called system ageing.

To prevent system ageing and the performance decrease, one might want to defragment the disk surface. You are probably aware of some tools to do so. In this task you will be asked to deal with a simplified version of some of the optimization problems you would meet while constructing such software.

Task

Given the simplified file structure description, try to defragment it using a limited number of copy operations.

Input

In the first line of input you are given two numbers: n - the number of files in the system and m – the number of disk memory allocation blocks.

In the successive n lines, the description of files follows. Each file is described by two strings: FileName (alphanumeric ASCII string, four characters long) and StartingBlock (a hexadecimal four-digit number).

Next, there is an empty line and in the successive m lines, the descriptions of the blocks follow. Each block is described by two strings: BlockData (alphanumeric ASCII string, four characters long) and NextBlock (a hexadecimal four-digit number). The first character of BlockData is either 'U' denoting a used block or 'E' for an empty block. The next three characters of BlockData describe either the essential file data, or just rubbish in the case of empty blocks.

NextBlock redirects to the next block of the file. NextBlock equal to FFFF indicates the last block in the file.

Output

Output one word: NOTHING if you do not want to solve a given test.

Otherwise, first output c – the number of copy operations and in the c following lines, output the appropriate description of the operations. Every copy operation is of the form: Source Destination Predecessor'sType Predecessor.

Source indicates the number of a source block. Destination is the number of a destination block (the destination block must be empty). Predecessor'sType is one character, either 'F' for a file table entry, or 'B' for a block. Predecessor is either the file name or the block number.

Observe that copying of a block affects not only the considered block but also the preceeding block (or the file table in the case of the first block in the file).

At the end of your output print an empty line and the disk structure in the same format as that given in the input.

Scoring

Let us consider two consecutive blocks of the same file, say i is the block number of the first block and j is the position of the next block (NextBlock for i is j). If j is not equal to i+1, the situation is called a jump (the file is fragmented at this point).

The score awarded to your program for a given test is the difference between the Initial number of jumps and the final number of jump, times 10, minus the number of copy operations: 10*(InitJ-FinalJ)-c.

The number of points given in the ranking is scaled so that it is equal to 10 for the registered contestant whose solution has the highest score, and proportionally less for all solutions with lower scores.

An attempt to perform an incorrect operation, such as copying non-existent blocks, using a non-empty block as a destination, inconsistent or invalid disk structure will be judged as Wrong Answer.

Example

Input:
3 12
F001 0003
3aaL 0001
GGhu 000A

EXa3 34EA
UNDO 0002
UNDO FFFF
URea 0007
Eaae 0000
Uool FFFF
E232 0000
Uson 0009
Eeee FE43 
Uing 000B
UYes FFFF 
UIsC 0005

Output:
4
0007 0004 B 0003
0005 0007 B 000B
0009 0005 B 0004
000B 0006 B 0005

3 12
F001 0003
3aaL 0001
GGhu 000A

EXa3 34EA
UNDO 0002
UNDO FFFF
URea 0004
Uson 0005
Uing 0006
UIsC 0007
Uool FFFF
Eeee FE43 
Eing 000B
UYes FFFF 
EIsC 0007

Scoring:
36

Scoring explanation
The initial number of jumps is: 4 
The final number of jumps is: 0
The number of copy operations is: 4
The score is (4-0)*10 - 4 = 36

Input data sizes

 t     n     m    u   l 
 1      4     10    8    2s
 2      4    100    25   2s
 3     26    600   400   2s
 4     87   1140   175   2s
 5    100   7300  2890   2s
 6    110   7310  5890   5s
 7    156    690   410   5s 
 8     31    580   430   5s
 9      6    100    43   5s
10      5     18    16   5s

 t - test set number 
 n - the number of files
 m - the number of blocks
 u - the number of used blocks
 l - time limit

Please note

• Until the last week of the series, all submitted codes will be visible to all users and tested on temporary data sets only.
• For the last week of the series, submissions will be visible to the submitting contestant, only, and tested on the full test sets (all earlier solutions will be rejudged).
• Please do not submit more than 100 times to this problem (all submissions starting with the 101st will be ignored).