Задача G. Generator of palindromes ≡

Условие

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

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

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

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

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

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

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

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

Ограничения

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

0 < n ≤ 2 ⋅ 10⁴

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

abcbac
aca
15

aca
acbbca
acbca
acca
b
baab
bab
bacab
baccab
bb
bcaacb
bcacb
bcb
bccb
c

123243
21a
50

22
23132
232
2332
23432
242
3
313
32123
3223
323
32423
33
343
4