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