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

Условие

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

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

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

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

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

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

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

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

Ограничения

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