Задача A. Имена файлов ≡

Условие

I wish we had some way to handle it sanely, but I don't think a sane solution to case-insensitivity exists.

Linus Torvalds

На компьютере под управлением операционной системы Linux имеется каталог, содержащий N файлов. Пользователю требуется скопировать эти файлы на компьютер, работающий под управлением ОС Windows. К сожалению, файловая система Windows имеет странное свойство. Несмотря на то, что она сохраняет большие и малые буквы в именах файлов, имена, отличающиеся только регистром букв, считаются одинаковыми. Например, файлы с именами ChangeLog, CHANGELOG и changelog при копировании на файловую систему Windows попадут в один и тот же файл.

Чтобы избежать потери данных, предлагается при копировании переименовывать файлы по следующим правилам:

1. Файлы копируются в порядке перечисления в исходном каталоге.
2. Имена файлов считаются одинаковыми, если они совпадают с точностью до регистра.
3. Если при копировании очередного файла выяснилось, что файл с таким именем уже был скопирован, то к имени текущего файла добавляется суффикс "1".
4. Если имя, полученное после присоединения суффикса, также уже встречалось, то перебираются суффиксы "2", "3", ..., "10", "11", ... до тех пор, пока не найдётся суффикс, дающий уникальное имя.

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

Входной файл содержит количество имён N, за которым следует N строк с именами. Имена состоят из латинских букв и цифр и имеют длину от 1 до M символов.

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

Выходной файл должен содержать N строк с модифицированными именами файлов.

Ограничения

1 ≤ N ≤ 10000, 1 ≤ M ≤ 255

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

4
aA
Aa
aa
AA1

aA
Aa1
aa2
AA11

Разбор

Тривиальное решение задачи можно получить буквальным воспроизведением алгоритма, описанного в условии. Если при этом проверку наличия файла с данным именем реализовать линейным поиском, то получим решение сложностью O(N³ × M) операций, которое может пройти небольшие тесты.

Линейный поиск может быть заменён эффективной структурой данных, например хешем или сбалансированным деревом. В таком случае сложность снизится до O(N² × M) либо O(N² log N × M) операций, что достаточно для прохождения средних тестов.

Заметим, что наиболее проблематичными для последнего решения являются тесты, содержащие большое число одинаковых (с точностью до регистра) имён файлов. Чтобы не повторять для каждого такого имени попытки переименования в "имя1", "имя2" и т. д., будем для каждого файла хранить первый ещё не проверявшийся числовой суффикс. Таким образом амортизированная сложность алгоритма снизится до O(N × M), что позволит пройти все тесты.

В случае, если используемый язык программирования (например, Pascal) не содержит эффективного контейнера в качестве встроенного типа либо элемента стандартной библиотеки, можно заменить его двоичным поиском по предварительно отсортированному массиву имён. При этом для каждого искомого имени следует рассматривать все имена, состоящие из искомого с добавлением числового суффикса.