Replacing Digits

2000ms

262144K

Description:

You are given an integer a that consists of n digits. You are also given a sequence of digits s of length m. The digit in position j (1 ≤ j ≤ m) of sequence s means that you can choose an arbitrary position i (1 ≤ i ≤ n) in a and replace the digit in the chosen position i with s_j. Each element in the sequence s can participate in no more than one replacing operation.

Your task is to perform such sequence of replacements, that the given number a gets maximum value. You are allowed to use not all elements from s.

Input:

The first line contains positive integer a. Its length n is positive and doesn't exceed 10⁵. The second line contains sequence of digits s. Its length m is positive and doesn't exceed 10⁵. The digits in the sequence s are written consecutively without any separators.

The given number a doesn't contain leading zeroes.

Output:

Print the maximum value that can be obtained from a after a series of replacements. You are allowed to use not all elements from s. The printed number shouldn't contain any leading zeroes.

Sample Input:

1024
010

Sample Output:

Sample Input:

987
1234567

Sample Output:

Informação

Provedor Codeforces

Código CF169B