Задача 05C. Сжатый префиксный словарь ≡

Условие

Пусть имеется текстовая строка S, состоящая из цифр и букв латинского алфавита. При этом полагается, что регистр их написания неважен, т.е. заглавные и строчные символы эквивалентны между собой. На основе указанной строки требуется сформировать словарь T, в котором отдельным ее подстрокам ставятся в соответствие некоторые числовые коды. Описание вычислительной процедуры для получения таких кодов приводится ниже:

1. на начальном этапе алгоритма создадим пустой словарь T и заведем счетчик k = 0;
2. будем двигаться по заданной строке, читая ее символы слева направо;
3. находясь в начале очередного суффикса строки S, выберем наименьший непустой его префикс, который отсутствует в словаре T;
4. выбранный на предыдущем этапе префикс добавим в словарь, указав в качестве числового кода его порядковый номер k;
5. увеличим счетчик k на единицу;
6. дальнейший поиск продолжается с позиции, следующей после указанного префикса.

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

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

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

В первой строке входного файла "input.txt" записано натуральное число n.
Далее следует строка S, для которой необходимо построить словарь.

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

В выходной файл "output.txt" нужно вывести все содержащиеся в словаре подстроки, приведенные к одному регистру и расположенные в лексикографическом порядке.
Напротив каждой такой строки (через пробел) следует указать ее порядковый номер.

Ограничения

10 ≤ n ≤ 5000, 0 < |S| ≤ 2 ⋅ 10⁷

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

50
BaNaNAbaNAnaBaNaNAba

a 1
ab 4
aba 9
an 3
ana 5
b 0
ba 7
n 2
na 6
nan 8

10
12uitNp3zxrv45swe6qa

4 2
5 3
6 7
a 9
e 6
q 8
r 0
s 4
v 1
w 5