CF794C Naming Company

Oleg 和 Igor 是好朋友，不过有时他们会因为小事争论。最近，他们创办了一家公司，但在为公司起名字时遇到困难。 为了解决这个问题，他们决定玩一个游戏。公司名字将由 $n$ 个字母组成。Oleg 和 Igor 各自有一个包含 $n$ 个字母的集合（集合中可能有重复字母，两个集合可能不同）。一开始，公司名字由 $n$ 个问号表示。Oleg 和 Igor 轮流进行操作，Oleg 先手。在每一回合，当前玩家可以选择自己集合中的一个字母 $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 则希望名字字典序尽可能大。如果两人都采取最优策略，公司名字会是什么？ 对于两个长度为 $m$ 的字符串 $s = s_1 s_2...s_m$ 和 $t = t_1 t_2...t_m$（$s \neq t$），如果存在最小的下标 $i$ 满足 $s_i \neq t_i$ 且 $s_i < t_i$（且对于所有 $j < i$，$s_j = t_j$），那么 $s$ 的字典序比 $t$ 小。

输入第一行是长度为 $n$ 的字符串 $s$（$1\leq n\leq 3\times10^5$），所有字符均为小写英文字母。该字符串表示 Oleg 起始时所拥有的字母集合。 输入第二行是长度为 $n$ 的字符串 $t$，也全是小写英文字母，表示 Igor 起始的字母集合。

输出一行，包含 $n$ 个小写英文字母，表示按照最优策略游戏后得到的公司名字。

第一个样例的一种最优策略如下： - 初始名字是 ???????。 - Oleg 把第一个问号替换为 ‘f’，名字变为 f??????。 - Igor 把第二个问号替换为 ‘z’，名字变为 fz?????。 - Oleg 把第三个问号替换为 ‘f’，名字变为 fzf????。 - Igor 把第四个问号替换为 ‘s’，名字变为 fzfs???。 - Oleg 把第五个问号替换为 ‘i’，名字变为 fzfsi??。 - Igor 把第六个问号替换为 ‘r’，名字变为 fzfsir?。 - Oleg 把第七个问号替换为 ‘k’，名字变为 fzfsirk。 对于第二个样例，无论怎么玩，最终公司名字都只会是 xxxxxx。 由 ChatGPT 5 翻译