客户 Oleg 和分析师 Igor 是好朋友。不过,有时他们也会因为一些小事而争吵。最近,他们创办了一家新公司,但在为公司取名时遇到了困难。
为了解决这个问题,他们决定玩一个游戏。公司名称由n个字母组成。 Oleg 和 Igor 各有一组 n 个字母(可能包含同一字母的多个副本,这些字母组可以不同)。最初,公司名称由n个问号表示。奥列格和伊戈尔轮流玩游戏,奥列格先行动。在每一回合中,玩家可以选择他的集合中的字母 c 之一,并用 c 替换任何问号。然后,字母 c 的副本从他的集合中删除。当所有问号都被某个字母取代时,游戏结束。
例如,假设 Oleg 有一组字母 {i, o, i},而 Igor 有一组字母 {i, m, o}。一种可能的游戏如下:
最初,公司名称是???。
Oleg 将第二个问号替换为“i”。公司名称变为“i”。 Oleg 现在拥有的字母集是 {i, o}。
Igor 将第三个问号替换为“o”。公司名称变为?io。 Igor 现在拥有的字母集是 {i, m}。
最后,Oleg 将第一个问号替换为“o”。公司名称变为oio。 Oleg 现在拥有的字母集是 {i}。
最后,公司名称为oio。
Oleg 希望公司名称按字典顺序尽可能小,而 Igor 希望公司名称按字典顺序尽可能大。如果奥列格和伊戈尔总是发挥最佳状态,公司的名称是什么?
如果 si < ti,其中 i 是满足 si ≠ ti 的最小索引,则按字典顺序,字符串 s = s1s2...sm 被称为小于字符串 t = t1t2...tm(其中 s ≠ t)。 (所以 sj = tj 对于所有 j < i)
输入
输入的第一行包含长度为 n (1 ≤ n ≤ 3·105) 的字符串 s。字符串中的所有字符都是小写英文字母。该字符串表示 Oleg 最初的字母集。
输入的第二行包含长度为 n 的字符串 t。字符串中的所有字符都是小写英文字母。该字符串表示 Igor 最初拥有的字母集。
输出
输出应包含一个由 n 个小写英文字母组成的字符串,表示 Oleg 和 Igor 发挥最佳状态时的公司名称。
示例
输入 #1
tinkoff zscoder
输出 #1
fzfsirk
输入 #2
xxxxxx xxxxxx
输出 #2
xxxxxx
输入 #3
ioi imo
输出 #3
ioi
注意
在第一个示例中实现最佳播放效果的一种方法如下:
- 最初,公司名称是??????。
- Oleg 将第一个问号替换为“f”。公司名称变成f??????。
- Igor 将第二个问号替换为“z”。公司名称变成fz??????。
- Oleg 将第三个问号替换为“f”。公司名称变成fzf???。
- Igor 将第四个问号替换为“s”。公司名称变成fzfs???。
- Oleg 将第五个问号替换为“i”。公司名称变成fzfsi??。
- Igor 将第六个问号替换为“r”。公司名称变为fzfsir?。
- Oleg 将第七个问号替换为“k”。公司名称变为 fzfsirk。
对于第二个样本,无论他们如何发挥,公司名称始终是xxxxxx。