问题陈述
Y教授的工作是挖掘古代文物。 最近,他发现了很多奇怪的石板,每块石板上都有$N^2$个字符,排列成$N×N$的矩阵。 进一步的研究表明,每个板块代表一条长度为 $N$ 的消息。 此外,从盘子上解码消息的过程如下:
从车牌中一一选择$N$个字符,使任意两个字符既不在同一行,也不在同一列。
通过连接选定的字符来创建字符串。
在上述步骤得到的所有可能的字符串中,找到字典序最小的一个。这就是这个盘子所代表的信息。
注意:字符的顺序定义为其 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