Problem G. Generator of palindromes

Author:A. Baranov   Time limit:1 sec
Input file:Standard input   Memory limit:512 Mb
Output file:Standard output  

Statement

A palindrome is a string of characters that reads equally in both directions (left to right and right to left).

Given an arbitrary string S, consider an lexicographically ordered list of all the different palindromes that can be obtained by deleting and rearranging characters in the original string.

It is required to exclude from the specified list those palindromes which are lexicographically less than given string T.
If after that list is still longer than n, the extra palindromes from the end should also be removed.

Input format

The first two lines of the input contain strings S and T, consisting of digits and lowercase letters of the Latin alphabet.
They are followed by an integer n.

Output format

The output must contain all the remaining palindromes in the list in lexicographic order.

If there are none, the output should be an empty string.

Constraints

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

0 < n ≤ 2 ⋅ 104

Sample tests

No. Standard input Standard output
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.083s 0.010s 13