Дистанционный практикум по программированию

Everybody knows that Windows operating system is a descendant of MS DOS to a certain extent. One of the inherited features is the drive naming system employing capital Latin letters. However, system programmers know that Windows drivers use native, not character names. For example, the file name "C:\Temp\Standard input" may look like this: "\Device\HarddiskVolume1\Temp\Standard input" from a driver's perspective. The operating system uses symbolic links to translate between character and native names. A symbolic link is a named kernel object storing a string inside its body. The OS stores links in system object directory. (Not to be mixed with filesystem directory! The difference is that the object directory is stored in RAM and is rebuilt during each boot). For example, to resolve character name "C:\" the operating system uses two symbolic links: "\DosDevices" (having a value of "\??") and "C:" (located in subdirectory "??" and having a value of "\Device\HarddiskVolume1"). The first link, "\DosDevices", contains the name of a subdirectory where links to character disk names are located, while the second one contains the native name of the device.

The same machinery is used to create additional disks. For example, if we use subst command to create disk "D:" with the path "C:\Temp" then there will be a new link named "D:" and containing string "\??\C:\Temp". As you can see, it is possible to cascade symbolic links.

Write a program that will use a given system link directory to translate a character file name to a native file name. Take into account that link L can be applied to the file name S only if the name of L is an exact prefix of S. Also note that string comparisons are case-insensitive, i. e. names «aaa.txt» and «AaA.tXt» refer to the same file. As all symbolic links to letter devices are always located in a subdirectory pointed to by DosDevices link then:

1.     this link is guaranteed to exist;

2.     the file name must be prepended with it before the transformation: "C:\Temp" Þ "\DosDevices\C:\Temp".

A file name is considered to be in native format if it contains no symbolic links inside its body.

Limitations

1 <= n <= 1000;

1 <= m <= 150;

1 <= Length(L_i, N_i) <= 255. Strings L_i, N_i, S_i contain only Latin letters, decimal digits and the following characters: «\», «.», «:», «_», «#», «?», «@»;

there is no symbolic link with name that is prefix for another symbolic link name;

any symbolic link can be used at most once.

Input

The first line contains two space-delimited integer numbers n and m, where n is the number of symbolic links in the system object directory, m is the number of file names to be translated into native format. Then n lines follow, each containing a description of symbolic links in the following format:

<link name> (N_i) <whitespace> <link value> (L_i).

Link name is always specified using absolute path to the link: for the string "\??\C:" only "C:\" will be the link name.

The rest m lines contain names to be translated (one per line).

Output

The output file consists of m lines, each containing a native name – the result of transformation of the name from the input file. The order of lines in the output file must match the order from the input file.

Samples

Standard input	Standard output
3 5 \DosDevices \?? \??\C: \Device\HarddiskVolume1 \??\D: \??\C:\Temp C:\ D:\ C:\Temp\Standard input D:\Standard input F:\Standard input	\Device\HarddiskVolume1\ \Device\HarddiskVolume1\Temp\ \Device\HarddiskVolume1\Temp\Standard input \Device\HarddiskVolume1\Temp\Standard input \??\F:\Standard input