Schottkey 7th Path

On a typical operating system, a filesystem consists of directories in which files reside. Each file generally has a canonical location, known as its absolute path (such as /usr/games/bin/kobodl), which refers to the file no matter where the user currently is on the system.

Most environments also let you refer to files in other directories without stating their full location. This is usually done through an ordered list of locations to search, commonly stored in a variable such as PATH. In this problem every such location is given as an absolute path, and we call this ordered list a search path.

In the brand-new crash shell, filename lookup is handled more helpfully than usual. When a user requests a filename, crash follows this process:

• If some file exactly matches the requested filename, it is returned. Exact matches in locations earlier in the search path are preferred. (Within a single location there are no duplicate filenames.)
• If there is no exact match, crash looks for filenames that contain exactly one extra character. The extra character may appear at any position, but the remaining characters must appear in the same order as in the requested filename. Again, matches in earlier locations are preferred; if the highest-ranked location with a match contains several such files, all of them are returned.
• If there is neither an exact match nor a one-extra-character match, crash looks for filenames with exactly two extra characters, using the same precedence and multiple-match rules.
• If no file satisfies any of the three cases above, nothing is returned. Two extra characters is the limit of "permissiveness" for the crash shell.

For example, the files bang and tang are each one character away from the filename ang and two characters away from ag. (Every character in this problem is lowercase.)

Given the complete list of locations and the files in them, a set of users each with their own ordered search path, and a set of filenames the users wish to look up, determine which filenames crash returns.

For simplicity, every location is described by a single alphabetic string, as are filenames and usernames. Real operating-system paths often have several components separated by characters such as slashes, but this problem does not. Note also that a user may accidentally list a nonexistent location in their search path; such a location obviously contains no files.

Every alphabetic string in the input has between 1 and 20 characters, contains no special characters such as slashes or spaces, and consists only of lowercase letters.

The input begins with a line containing a single integer $N$ ($1 \le N \le 100$), the number of data sets. Each data set consists of the following:

• A line with a single integer $F$ ($1 \le F \le 100$), the number of files on the system.
• $F$ lines describing the files, each in the format location filename, where location and filename are alphabetic strings.
• A line with a single integer $U$ ($1 \le U \le 10$), the number of users.
• $U$ user stanzas. Each stanza consists of:
  • A line with a single alphabetic string, the username.
  • A line with a single integer $L$ ($1 \le L \le 10$), the number of locations in the user's search path.
  • $L$ lines, each a single alphabetic string, listing the locations in the search path from highest priority to lowest.
• A line with a single integer $S$ ($1 \le S \le 200$), the number of searches to run.
• $S$ lines describing the searches, each in the format username filename, where username matches one of the users defined in this data set and filename is the requested filename.

For each data set, output the heading DATA SET #k, where k is 1 for the first data set, 2 for the second, and so on. Then, for each of the $S$ searches (in input order), do the following:

• Print username REQUESTED filename, where filename is the file requested by username.
• For each file (if any) that matches the search, print FOUND filename IN location, where filename is the matching file and location is where it was found. These lines must be sorted in alphabetical order by filename.