CF58D Calendar

BerOilGasDiamondBank 在 $n$ 个城市拥有分行，其中 $n$ 是一个偶数。银行管理层希望发布一份日历，在日历上将所有这些城市的名字分成两列写出：日历应正好包含 $n/2$ 行，每行长度完全相等，每行恰好包含两个名字，且它们中间用一个分隔符字符隔开。每个城市的名字恰好在日历中出现一次。由于历史原因，分隔符采用符号 $d$。 银行管理层想要表明所有分行对他们来说同等重要，因此城市名称在日历上的排列顺序需要满足：若将 $n/2$ 行从上到下依次“粘合”（拼接）为一行（行与行之间不加任何分隔符），则得到的整个字符串是所有拼接方式中字典序最小的。例如，如果两行为 "bertown!berville" 和 "newberville!bera"，拼接后为 "bertown!bervillenewberville!bera"。换句话说，需要找到字典序最小的日历，字典序的比较以整行作为单位进行。 请帮助 BerOilGasDiamondBank 构造满足要求的日历。

第一行包含一个整数 $n$（$1 \leq n \leq 10^{4}$，$n$ 为偶数），表示分行数量。接下来的 $n$ 行，每行包含一个城市的名字。所有名字均由小写拉丁字母组成，长度不少于 $1$ 且不超过 $10$。最后一行给出单个字符 $d$（$d$ 的 ASCII 码在 $33$ 到 $126$ 之间，且不是小写拉丁字母），作为日历中城市名字的分隔符。保证可以构造出满足要求的日历，且所有城市名各不相同。

输出 $n/2$ 行，每行格式与要求的日历一致。每行应恰好包含两个城市名字和一个分隔符，且长度相同。如果有多种方案，输出字典序最小的那一个。行的字典序比较以现代编程语言中的 "

由 ChatGPT 5 翻译