Однажды на уроке информатики Аня и Маша прошли лексикографический порядок.

Строка x лексикографически меньше строки y, если либо x является префиксом y (и при этом x ≠ y), либо существует такое i (1 ≤ i ≤ min(|x|, |y|)), что x_i < y_i, и для любого j (1 ≤ j < i) x_j = y_j. Здесь |a| обозначает длину строки a. Лексикографическое сравнение строк реализует оператор < в современных языках программирования.

Учительница задала Ане и Маше домашнее задание. Она выдала им строку длины n. Из этой строки требуется выписать все подстроки, в том числе всю строчку целиком и все одинаковые подстроки (например, из строки «aab» требуется выписать «a», «a», «aa», «ab», «aab», «b»). После этого полученные строки требуется расположить в лексикографическом порядке. А чтобы не проверять все эти строки, хитрая учительница попросила предъявить лишь k-тую строку из этого списка. Помогите Ане с Машей выполнить домашнее задание.