题目描述

两个字符串可以穿插合并成一个字符串。规则是不断地提取两个字符串的首字母，直到两个字符串被取完为止，以提取的顺序合并成一个字符串。

比如 $ac$ 与 $bd$ 可以穿插成 $abcd$，也可以穿插成 $acbd$ 或 $bdac$。

给定两个字符串 $s$ 与 $t$，$s$ 由一部分英文字符构成，$t$ 由另一部分英文构成，请将它们穿插合并成一个字典序意义下最小的字符串。

所谓字典序，是指两个字符串比较大小的方法：

• 空串是最小的字符串；
• 对于两个不为空的字符串，如果首字母不同，则首字母较小的字符串更小；
• 否则，以去掉首字母后剩余的字符串的字典序为准。

输入格式

• 第一行：一个字符串表示 $s$
• 第二行：一个字符串表示 $t$
• 保证 $s$ 与 $t$ 只包含小写字母，且 $t$ 的字符与 $s$ 完全不同。

输出格式

• 第一行：一个字符串表示 $s$ 与 $t$ 穿插后形成的最小字符串。

acca
bbdd

abbccadd

数据范围

记 $s$ 的长度为 $|s|$

• $30\%$ 的分数，$1\leq |s|, |t|\leq 100$
• $60\%$ 的分数，$1\leq |s|, |t|\leq 10,000$
• $100\%$ 的分数，$1\leq |s|, |t|\leq 100,000$