Schottkey 7th Path

문제

일반적인 운영체제에서 파일 시스템은 여러 디렉터리로 이루어지며, 그 안에 파일들이 들어 있습니다. 각 파일에는 보통 절대 경로(예: /usr/games/bin/kobodl)라고 불리는 표준 위치가 있으며, 사용자가 시스템의 어디에 있든 이 경로로 파일을 가리킬 수 있습니다.

대부분의 환경에서는 위치를 일일이 지정하지 않고도 다른 디렉터리의 파일을 참조할 수 있습니다. 이를 위해 흔히 PATH 같은 변수에 검색할 위치들의 순서 있는 목록을 저장합니다. 이 문제에서 각 위치는 모두 절대 경로로 주어지며, 이 순서 있는 목록을 검색 경로(search path)라고 부릅니다.

새로 만들어진 crash 셸에서는 파일 이름을 평소보다 더 친절하게 찾아 줍니다. 사용자가 어떤 파일 이름을 요청하면 crash는 다음 과정을 따릅니다.

요청한 이름과 정확히 일치하는 파일이 있으면 그 파일을 반환합니다. 검색 경로에서 더 앞선 위치의 정확한 일치가 우선합니다. (한 위치 안에는 같은 이름의 파일이 중복으로 존재하지 않습니다.)
정확히 일치하는 파일이 없으면, 여분의 문자가 정확히 하나 더 있는 이름을 찾습니다. 여분의 문자는 어느 위치에나 올 수 있지만, 나머지 문자들의 순서는 요청한 이름과 똑같아야 합니다. 이때도 더 앞선 위치가 우선하며, 일치가 발견된 가장 높은 우선순위 위치에 그런 파일이 여러 개 있으면 그 위치의 모든 파일을 반환합니다.
정확한 일치도, 여분 문자 하나짜리 일치도 없으면, 여분의 문자가 정확히 두 개 더 있는 파일을 같은 우선순위·다중 일치 규칙으로 찾습니다.
위 세 가지 중 어느 것에도 해당하는 파일이 없으면 아무것도 반환하지 않습니다. crash 셸에서 "관대함"의 한계는 여분 문자 두 개입니다.

예를 들어 파일 bang과 tang은 각각 이름 ang과는 한 글자 차이, ag와는 두 글자 차이입니다. (이 문제의 모든 문자는 소문자입니다.)

시스템의 모든 위치와 그 안의 파일 목록, 각자 자신의 순서 있는 검색 경로를 가진 사용자들, 그리고 사용자들이 찾고자 하는 파일 이름들이 주어질 때, crash가 어떤 파일 이름을 반환하는지 구하세요.

문제를 단순화하기 위해 모든 위치는 하나의 알파벳 문자열로 표현되며, 파일 이름과 사용자 이름도 마찬가지입니다. 실제 운영체제 경로는 슬래시 같은 문자로 구분된 여러 요소로 이루어지는 경우가 많지만, 이 문제에서는 그렇지 않습니다. 또한 사용자가 실수로 존재하지 않는 위치를 검색 경로에 넣을 수도 있는데, 그런 위치에는 당연히 파일이 하나도 없습니다.

입력

입력의 모든 알파벳 문자열은 길이가 1 이상 20 이하이며, 슬래시나 공백 같은 특수 문자를 포함하지 않고, 모두 소문자로만 이루어집니다.

입력의 첫 줄에는 데이터 집합의 개수를 나타내는 정수 $N$ ($1 \le N \le 100$)이 주어집니다. 각 데이터 집합은 다음으로 구성됩니다.

시스템의 파일 개수를 나타내는 정수 $F$ ($1 \le F \le 100$)가 한 줄에 주어집니다.
파일을 나타내는 $F$개의 줄이 이어지며, 각 줄은 location filename 형식입니다. location과 filename은 모두 알파벳 문자열입니다.
사용자 수를 나타내는 정수 $U$ ($1 \le U \le 10$)가 한 줄에 주어집니다.
사용자를 나타내는 $U$개의 단락이 이어집니다. 각 단락은 다음으로 구성됩니다.
- 사용자 이름인 알파벳 문자열이 한 줄에 주어집니다.
- 사용자의 검색 경로에 있는 위치의 개수를 나타내는 정수 $L$ ($1 \le L \le 10$)이 한 줄에 주어집니다.
- 검색 경로의 위치를 나타내는 $L$개의 줄이 이어지며, 각 줄에 알파벳 문자열이 하나씩 주어집니다. 첫 번째가 가장 높은 우선순위이고, 두 번째가 그다음, 이런 식으로 이어집니다.
실행할 검색의 개수를 나타내는 정수 $S$ ($1 \le S \le 200$)가 한 줄에 주어집니다.
검색을 나타내는 $S$개의 줄이 이어지며, 각 줄은 username filename 형식입니다. username은 이 데이터 집합에 정의된 사용자 중 하나와 일치하고, filename은 요청하는 파일 이름입니다.

출력

각 데이터 집합에 대해 먼저 제목 DATA SET #k를 출력합니다. 여기서 k는 첫 번째 데이터 집합이면 1, 두 번째면 2와 같이 매겨집니다. 그다음, 각 데이터 집합의 $S$개 검색에 대해 (입력에서 읽은 순서대로) 다음을 수행합니다.

username REQUESTED filename 줄을 출력합니다. 여기서 filename은 username이 요청한 파일 이름입니다.
이 검색에 일치하는 각 파일(있는 경우)에 대해 FOUND filename IN location 줄을 출력합니다. 여기서 filename은 일치한 파일이고 location은 그 파일이 발견된 위치입니다. 이 줄들은 파일 이름의 알파벳 순으로 정렬되어야 합니다.