Lexicographically Smallest Merge of Two Numeric Strings

Given two numeric strings \(A\) and \(B\), merge them (preserving the order of digits in each string) to form a new string \(T\). Among all possible merges, find the one that is lexicographically smallest.

You must select digits from the front of either string \(A\) or \(B\) at each step. When the current digits are equal, compare the remaining parts \(A[i:]\) and \(B[j:]\) (in \(\LaTeX\), written as \(A[i:]\) and \(B[j:]\)) to break the tie.

Note: The input consists of two lines. The first line contains string \(A\) and the second line contains string \(B\).

inputFormat

The input contains two lines:

• The first line is the numeric string \(A\).
• The second line is the numeric string \(B\).

outputFormat

Output the lexicographically smallest merge string \(T\) formed by interleaving \(A\) and \(B\) while preserving the order of digits in each string.

sample

123
456

123456