Problem A. Alphabetic replacement

Author:M. Sporyshev   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

You are given two strings of small Latin letters, S and T. Some letters of string S may be replaced by letters of T according to the following rules:

  1. Each letter from T may be used only once or not used at all.
  2. Letters from T must be used in order from left to right. In other words, if letter Si is replaced by letter Tp, letter Sj is replaced by letter Tq, and i < j, then p < q.

You program must modify string S according to the rules above to get lexicographically smallest string.

Input file format

First line of input file contains string S. Second line of input file contains string T.

Output file format

Output file must contain optimally modified string S.

Constraints

0 < |S|, |T| ≤ 105

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
aaa
abacaba
aaa
2
ababcaba
abca
aaaacaba

0.069s 0.009s 13