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

Можно привести множество примеров простых слов, в которых большое количество букв: «информатика», «клавиатура», «университет», «строительство», «консерватория», «сковородка», «холодильник», «секундомер», «подоконник», «электричество», «государство», «автомобиль» и другие. Разумеется, этот список можно продолжать до бесконечности.

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

Рассмотрим следующую формальную модель преобразования слов: будем считать, что в разговоре можно использовать n слов. Для каждого слова введем понятие его сокращенного аналога. Сокращенным аналогом произвольного слова s назовем такое слово t, которое удовлетворяет следующим условиям:

• встречается в s в качестве подпоследовательности,
• имеет длину от одного до четырех символов.

Другими словами, слово t состоит хотя бы из одного и не более чем из четырех символов, которые встречаются в том же порядке, но не обязательно подряд, в слове s. Разрешается не сокращать исходное слово, если его длина не превосходит четырех символов.

Вашей задачей является для заданного списка из n различных слов получить набор их сокращенных аналогов. Сокращенные аналоги всех слов из списка должны быть различны.