Вася — страстный любитель компьютерных игр. Его коллекция насчитывает десятки компакт-дисков с играми. Однако он очень неаккуратный мальчик. Коробки с дисками в полном беспорядке раскиданы по его столу, и поэтому найти что-либо на столе практически невозможно.
Когда Вася хочет поиграть в очередную игру, он действует следующим образом: берет произвольную коробку с диском со стола и вставляет диск из этой коробки в CD-привод своего компьютера. Если в CD-приводе уже есть какой-нибудь диск, то вместо того, чтобы найти коробку от этого диска и убрать его туда, Вася убирает диск в коробку, из которой он только что достал очередной диск.
Например, пусть у Васи есть три компакт-диска с играми — «Цивилизация», «Тетрис» и «Сапер». Пусть Вася сначала начал играть в «Цивилизацию», а затем решил поиграть в «Тетрис». Тогда после этого диск с «Цивилизацией» окажется в коробке от «Тетриса». Пусть затем он решил поиграть в «Сапера». Тогда диск от «Тетриса» окажется в коробке от «Сапера». Если после этого он снова решит поиграть в «Цивилизацию» (заметим, что для этого он достанет ее из коробки от «Тетриса»), то игра «Сапер» окажется в коробке от «Тетриса», а «Цивилизация» — в CD-приводе Васиного компьютера.
Предполагая, что исходно все диски с играми находятся в своих коробках, напишите программу, которая по заданной последовательности игр, в которые играл Вася, определит, в какой коробке окажется после этого каждый из дисков с играми.
Формат входных данных
Первая строка входного файла содержит число n — количество игр, в которые играл Вася (1 ≤ n ≤ 1000), при этом Вася мог играть в одну и ту же игру несколько раз. Следующие n строк содержат названия игр в том порядке, в котором играл Вася. Все названия состоят из латинских букв, цифр и пробелов, длина названия не превышает 50 символов.
Формат выходных данных
Выведите в выходной файл k строк, где k — количество различных игр, в которые играл Вася. Каждая строка должна иметь вид «<game> - <box>», где <game> — название игры, а <box> — название игры, в коробке от которой лежит игра <game>. Если соответствующая игра лежит в CD-приводе компьютера, вместо <box> выведите «*» (звездочку). Выводите игры в произвольном порядке
Примеры входного и выходного файлов
| входные данные |
выходные данные |
4
Civilization
Tetris
Minesweeper
Civilization |
Civilization - *
Tetris – Minesweeper
Minesweeper - Tetris |