ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

2007. Mutants versus Machines

Time limit: 0.5 second
Memory limit: 64 MB
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.
  1. Insert a gene modifier into any place of the DNA sequence (between the letters, before a string or after the string).
  2. 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