Задача G. Generator of palindromes

Автор:A. Baranov   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

Формат входных данных

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

Формат выходных данных

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

В случае если их число равно нулю, на выходе должна быть пустая строка.

Ограничения

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

0 < n ≤ 2 ⋅ 104

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

Стандартный вход Стандартный выход
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.120s 0.021s 15