题目描述

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

比如 $acac$ 与 $bdbd$ 可以穿插成 $abcdabcd$，也可以穿插成 $acbdacbd$ 或 $bdacbdac$。

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

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

空串是最小的字符串；

对于两个不为空的字符串，如果首字母不同，则首字母较小的字符串更小；

否则，以去掉首字母后剩余的字符串的字典序为准。

输入格式

第一行：一个字符串表示 s

第二行：一个字符串表示 t

保证 s 与 t 只包含小写字母，且 t 的字符与 s 完全不同。

输出格式

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

样例 #1

样例输入 #1

acca
bbdd

样例输出 #1

abbccadd

提示

记 s 的长度为 ∣s∣

30% 的分数，$1≤∣s∣,∣t∣≤100$

60% 的分数，$1≤∣s∣,∣t∣≤10,000$

100% 的分数，$1≤∣s∣,∣t∣≤100,000$