/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 7 点
注意
この問題に対する言及は、2020/6/6 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
整数 N 及び 小文字アルファベットからなる N×N 行列 a が与えられます。 以下の条件を満たすような 長さ N の文字列 S をいずれか 1 つ構築してください。
- 文字列 S は英小文字から構成される。
- 文字列 S は回文である。なお, 回文とは前から読んでも後ろから読んでも同じである文字列である。
- S_{i} は a_{i,1},a_{i,2}, \ldots, a_{i,N} のいずれかと同じ文字である。
ただし、条件を満たす文字列が存在しない場合はそれを指摘してください。
制約
- N は整数
- 1 \leq N \leq 500
- a_{i,j} は英小文字
入力
入力は以下の形式で標準入力から与えられる。
N
a_{1,1}a_{1,2}\cdotsa_{1,N}
\vdots
a_{N,1}a_{N,2}\cdotsa_{N,N}
出力
条件を満たす文字列が存在する場合は、そのような文字列を以下の形式で出力せよ。
S_{1}S_{2}S_{3}\cdotsS_{N}
条件を満たす文字列が複数存在する場合は、そのうちのいずれを出力してもよい。
条件を満たす文字列が存在しない場合は、-1 を出力せよ。
入力例 1
2 yc ys
出力例 1
yy
入力例 2
2 rv jh
出力例 2
-1
Score : 7 points
Warning
Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
Given an integer N and a matrix a of size N×N consisting of lowercase English letters. Your task is to construct a string S of length N that satisfies the following conditions:
- The string S contains only lowercase English letters.
- The string S is a palindrome. Recall that a string is called a palindrome if it reads the same way in both directions.
- Every character S_{i} equals at least one of the characters a_{i,1},a_{i,2}, \ldots, a_{i,N}.
If no strings can satisfy all the above conditions, you have to point out this fact.
Constraints
- N is an integer.
- 1 \leq N \leq 500
- Each character a_{i,j} is a lowercase English letter.
Input
Input is given from Standard Input in the following format:
N
a_{1,1}a_{1,2}\cdotsa_{1,N}
\vdots
a_{N,1}a_{N,2}\cdotsa_{N,N}
Output
If there exists a string S that satisfies all the conditions, print the answer in the following format:
S_{1}S_{2}S_{3}\cdotsS_{N}
If there exist multiple strings satisfying all the conditions, you can print any of them.
If there is no solution, print -1.
Sample Input 1
2 yc ys
Sample Output 1
yy
Sample Input 2
2 rv jh
Sample Output 2
-1