Lexicographically Smallest String Construction

You are given a string \( S \) of length \( N \) consisting of lowercase letters, and an additional set of \( M \) lowercase letters \( c_1, c_2, \dots, c_M \). Each of these extra letters can be inserted at any position in \( S \) (including at the beginning, between any two characters, or at the end). The relative order of the characters originally in \( S \) must be preserved.

Your task is to determine the lexicographically smallest string that can be obtained after inserting all \( M \) letters into \( S \).

Note: When comparing two strings, the lexicographical order is determined by comparing corresponding characters from left to right. If one string is a prefix of another, the shorter string is considered smaller.

The optimal strategy is to sort the extra letters and merge them with the original string \( S \) in such a way that at each step, you choose the smallest possible next character while preserving the relative ordering of characters in \( S \) and in the sorted extra letters.

The decision of which character to pick at every merge step should be made by comparing the remaining substring of \( S \) with the remaining sorted extra letters (treated as a string). Formally, let \( A \) be the substring of \( S \) yet to be used and \( B \) be the sorted list of extra letters that remain (concatenated into a string). At each step, if \( A \) is lexicographically less than or equal to \( B \), choose the first character from \( A \); otherwise, choose the first character from \( B \>.

inputFormat

The input consists of three lines:

1. A string \( S \) (a sequence of lowercase letters).
2. An integer \( M \) representing the number of extra letters.
3. \( M \) lowercase letters separated by spaces.

You can assume that \( 1 \leq |S| \leq 10^5 \) and \( 1 \leq M \leq 10^5 \).

outputFormat

Output the lexicographically smallest string that can be obtained after inserting all extra letters into \( S \).

sample

b
1
a

ab