Алиса и Боб играют в игру. Изначально у них есть строка s и её подстрока t. Ход каждого из игроков заключается в приписывании произвольной буквы c_l к t слева и произвольной буквы c_r к t справа таким образом, чтобы t оставалась подстрокой s. Игрок, который не может сделать ход проигрывает.

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

Первая строка входных данных содержит строку s из строчных английский букв (1 ≤ |s| ≤ 10⁵).

Вторая строка входных данных содержит число k (1 ≤ k ≤ 10¹⁰).

Если подходящих вариантов начальной строки t меньше, чем k, выведите “no solution”. В противном случае выведите k-ю лексикографически наименьшую из них. Если ответом является пустая строка, выведите “-” вместо неё.

Выигрышными для s=abac являются строки {-, a, b, ba}.