A. Amalgram
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

An anagram is any arrangement of the letters of a word in which each letter of the alphabet occurs exactly as many times as in the original. For example, clarinets is an anagram of larcenist.

An amalgram is any arrangement of the letters of two words in which each letter of the alphabet occurs at least as many times as in either of the originals. For example, administration is an amalgram of mantis and raisin, although not the shortest possible because the letter d appears in neither.

Given two words, invent an amalgram for them that contains as few letters as possible.

Input

  • One line containing lowercase Latin letters representing the word $$$a$$$ ($$$1 \le |a| \le 10^6$$$).
  • One line containing lowercase Latin letters representing the word $$$b$$$ ($$$1 \le |b| \le 10^6$$$).
Output

Output a minimally-long sequence of letters that represents an amalgram of $$$a$$$ and $$$b$$$. If there are multiple answers, you may output any of them. Your answer will be judged as correct if it contains at least all of the letters of $$$a$$$ and all of the letters of $$$b$$$, and there is no other possible answer that could be shorter.

Examples
Input
hello
world
Output
wordhell
Input
unclear
instructions
Output
lensrustication
Input
boring
boring
Output
boring