ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1897. Алиса и Боб и строка

Ограничение времени: 1.0 секунды
Ограничение памяти: 256 МБ
Алиса и Боб играют в игру. Изначально у них есть строка s и её подстрока t. Ход каждого из игроков заключается в приписывании произвольной буквы cl к t слева и произвольной буквы cr к t справа таким образом, чтобы t оставалась подстрокой s. Игрок, который не может сделать ход проигрывает.
Алиса ходит первой. Перед своим первым ходом она может выбрать начальную строку t. Конечно, Алиса хочет сжульничать и выберет такую строку t, которая гарантирует ей победу (в предположении, что оба игрока ходят оптимально), но она не хочет, чтобы Боб что-либо заподозрил. Поэтому Алиса решила выбрать k-ю лексикографически наименьшую строку среди всех возможных выигрышных начальных строк t. Помогите Алисе!

Исходные данные

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

Результат

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

Примеры

исходные данныерезультат
abac
3
b
rndstr
1
-
abc
10
no solution

Замечания

Выигрышными для s=abac являются строки {-, a, b, ba}.
Автор задачи: Александр Кульков
Источник задачи: Петрозаводск лето 2018. Moscow IPT Contest