eolymp
bolt
Try our new interface for solving problems
Problems

Википедия

Википедия

Time limit 1 second
Memory limit 64 MiB

Воодушевленный успехом "Википедии", Петя решил создать аналогичную энциклопедию на своей домашней странице. Поскольку Петя изучает английский язык, он решил сделать английскую версию энциклопедии.

Для начала он взял несколько текстов из "Encyclopedia Britannica" и набрал их. Теперь он хочет расставить внутри статей ссылки на другие статьи. Однако статей очень много, поэтому он решил автоматизировать процесс.

Ссылка на статью на вики-странице устроена следующим образом:

"[[Название статьи|текст ссылки]]".

Например, во фразе "In the wild cats are often enemies of [[Dog|dogs]]." слово "dogs" будет ссылкой на статью "Dog". Если название статьи совпадает с текстом ссылки, можно ссылку можно оформить просто как

"[[Название статьи]]".

Например, во фразе "Growing together a [[dog]] and a cat can often be friends." слово "dog" будет ссылкой на статью "dog". При этом в названиях статей регистр первой буквы игнорируется, а регистр остальных букв важен. Например, слово "dog" может быть ссылкой на статью "Dog", а слово "DOG" — нет.

Помогите Пете расставить ссылки на его сайте. Сайт представляет собой множество статей. Каждая статья имеет название — одно слово, и текст. Для слова названия известны все его словоформы и синонимы.

Будем называть словом в тексте последовательность букв английского алфавита, ограниченную с обеих сторон символами, не являющимися буквами, либо началом или концом строки. В тексте статьи требуется найти все слова, которые являются словоформами или синонимами названий других статей и превратить их в вики-ссылки.

Input data

Первая строка входного файла содержит число n — количество статей в Петиной википедии (2n50). Далее следуют описания статей.

Описание каждой статьи начинается со строки, которая содержит название этой статьи. Далее следует строка, содержащая одно число k — количество словоформ и синонимов к названию статьи, это число не превышает 10. Следующие k строк содержат по одному слову на строке — словоформы и синонимы к названию текущей статьи. Далее следует строка, содержащая число l — количество строк в тексте статьи, это число не превышает 10. Затем следует текст статьи — l строк, каждая из которых имеет длину не более 80 символов.

Все названия статей различны. Все словоформы и синонимы всех названий различны и отличаются от названий статей.

Все слова состоят из букв латинского алфавита, длина каждого слова во входном файле не превышает 20, во входном файле встречаются только пробелы, переводы строк и символы с ASCII кодами от 32 до 126.

Output data

Выведите в выходной файл версии статей с расставленными ссылками. Выводите статьи следующим образом. Сначала выведите название статьи. Затем выведите текст статьи, разбитый на строки также как и во входном файле. Все слова в тексте, которые совпадают с названием статьи, или со словоформой или синонимом названия статьи, отличной от той, в которой они встречаются, следует превратить в ссылки. При сравнении слов следует игнорировать регистр первой буквы, но соблюдать регистр остальных. Слова, совпадающие с названием, следует превратить в краткую версию ссылки, а не совпадающие — в полную.

Examples

Input example #1
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.
Output example #1
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.
Author Андрей Станкевич