SCUSA Region ACM Balloon Logo ICPC Masthead
2007 South Central USA Regional Programming Contest

Schottkey 7th Path

Introduction:

With a typical operating system, a filesystem consists of a number of directories, in which reside files. These files generally have a canonical location, known as the absolute path (such as /usr/games/bin/kobodl), which can be used to refer to the file no matter where the user is on a system.

Most operating system environments allow you to refer to files in other directories without having to be so explicit about their locations, however. This is often stored in a variable called PATH, and is an ordered list of locations (always absolute paths in this problem) to search for a given name. We will call these search paths.

In the brand-new crash shell, paths are handled somewhat differently. Users still provide an ordered list of locations that they wish to search for files (their search paths); when a particular filename is requested, however, crash tries to be even more helpful than usual. The process it follows is as follows:

So, for example, given the two files bang and tang, they are both one character away from the filename ang and two from ag. (All characters in this problem will be lowercase.) In the sample data below, both cat and rat are one character away from at.

Given a complete list of locations and files in those locations on a system, a set of users each with their own ordered lists of search paths, and a set of files that they wish to search for, what filenames would crash return?

For the purposes of simplification, all locations will be described by a single alphabetic string, as will filenames and usernames. Real operating system paths often have many components separated by characters such as slashes, but this problem does not. Also note that users may accidentally refer to nonexistent locations in their search paths; these (obviously) contain no files.

Input:

All alphabetic strings in the input will have at least one and at most 20 characters, and will contain no special characters such as slashes or spaces; all letters will be lowercase.

Input to this problem will begin with a line containing a single integer N (1 ≤ N ≤ 100) indicating the number of data sets. Each data set consists of the following components:

Output:

For each data set in the input, output the heading "DATA SET #k" where k is 1 for the first data set, 2 for the second, etc. Then for each of the S searches in the data set (and in the same order as read from the input) do the following:

Sample Input:

1
4
food oat
food goat
animal rat
animal cat
2
bob
2
food
animal
bill
1
animal
4
bob at
bob cat
bill goat
bill at

Sample Output:

DATA SET #1
bob REQUESTED at
FOUND oat IN food
bob REQUESTED cat
FOUND cat IN animal
bill REQUESTED goat
bill REQUESTED at
FOUND cat IN animal
FOUND rat IN animal