Задача N. Генератор палиндромов

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

Палиндромом называется строка символов, которая одинаково читается в обоих направлениях (слева направо и справа налево).

Пусть имеется произвольная строка S. Рассмотрим упорядоченный список всех различных палиндромов,
которые могут быть получены через операции удаления и перестановки символов в исходной строке.

Из указанного списка требуется исключить палиндромы, лексикографический порядок которых меньше, чем у некоторой заданной строки T.
Если после этого его длина окажется больше n, лишние (с конца) палиндромы также следует удалить.

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

В заголовке входного файла "input.txt" содержатся две строки S и T, состоящие из цифр и строчных букв латинского алфавита.
За ними следует натуральное число n.

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

Выходной файл "output.txt" должен содержать все оставшиеся палиндромы, расположенные в лексикографическом порядке.

В случае если их число равно нулю, выходной файл следует оставить пустым.

Ограничения

0 < |T| ≤ |S| ≤ 100,

0 < n ≤ 2 ⋅ 104

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

Входной файл (input.txt) Выходной файл (output.txt)
1
abcbac
aca
15
aca
acbbca
acbca
acca
b
baab
bab
bacab
baccab
bb
bcaacb
bcacb
bcb
bccb
c
2
123243
21a
50
22
23132
232
2332
23432
242
3
313
32123
3223
323
32423
33
343
4

0.066s 0.015s 15