AT_past202005_f.回文行列

给定一个整数 $N$ 和一个由小写英文字母组成的 $N \times N$ 矩阵 $a$。请构造一个满足以下条件的长度为 $N$ 的字符串 $S$（只需构造一个即可）。

• 字符串 $S$ 由小写英文字母组成。
• 字符串 $S$ 是回文串。回文串是指正着读和反着读都相同的字符串。
• $S_i$ 必须等于 $a_{i,1}, a_{i,2}, \ldots, a_{i,N}$ 中的某一个字符。

如果不存在满足条件的字符串，请指出。

输入通过标准输入给出，格式如下：

$N$
$a_{1,1}\ a_{1,2}\ \cdots\ a_{1,N}$
$\vdots$
$a_{N,1}\ a_{N,2}\ \cdots\ a_{N,N}$

如果存在满足条件的字符串，输出该字符串：

$S_1 S_2 S_3 \cdots S_N$

如果不存在满足条件的字符串，输出 $-1$。

注意

本题在 2020 年 6 月 6 日 18:00（日本标准时间）之前禁止讨论。如有违反，可能会被要求赔偿。考试结束后可以公开总分和认证等级，但请不要透露解答了哪些题目等信息。

约束条件

• $N$ 是整数。
• $1 \leq N \leq 500$。
• $a_{i,j}$ 是小写英文字母。

由 ChatGPT 4.1 翻译