It’s the year of 2031. The long expected singularity point came, and
computers rose against people. The only hope of the mankind is intelligent
genetically modified war organisms that took our part in the conflict.
Naturally, the machines never stop developing and they keep creating
deadlier and deadlier robots. People keep looking for new DNA sequences to
make the mutants stronger and tougher.
For example, Professor Yerfalomeus
Ben has recently revealed that we can compare the mutants’ strengths only
if we know their DNA.
For that purpose, both DNA sequences should be written as strings of small
English letters (the scientists of the future quickly run out of the four
nitrogenous bases and they had to introduce new ones).
Mutant X is stronger than mutant Y, if the DNA sequence of mutant X
is lexicographically smaller of the DNA sequence of mutant Y.
Now professor Ben wants to make an experiment.
He has a DNA of some mutant and a set of gene modifiers in the lab.
A gene modifier is a substance that can change a DNA.
Each gene modifier is described by a small English
letter. Professor Ben can take gene modifiers from the set in any order
and perform one of the following actions with each of them.
- Insert a gene modifier into any place of the DNA sequence (between
the letters, before a string or after the string).
- Choose the position in the DNA sequence that contains a letter that
is identical to the modifier gene. Then remove the given letter from the
sequence and destroy the gene modifier.
Gene modifiers’ “use before” date is about to expire, so the professor wants
to use the whole set. How should he use them to get from the initial DNA
sequence a DNA sequence of mutant of maximum possible strength?
The first line contains the initial DNA sequence. The second
line contains the set of gene modifiers. Both strings are non-empty,
consist of small English letters and have length not more than 100 000.
Output the lexicographically minimum DNA sequence that
can be obtained after using all gene modifiers.
It is guaranteed that it is impossible to get an empty string from
the initial DNA using all gene modifiers.
Problem Author: Ilya Kuchumov
Problem Source: Ural Regional School Programming Contest 2013