Краевая олимпиада 2006 I тур - Перепутанные диски

Задача C. Перепутанные диски ≡

задачи
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	Рекомендации	Ограничение времени:	1 сек
Входной файл:	input.txt	Ограничение памяти:	64 Мб
Выходной файл:	output.txt
Максимальный балл:	100

Условие

Вася — страстный любитель компьютерных игр. Его коллекция насчитывает десятки компакт-дисков с играми. Однако он очень неаккуратный мальчик. Коробки с дисками в полном беспорядке раскиданы по его столу, и поэтому найти что-либо на столе практически невозможно.

Когда Вася хочет поиграть в очередную игру, он действует следующим образом: берет произвольную коробку с диском со стола и вставляет диск из этой коробки в CD-привод своего компьютера. Если в CD-приводе уже есть какой-нибудь диск, то вместо того, чтобы найти коробку от этого диска и убрать его туда, Вася убирает диск в коробку, из которой он только что достал очередной диск.

Например, пусть у Васи есть три компакт-диска с играми — "Цивилизация", "Тетрис" и "Сапер". Пусть Вася сначала начал играть в "Цивилизацию", а затем решил поиграть в "Тетрис". Тогда после этого диск с "Цивилизацией" окажется в коробке от "Тетриса". Пусть затем он решил поиграть в "Сапера". Тогда диск от "Тетриса" окажется в коробке от "Сапера". Если после этого он снова решит поиграть в "Цивилизацию" (заметим, что для этого он достанет ее из коробки от "Тетриса"), то игра "Сапер" окажется в коробке от "Тетриса", а "Цивилизация" — в CD-приводе Васиного компьютера.

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

Формат входного файла

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

Формат выходного файла

Выведите в выходной файл k строк, где k — количество различных игр, в которые играл Вася. Каждая строка должна иметь вид "game - box", где game — название игры, а box - название игры, в коробке от которой лежит игра game. Если соответствующая игра лежит в CD-приводе компьютера, вместо box выведите "*" (звездочку). Выводите игры в произвольном порядке.

Ограничения

1 ≤ n ≤ 1000, длина названия не превышает 50 символов.

Примеры тестов

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`4 Civilization Tetris Minesweeper Civilization`	`Civilization - * Tetris - Minesweeper Minesweeper - Tetris`