Problem Description

Given an integer \( N \) and an \( N \times N \) matrix \( a \) consisting of lowercase alphabets, construct a string \( S \) of length \( N \) that satisfies the following conditions:

• The string \( S \) consists of lowercase English letters.
• The string \( S \) is a palindrome. A palindrome is a string that reads the same forward and backward.
• \( S_i \) is the same as one of the characters in \( a_{i,1}, a_{i,2}, \ldots, a_{i,N} \).

If no such string exists, indicate that.

Input Format

The input is given from the standard input in the following format:

\( N \) \( a_{1,1} \) \( a_{1,2} \) \( \cdots \) \( a_{1,N} \) \( \vdots \) \( a_{N,1} \) \( a_{N,2} \) \( \cdots \) \( a_{N,N} \)

Output Format

If a string satisfying the conditions exists, output such a string in the following format:

\( S_1 \) \( S_2 \) \( S_3 \) \( \cdots \) \( S_N \)

If multiple such strings exist, you may output any one of them.

If no such string exists, output \( -1 \).

Sample Input and Output

Sample Input #1

2
yc
ys

Sample Output #1

yy

Sample Input #2

2
rv
jh

Sample Output #2

-1

Notes/Hints

Constraints

• \( N \) is an integer
• \( 1 \leq N \leq 500 \)
• \( a_{i,j} \) is a lowercase English letter

见题面 Input 部分

见题面 Output 部分