← 返回题目列表

Codeforces · 58/D

D. 日历

中文机器翻译题面 查看原题

BerOilGasDiamondBank在n个城市设有分行,其中n为偶数。银行管理层想要发布一份日历,其中所有这些城市的名称写成两列:该日历应由严格相等长度的 n / 2 行组成,每行恰好包含两个名称以及它们之间的一个分隔符。每个城市的名称应在日历中仅使用一次。由于历史原因,符号 d 被用作日历中单词的分隔符。

BerOilGasDiamondBank 管理层希望表明其所有分支机构对其同等重要,这就是为什么它们在日历中出现的顺序应如下:如果我们“粘合”(连接)所有 n / 2 条日历线(从上到下)形成一条线,则获得字典顺序最小的线。不会使用分隔符来分隔日历行。例如,如果行是“bertown!berville”、“newberville!bera”,则结果行是“bertown!bervillenewberville!bera”。从某种意义上说,人们必须找到字典顺序最小的日历,其中日历的比较是逐行进行的。

帮助 BerOilGasDiamondBank 构建所需的日历。

输入

第一行包含一个整数n(1≤n≤104,n为偶数),它是分支的数量。然后n行是城市的名称。所有名称均由小写拉丁字母组成;它们的长度不少于1个且不超过10个符号。下一行包含一个符号 d(d 的 ASCII 代码为 33 到 126,不包括小写拉丁字母),它是日历行中单词之间的分隔符。保证日历可以被构造并且所有的名称都是不同的。

输出

打印 n / 2 行相似长度的行,这是所需的日历。每一行应包含正好两个单词,并且它们之间正好有一个分隔符。如果有多个解决方案,请打印字典顺序最小的一个。现代编程语言中行的字典序比较是通过“<”运算符实现的。

示例

输入 #1

4
b
aa
hg
c
.

输出 #1

aa.b
c.hg

输入 #2

2
aa
a
!

输出 #2

a!aa

输入 #3

2
aa
a
|

输出 #3

aa|a