← 返回题目列表

AtCoder · icpc2014spring_c

C. 解码古代消息

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

问题陈述

Y教授的工作是挖掘古代文物。 最近,他发现了很多奇怪的石板,每块石板上都有$N^2$个字符,排列成$N×N$的矩阵。 进一步的研究表明,每个板块代表一条长度为 $N$ 的消息。 此外,从盘子上解码消息的过程如下:

  1. 从车牌中一一选择$N$个字符,使任意两个字符既不在同一行,也不在同一列。

  2. 通过连接选定的字符来创建字符串。

  3. 在上述步骤得到的所有可能的字符串中,找到字典序最小的一个。这就是这个盘子所代表的信息。

注意:字符的顺序定义为其 ASCII 值的顺序(即 $\mathtt{A} \lt \mathtt{B} \lt \cdots \lt \mathtt{Z} \lt \mathtt{a} \lt \mathtt{b} \lt \cdots \lt \mathtt{z}$)。

在与板块斗争之后,Y 教授放弃了手工解码信息。 你,一位伟大的程序员,也是 Y 的老朋友,有人向你寻求帮助。 你的任务是编写一个程序来解码隐藏在盘子中的消息。


输入

输入格式如下:

$N$
$c_{11} c_{12} \cdots c_{1N}$
$c_{21} c_{22} \cdots c_{2N}$
:
:
$c_{N1} c_{N2} \cdots c_{NN}$

第一行包含一个整数 $N$ ($1 \le N \le 50$)。 随后的每一行 $N$ 都包含一个由 $N$ 个字符组成的字符串。 字符串中的每个字符都是大写或小写英文字母(A-Z, a-z).

输出

打印一行中的板代表的消息。


示例输入 1

3
aab
czc
baa

样本输入 1 的输出

aac

示例输入 2

36
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiQiiiiiiiiiiiiiiiQiiiiiiiii
iiiiiiiiiiQQQiiiiiiiiiiQQQQiiiiiiiii
iiiiiiiiiiQQQQQiiiiiiiQQQQiiiiiiiiii
iiiiiiiiiiiQQQQQQQQQQQQQQQiiiiiiiiii
iiiiiiiiiiiQQQQQQQQQQQQQQQiiiiiiiiii
iiiiiiiiiiiQQQQQQQQQQQQQQiiiiiiiiiii
iiiiiiiiiiiiQQQQQQQQQQQQQiiiiiiiiiii
iiiiiiiiiiiQQQQQQQQQQQQQQQiiiiiiiiii
iiiiiiiiiiQQQQQQQQQQQQQQQQQiiiiiiiii
iiiiiiQiiiQQQQQQQQQQQQQQQQQiiiQiiiii
iiiiiiQQiQQQQQQQQQQQQQQQQQQiiQQiiiii
iiiiiiiQQQQQQQQQQQQQQQQQQQQiQQiiiiii
iiiiiiiiiQQQQQQQQQQQQQQQQQQQQiiiiiii
iiiiiiiiQQQQQiiQQQQQQQQiiQQQQQiiiiii
iiiiiiQQQQQQiiiiQQQQQiiiiQQQQQQiiiii
iiiiiQQQQQQQQiiiQQQQQiiQQQQQQQQiQiii
iiiQQQQQQQiiQiiiQQQQQiiQiiQQQQQQQQii
iQQQQQQQQQiiiiiQQQQQQQiiiiiiQQQQQQQi
iiQQQQQQQiiiiiiQQQQQQQiiiiiiiiQQQiii
iQQQQiiiiiiiiiQQQQQQQQQiiiiiiiiQQQii
iiiiiiiiiiiiiiQQQQQQQQQiiiiiiiiiiiii
iiiiiiiiiiiiiQQQQQQQQQQiiiiiiiiiiiii
iiiiiiiiiiiiiQQQQQQQQQQiiiiiiiiiiiii
iiiiiiiiiiiiiiQQQQQQQQiiiiiiiiiiiiii
iiiiiiiiiiiiiiQQQQQQQQiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii

样本输入 2 的输出

QQQQQQQQQQQQQQQQQQQQQQQQQiiiiiiiiiii

示例输入 3

3
Acm
aCm
acM

样本输入 3 的输出

ACM