Задача O. Hot-keys

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

Условие

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

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

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

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

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

Входной файл содержит количество заголовков N, за которым следует N строк с названиями заголовков.

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

Выходной файл должен содержать N строк с одинаковыми заголовками, как и во входном файле. В каждом заголовке, которому была назначена какая-то комбинации, перед самым левым вхождением символа из горячей клавиши необходимо добавить символ '&' (ASCII 38).

Ограничения

1 ≤ N ≤ 10, все заголовки имеют длину от 1 до 10 символов и состоят из строчных латинских букв.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
yes
no
cancel
&yes
&no
&cancel
2
4
abc
bca
acb
aaaa
&abc
&bca
a&cb
aaaa

0.107s 0.019s 15