MINSEQ - Minimal Possible String

no tags 

Given two strings A and B, your are to find the lexicographically smallest string after inserting B into A.

For example, string A is "369", and string B is "4799". There are 4 ways that I can insert B into A, and I’ll get 4 different results: 4799369, 3479969, 3647999, 3694799. Thus, 3479969 is the lexicographically smallest one.

Input

Input contains several cases. Each case has 2 strings A and B with length no longer than 100000 in 2 lines. Process the input until EOF. The strings consist of only digit 1-9.

Output

For each case, output the minimal possible result.

Example

Input:
369
4799
666
12345

Output:
3479969
12345666

hide comments
3xian: 2011-06-26 16:54:23

@nagy mohamed
Yes.

Nagy Mohamed: 2011-06-26 16:54:23

what is meant by lexicographically smallest one?
is it smallest number can be formed by adding number b in number a

[Trichromatic] XilinX: 2011-06-26 16:54:23

Use "while(scanf("%s"),s)!=EOF", don't use "while(gets(s))". There must be some empty lines (which should be ignored) in the input file.

Neha Gupta: 2011-06-26 16:54:23

Are there any empty lines before or after the input?


Added by:3xian
Date:2009-10-30
Time limit:1s-1.567s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 PERL6
Resource:GDUT Monthly