Question

Best Sequence
Problem Description
Some of the keys of Ajith's Laptop's Keyboard are damaged and he is not able to type those keys. He has to complete his assignment and submit it the next day and since it is midnight he will not be able to give his laptop for repair. So he decides to make a character sequence of all the damaged keys in a sequence that he can copy and paste and make a word out of them.

Ajith needs to type a paragraph with all the characters in lower case. Help Ajith to find out the best permutation of the sequence of the characters (corresponding to the damaged keys) per word, that can be used while typing the paragraph, i.e. the sequence that will require least insertion and deletion while typing a word. Consider paste operation to be of one keystroke. Ignore the copy operation.

Recursively apply the same procedure for all the words in the paragraph. This way you will get the best combination that should be selected for that word. Finally, how many different words exist per character sequence combination. The combination that is the best for maximum words should be printed as output. If there are more than one candidates for best character sequence print the lexicographically smallest character sequence.

Refer the example section for better understanding.

Constraints
0 < Number of words in paragraph < 50

0 < Number of damaged keys <= 6

Input
First line contains the paragraph P that is to be written Second line contains the characters that represent the damaged keys

Output
One Line containing the best string which can be used to copy paste for the words.

Time Limit
1

Examples
Example 1

Input

supreme court is the highest judicial court

s u

Output

su

Explanation

There are two possible combinations of the damaged keys i.e. either su or us.

For word supreme, su is suitable as it requires only paste operation

For court, us is suitable as it requires less keystrokes for deletion

Similarly, for is, su is suitable and so on

Finally, we get su suitable for words supreme, is and highest and us suitable for words court (twice) and judicial. We get su and us suitable for 3 words each.

Since su is lexicographically smaller than us. So, the output will be su.

Example 2

Input

ginnestinggin gniinginging

n i g

Output

gin

Explanation

There are six possible combinations of the damaged keys i.e. {nig, ngi, ing, ign, gni, gin}.

For the first word, gin sequence requires least keystrokes for insertion and deletion. Similarly, for the second word ing sequence requires least keystrokes. Since both are eligible for best sequence, we will need to output the lexicographic

Answer 1

Answer:

can't understand your question please send the question again