Wikipedia

Time limit2sMemory limit512 MB

Summary

Given n articles with title synonyms and text, wrap every word matching another article's title or synonym in a wiki link, using short form for exact title matches and full form otherwise.

Level: Medium6 of 10
Topics: String, Hash map, Implementation
Solved: No attempts yet

Problem

Inspired by the success of <>, Petya decided to create a similar encyclopedia on his home page. Since Petya is studying English, he decided to make an English version of the encyclopedia.

First he took several texts from <> and typed them in. Now he wants to place links to other articles inside the articles. However, there are very many articles, so he decided to automate the process.

A link to an article on a wiki page looks like this:

[[Article name|link text]].

For example, in the phrase In the wild cats are often enemies of [[Dog|dogs]]. the word <> will be a link to the article <>. If the article name matches the link text, the link can be written simply as

[[Article name]].

For example, in the phrase Growing together a [[dog]] and a cat can often be friends. the word <> will be a link to the article <>. In article names the case of the first letter is ignored, but the case of the remaining letters matters. For example, the word <> can be a link to the article <>, but the word <> cannot.

Help Petya place links on his site. The site is a collection of articles. Each article has a title, one word, and a text. For the title word, all of its word forms and synonyms are known.

We call a word in the text a sequence of English alphabet letters bounded on both sides by characters that are not letters, or by the beginning or end of a line. In the text of an article, you must find all words that are word forms or synonyms of the titles of other articles and turn them into wiki links.

Input

The first line of the input file contains the number $n$ , the number of articles in Petya's Wikipedia ( $2 \le n \le 50$ ). Then the descriptions of the articles follow.

The description of each article begins with a line containing the title of that article. Next comes a line containing a single number $k$ , the number of word forms and synonyms for the article title; this number does not exceed 10. The following $k$ lines contain one word per line, the word forms and synonyms for the title of the current article. Next comes a line containing the number $l$ , the number of lines in the article text; this number does not exceed 10. Then the text of the article follows, $l$ lines, each of length at most 80 characters.

All article titles are distinct. All word forms and synonyms of all titles are distinct and differ from the article titles.

All words consist of Latin alphabet letters, the length of each word in the input file does not exceed 20, and the input file contains only spaces, newlines, and characters with ASCII codes from 32 to 126.

Output

Output to the output file the versions of the articles with the links placed. Output the articles as follows. First output the title of the article. Then output the text of the article, broken into lines in the same way as in the input file. All words in the text that match the title of an article, or a word form or synonym of the title of an article other than the one in which they occur, must be turned into links. When comparing words, ignore the case of the first letter but preserve the case of the remaining letters. Words that match a title must be turned into the short form of the link, and those that do not must be turned into the full form.

Examples1

Example 1

Input

2
Cat
2
Kitten
Cats
3
Cat is one of the most common pets, together with dogs.
In the wild cats are often enemies of dogs.
Growing together a dog and a cat can often be friends.
Dog
1
Dogs
2
Dog is one of the most common pets, together with cats.
DOG can also be an abbreviation.

Expected output

Cat
Cat is one of the most common pets, together with [[Dog|dogs]].
In the wild cats are often enemies of [[Dog|dogs]].
Growing together a [[dog]] and a cat can often be friends.
Dog
Dog is one of the most common pets, together with [[Cat|cats]].
DOG can also be an abbreviation.