Problem D. Directory synchronization ≡

Statement

Consider the directory that contains files. Names of these files are composed from Latin letters (uppercase A-Z and lowercase a-z letters are distinct), digits, such characters as '-' (ASCII 45), '.' (ASCII 46) and spaces (ASCII 32). Different files have different names.

Initial content of any file is unique. In future it can not be changed, but it can be copied to a new file.

There is need to periodically synchronize the local version of this directory with its backup copy that is placed on remote server. In this case the previous version of the remote directory must be updated to the current state with minimal computational costs.

For this purpose all operations that are performed in the local directory are stored to in a special log, in historical order. This log contains records in following forms:

• cpy "source" "target" — file "source" was copied to "target";
• mov "source" "target" — file "source" was moved to "target";
• new "target" — file "target" was created;
• del "target" — file "target" was deleted.

It is known that these operations cause error if:

• the source that is specified for cpy or mov does not exist;
• the target that is specified for cpy, mov or new exists;
• the target that is specified for del does not exist.

To update of the remote directory, we must apply similar operations to it. In this case each of them has a certain cost: for mov and del it is 1, cost of cpy is 10.

Also we assume that operation new means to copy a file from the local directory to remote server and has cost is 100.

Your program must, given the initial state of remote directory and set of records of the log, obtain sequence of the operations with minimal total cost that allow to make update of the backup copy to the current state. These operations must not cause errors.

Special file name "~" (ASCII 126) is considered acceptable by remote server, but is not used by operations in the log. It is recommended to use this name for temporary file copies.

Input file format

Input file contains integer N — initial number of files in the directory, followed by the N file names enclosed in double quotes, one name per line.

After that, input file contains integer M — number of the records of the log, followed by M log records, one record per line.

All file names are enclosed in double quotes.

Output file format

Output file must contain integer L — number of the operations, followed by L operations in the same format as log records, one operation per line.

All file names must be enclosed in double quotes.

Constraints

File names have length from 1 to 16 characters. Operations in the log do not cause errors.

0 ≤ N, M ≤ 10⁴

Sample tests

5
"BaNaNa-145"
"Example-01"
"MyMusic-03"
"MyGame.exe"
"UNIT.1.pas"

10
mov "MyMusic-03" "BestMusic.mp3"
mov "MyGame.exe" "F0"
mov "BaNaNa-145" "MyMusic-03"
del "Example-01"
cpy "UNIT.1.pas" "UNIT.2.pas"
del "UNIT.1.pas"
mov "F0" "BaNaNa-145"
new "x2"
mov "BestMusic.mp3" "MyGame.exe"
new "UNIT.1.pas"

8
mov "BaNaNa-145" "~"
mov "MyGame.exe" "BaNaNa-145"
mov "MyMusic-03" "MyGame.exe"
mov "~" "MyMusic-03"
del "Example-01"
mov "UNIT.1.pas" "UNIT.2.pas"
new "x2"
new "UNIT.1.pas"

5
"BaNaNa-145"
"Example-01"
"MyMusic-03"
"MyGame.exe"
"UNIT.1.pas"

10
mov "BaNaNa-145" "BaNaNa-360"
cpy "MyMusic-03" "M0"
cpy "BaNaNa-360" "NaN.InF"
mov "NaN.InF" "BaNaNa-145"
new "x2"
del "BaNaNa-360"
mov "M0" "Music.mp3"
del "MyMusic-03"
mov "Music.mp3" "MyMusic-03"
del "x2"

0